What iterator does .end() return exactly？

[RicoJ]

Now I am trying to write my own container and I need to return an end iterator using .end() function. I understand that for containers such as vector, end is simply

template<typename T>
class vec
{
public:
    // type definitions, constructor are omitted here
    iterator end(){return beg+size;}     //end is simply a pointer that points to the contiguous memory location past the last element. 
private:
    iterator beg, end;
    size_type size; 
}

However, for containers like list, how to implement .end()? Do I dynamically append an empty node at the end of the list and make end point to that node?

[highwayman]

Have you checked the reference yet?

http://www.cplusplus.com/reference/list/

[highwayman]

Nvm that doesn’t tell you crap in that thing, sry.

[dutch]

And end iterator for a list could be an iterator object containing a nullptr.

[mbozzi]

The trick is to use the null-pointer as the empty node. end() is always after the last element in the list.

Maybe implement it somewhat like this:

#include <iostream>
#include <string>

namespace my {
  struct node {
    node() = default;
    explicit node(int value, node *next = nullptr) : data_(value), next_(next) {}
  
    int data_;
    node *next_ = nullptr;
  };
  
  // TODO(mbozzi): define a class template
  struct forward_list {
    forward_list() = default;
    ~forward_list() { while (!empty()) erase_after(&head_); }
    
    forward_list(forward_list const &)            = delete;
    forward_list(forward_list &&)                 = delete;
    forward_list operator=(forward_list const &)  = delete;
    forward_list operator=(forward_list const &&) = delete;
    
    // TODO(mbozzi): const_iterator
    struct iterator 
    {
      friend struct forward_list;

      int  operator*()  const { return n_->data_; }
      int* operator->() const { return std::addressof(n_->data_); }
        
      iterator operator++()    
      { n_ = n_->next_; return *this; }
      iterator operator++(int) 
      { iterator result(*this); ++(*this); return result; }
        
      friend bool operator==(iterator l, iterator r) 
      { return l.n_ == r.n_; }
      friend bool operator!=(iterator l, iterator r)
      { return !(l == r); }

    private:
        node* n_;
        
        explicit iterator(node* n = nullptr)
          : n_(n) 
        {}
    };
    
    iterator begin() { return iterator(head_.next_); }
    iterator end()   { return iterator(); }

    bool empty() const { return head_.next_; }
    void push_front(int value) { insert_after(&head_, value); }
  
    std::string to_string() const {
      std::string result;
      for (node const *tmp = &head_; (tmp = tmp->next_);)
        result += std::to_string(tmp->data_) + ' ';
      return result;
    }
  
  private:
    node *erase_after(node *pos) {
      node *current = pos->next_;
      pos->next_ = current->next_;
      delete current;
      return pos->next_;
    }
  
    node *insert_after(node *pos, int value) {
      node *thing = new node(value);
      thing->next_ = pos->next_;
      return pos->next_ = thing;
    }
  
    node head_;
  };
} // namespace my

int main() {
  my::forward_list l;

  for (int i = 1; i <= 10; ++i) 
    l.push_front(i);
  
  for (auto elt : l)
    std::cout << elt << '\n';
}

[Duthomhas]

It can be anything you like, but a nullptr works.

There are a number of good places to reference when writing your own iterators:
http://www.cplusplus.com/reference/iterator/iterator/
http://www.cplusplus.com/reference/iterator/
https://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B

Your List<T> might look something like this:

template <typename T>
struct List
{
  struct Node
  {
    T      data;
    Node* next;
  };

  Node* head;

  ...

  struct Iterator: public std::iterator <std::forward_iterator_tag, T>
  {
    Node* current;
    Iterator( Node* current ): current(current) { }
    Iterator& operator ++ () { if (current) current = current->next; return *this; }
    Iterator operator ++ (int) { Iterator p( current ); operator ++ (); return p; }
    bool operator == ( const Iterator& that ) const { return this->current == that.current; }
    bool operator != ( const Iterator& that ) const { return this->current != that.current; }
    T& operator * () { return current->data; }
  };

