It is not often necessary to create your own iterator, and I would like to have on hand a small HowTo. In this article I want to tell you how to create a simple iterator that can be used in standard algorithms like std :: copy, std :: find. What methods and type definitions are needed in the container class so that it can be bypassed in for loops from c ++ 11 and BOOST_FOREACH.

Container

In the container class, you need to define the types of the iterator and const_iterator (types are needed first for convenience, and secondly the bypass will not work without them using BOOST_FOREACH), as well as the begin and end methods (depending on the requirements, you can add only constant methods returning const_iterator):
For example, take a container storing an array of integers.

class OwnContainer { public: typedef OwnIterator<int> iterator; typedef OwnIterator<const int> const_iterator; OwnContainer(std::initializer_list<int> values); iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; private: const size_t size; std::unique_ptr<int[]> data; }; 

')
Naturally, nothing prevents the definition of the iterator and const_iterator as aliases of the same type.

Iterator

The iterator should be inherited from the class std :: iterator. By itself, this class does not implement any methods, but declares the necessary types that are used in standard algorithms.


This is a template class, the first parameter of the template is an iterator type, since we are going to use it with the standard library, then the type is selected from the following types: input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, random_access_iterator_tag. The second parameter is the type of value that is stored and returned by the * and -> operators, the termination parameter is a type that can describe the distance between iterators, the fourth template parameter is the type of the pointer to the value, the fifth is the type of the reference to the values. The first two parameters are required.

The easiest iterator is InputIterator (input_iterator_tag), it must support the prefix increment form, the! = Operator, the * operator and the -> operator (I will not implement it, since the iterator is used for the int type in the example, and in this case operator-> meaningless). In addition, you need a constructor and copy constructor. The example does not suppose the creation of an iterator except as the begin and end methods of the container class, therefore the iterator constructor will be private, and the container class will be declared as friendly. And we add the operator ==, firstly it’s good practice to add support! = And == together, and secondly, BOOST_FOREACH will not work without it.

const_iterator is not much different from the iterator, so we declare an iterator as a template class with one parameter — the return type for the * and -> operators.

In the constructor we will pass a pointer to the array element stored in the OwnContainer.

 template<typename ValueType> class OwnIterator: public std::iterator<std::input_iterator_tag, ValueType> { friend class OwnContainer; private: OwnIterator(ValueType* p); public: OwnIterator(const OwnIterator &it); bool operator!=(OwnIterator const& other) const; bool operator==(OwnIterator const& other) const; //need for BOOST_FOREACH typename OwnIterator::reference operator*() const; OwnIterator& operator++(); private: ValueType* p; }; 

We could stop at this, but the boost library has a base class for creating iterators, and I want to say a few words about it.

Iterator inherited from boost :: iterator_facade

A container differs only in the types referenced by the iterator and const_iterator:

 class OwnContainerBBI { public: typedef OwnIteratorBB<int> iterator; typedef OwnIteratorBB<const int> const_iterator; OwnContainerBBI(std::initializer_list<int> values); iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; private: const size_t size; std::unique_ptr<int[]> data; }; 

The iterator is inherited from the template type boost :: iterator_facade. This is a template class, the first parameter is the type of the heir, the second type of value, the third type of iterator. The type used in std :: iterator and boost-specific (in the description this option is designated as old-style) can act as an iterator type, I will take the same type as for std :: iterator. boost :: iterator_facade implements the necessary methods: operator *, operator ++, operator->, etc. But their implementation is based on auxiliary methods that need to be implemented in our iterator, namely dereference, equal, increment, decrement, advance, distance. In a simple case (like ours) only equal, increment and dereference will be required. Since these methods are used to implement the iterator interface, we place them in the privat section, and use their class (boost :: iterator_core_access) to be declared friend.

 template<typename ValueType> class OwnIteratorBB: public boost::iterator_facade< OwnIteratorBB<ValueType>, ValueType, boost::single_pass_traversal_tag > { friend class OwnContainerBBI; friend class boost::iterator_core_access; private: OwnIteratorBB(ValueType* p); public: OwnIteratorBB(const OwnIteratorBB& it); private: bool equal(OwnIteratorBB const& it) const; void increment(); typename OwnIteratorBB::reference dereference() const; ValueType* p; }; 

Conclusion

An iterator can be created and used without a container, and sometimes the container is not needed at all. Iterators can serve as wrappers over other iterators and modify their behavior, for example, output items after one. Or data is stored separately, and a container with some keys or field values ​​is stored separately. And it is possible to organize an iterator that will be traversed over all the geels, but only return those that correspond to some condition based on the values ​​of the second container. More ideas can be found in the article Underrated iterators written by k06a .

For simple iterators, the use of boost :: iterator_facade is not very relevant, but for more complex ones it can reduce the amount of code, of course, if the boost library is already in use, there is no sense in pulling it just for the sake of iterator_facade.

Links

1. Description Iterator library at cppreference, com .
2. Description of boost :: iterator_facade
3. A repository with an example on github . The project uses Qt5 (for tests), since boost is used, then you need to declare the BOOST environment variable with the directory path with boost.