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

Question

I made a collection for which I want to provide an STL-style, random-access iterator. I was searching around for an example implementation of an iterator but I didn't find any. I know about the need for const overloads of [] and * operators. What are the requirements for an iterator to be "STL-style" and what are some other pitfalls to avoid (if any)?

Additional context: This is for a library and I don't want to introduce any dependency on it unless I really need to. I write my own collection to be able to provide binary compatibility between C++03 and C++11 with the same compiler (so no STL which would probably break).

Answer 1

http://www.cplusplus.com/reference/std/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.