  Iterator begin() { return Iterator( head ); }
  Iterator end() { return Iterator( nullptr ); }
};

BTW, I just typed this off the top of my head. Typos and dumb mistakes may have occurred.

Hope this helps.

[ne555]

> an iterator object containing a nullptr.
> The trick is to use the null-pointer
> a nullptr works.

--list.end();
list.insert(list.end(), 42);

> However, for containers like list, how to implement .end()?
it will depend on your implementation of the list and the functionallity you may want to provide.
for example, you may use a header cell, then the iterator points to the previous cell
iter->next->value; //to dereference
so the .begin() iterator will point to the header, and the .end() to the last cell

[dhayden]

ne555 wrote:

--list.end();

This is a critical point, and one that makes the suggested implementations incorrect.

#include <iostream>
#include <list>

using namespace std;

int main()
{
    list<int> list1, list2;
    list1.push_front(1);
    list2.push_front(2);

    // The iterator must know which list it points to
    // EDIT - comparing iterators from different containers is irrelevant. See Duthomas's comment below
    list<int>::iterator iter1 = list1.end(), iter2=list2.end();
    cout << "list1.end() == list2.end()? " << (iter1 == iter2) << '\n';

    // You must be able to decrement the end() iterator
    iter1--;
    iter2--;
    cout << *iter1 << ' ' << *iter2 << '\n';
}

list1.end() == list2.end()? 0
1 2

Read the details of bidirectional iterator: http://www.cplusplus.com/reference/iterator/BidirectionalIterator/. Think carefully about iterators to different lists, and the begin() and end() values.

[keskiverto]

However, for containers like list, how to

"Like list" as in "like std::list" OR as in "like std::forward_list"?

The first is double-linked list and provides bidirectional iterators, while
the second is single-linked list and provides forward iterators.

Forward iterator does not have operator--
but list1.end() == list2.end()? is still relevant.

[dutch]

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> a{1, 2}, b{3, 4, 5};
    if (a.end() == b.end()) std::cout << "equal\n";  // prints "equal" (g++)
}

[Duthomhas]

“Linked List” typically means “singly-linked list”, unless specifically disambiguated with introductory wording to the effect that we are dealing with a “doubly-linked list”.

Admittedly, OP referred specifically to the std::list container, which is indeed a doubly-linked list.


RE: --list.end()
True indeed if your list is a doubly-linked list. And, oddly enough, it is fairly trivial to turn your forward iterator into a bidirectional iterator. The simplest way is to make your iterator have a reference to the list object itself, which presumably maintains both a head and tail node pointer. Hence, and invalid value, like ‘end’, can be easily dealt with.

It might also be worth some time reading up on std::reverse_iterator and how it works.


RE: list1.end() == list2.end()
This is never relevant; there is no possible twist of logic to expect any iterators from separate containers to compare equal.

That they may compare equal is irrelevant trivia. Anyone seeking code review where disparate container’s iterators compare equal will be asked to rewrite the code correctly.

Note that this is sometimes explicitly flaunted when creating iterators over sequences (meaning, the documentation says that all end iterators are equal) so that you can treat, say, a stream, as if it were a sequenced object. See std::istream_iterator for the details. And remember, this is both exceptional and explicit and, notably, completely fails the “--end” thingy, as it is a unidirectional iterator.


Iterators are tools, designed to look and generally behave like pointers, but they are, in the end, not perfect and must be used within documented constraints.

OP, implementing an iterator is not typically difficult, but it does require a lot of boilerplate and some thinking. My recommendation is to make your iterator support the same level of access as your container: if your container is random-access, make your iterators random-access; if your container is bidirectional, make your iterators bidirectional. Etc.

Hope this helps.

[RicoJ]

Ok I got it, since we can compare two iterators by comparing their pointers, we simply set the last valid element to point to null, and when we want to compare a iterator with .end(), we simply generate an empty iterator with null pointer.

Thanks guys!