How to implement an STL-style iterator and avoid common pitfalls?

c++, const-iterator, iterator

Solution

https://cplusplus.com/reference/iterator/ has a handy chart that details the specs of § 24.2.2 of the C++11 standard. Basically, the iterators have tags that describe the valid operations, and the tags have a hierarchy. Below is purely symbolic, these classes don't actually exist as such.

iterator {
    iterator(const iterator&);
    ~iterator();
    iterator& operator=(const iterator&);
    iterator& operator++(); //prefix increment
    reference operator*() const;
    friend void swap(iterator& lhs, iterator& rhs); //C++11 I think
};

input_iterator : public virtual iterator {
    iterator operator++(int); //postfix increment
    value_type operator*() const;
    pointer operator->() const;
    friend bool operator==(const iterator&, const iterator&);
    friend bool operator!=(const iterator&, const iterator&); 
};
//once an input iterator has been dereferenced, it is 
//undefined to dereference one before that.

output_iterator : public virtual iterator {
    reference operator*() const;
    iterator operator++(int); //postfix increment
};
//dereferences may only be on the left side of an assignment
//once an output iterator has been dereferenced, it is 
//undefined to dereference one before that.

forward_iterator : input_iterator, output_iterator {
    forward_iterator();
};
//multiple passes allowed

bidirectional_iterator : forward_iterator {
    iterator& operator--(); //prefix decrement
    iterator operator--(int); //postfix decrement
};

random_access_iterator : bidirectional_iterator {
    friend bool operator<(const iterator&, const iterator&);
    friend bool operator>(const iterator&, const iterator&);
    friend bool operator<=(const iterator&, const iterator&);
    friend bool operator>=(const iterator&, const iterator&);

    iterator& operator+=(size_type);
    friend iterator operator+(const iterator&, size_type);
    friend iterator operator+(size_type, const iterator&);
    iterator& operator-=(size_type);  
    friend iterator operator-(const iterator&, size_type);
    friend difference_type operator-(iterator, iterator);

    reference operator[](size_type) const;
};

contiguous_iterator : random_access_iterator { //C++17
}; //elements are stored contiguously in memory.

You can either specialize `std::iterator_traits<youriterator>`, or put the same typedefs in the iterator itself, or inherit from `std::iterator` (which has these typedefs). I prefer the second option, to avoid changing things in the `std` namespace, and for readability, but most people inherit from `std::iterator`.

struct std::iterator_traits<youriterator> {        
    typedef ???? difference_type; //almost always ptrdiff_t
    typedef ???? value_type; //almost always T
    typedef ???? reference; //almost always T& or const T&
    typedef ???? pointer; //almost always T* or const T*
    typedef ???? iterator_category;  //usually std::forward_iterator_tag or similar
};

Note the iterator_category should be one of `std::input_iterator_tag`, `std::output_iterator_tag`, `std::forward_iterator_tag`, `std::bidirectional_iterator_tag`, or `std::random_access_iterator_tag`, depending on which requirements your iterator satisfies. Depending on your iterator, you may choose to specialize `std::next`, `std::prev`, `std::advance`, and `std::distance` as well, but this is rarely needed. In extremely rare cases you may wish to specialize `std::begin` and `std::end`.

Your container should probably also have a `const_iterator`, which is a (possibly mutable) iterator to constant data that is similar to your `iterator` except it should be implicitly constructable from a `iterator` and users should be unable to modify the data. It is common for its internal pointer to be a pointer to non-constant data, and have `iterator` inherit from `const_iterator` so as to minimize code duplication.

My post at Writing your own STL Container has a more complete container/iterator prototype.

Problem

Original source

Related problems

• How to correctly implement custom iterators and const_iterators?
• Writing your own STL Container