Не часто возникает необходимость создать свой итератор и хотелось бы иметь под рукой небольшой HowTo. В этой заметка хочу рассказать как создать простейший итератор, который можно использовать в стандартных алгоритмах типа std::copy, std::find. Какие методы и определения типов нужны в классе контейнере, чтобы его можно было обходить в циклах for из c++11 и BOOST_FOREACH.

Контейнер

В классе контейнере необходимо определить типы iterator и const_iterator (типы нужны во-первых для удобства, а во-вторых без них не будет работать обход при помощи BOOST_FOREACH), а также методы begin и end (тут в зависимости от требований, можно добавить только константные методы возвращающие const_iterator):
Для примера возьмем контейнер хранящий массив целых чисел.

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; }; 

OwnContainer::OwnContainer(std::initializer_list<int> values) :     size(values.size()),     data(new int[size]) {     std::copy(values.begin(), values.end(), data.get()); }  OwnContainer::iterator OwnContainer::begin() {     return iterator(data.get()); }  OwnContainer::iterator OwnContainer::end() {     return iterator(data.get() + size); }  OwnContainer::const_iterator OwnContainer::begin() const {     return const_iterator(data.get()); }  OwnContainer::const_iterator OwnContainer::end() const {     return const_iterator(data.get() + size); } 

Естественно, ничто не мешает определить iterator и const_iterator как псевдонимы одного и того же типа.

Итератор

Итератор следует наследовать от класса std::iterator. Сам по себе этот класс не реализует никаких методов, но объявляет необходимые типы, которые используются в стандартных алгоритмах.

  template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,            typename _Pointer = _Tp*, typename _Reference = _Tp&>     struct iterator     {       /// One of the @link iterator_tags tag types@endlink.       typedef _Category  iterator_category;       /// The type "pointed to" by the iterator.       typedef _Tp        value_type;       /// Distance between iterators is represented as this type.       typedef _Distance  difference_type;       /// This type represents a pointer-to-value_type.       typedef _Pointer   pointer;       /// This type represents a reference-to-value_type.       typedef _Reference reference;     }; 

Это шаблонный класс, первый параметр шаблона — тип итератора, так как собираемся использовать со стандартной библиотекой, то тип выбирается из следующих типов: input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, random_access_iterator_tag. Второй параметр тип значения которое хранится и возвращается операторами * и ->, теретий параметр — тип который может описывать растояние между итераторами, четвртый шаблонный параметр — тип указателя на значение, пятый — тип ссылки на значения. Обязательными являются первые два параметра.

Самый просто итератор — это InputIterator (input_iterator_tag), он должен поддерживать префиксную форму инкремента, оператор !=, оператор* и оператор -> (его реализовывать не буду, так как в примере итератор используется для типа int, и в этом случае operator-> бессмысленен). Помимо этого понадобится конструктор и конструктор копирования. В примере не предполагается создание итератора кроме, как методами begin и end класса контейнера, поэтому конструктор итератора будет приватным, а класс контейнера объявлен как дружественный. И добавим оператор ==, во-первых хорошая практика добавлять поддержку != и == вместе, а во-вторых без этого не будет работать BOOST_FOREACH.

const_iterator не сильно отличается от iterator, поэтому объявим iterator как шаблонный класс с одним параметром — тип возвращаемого значения для операторов * и ->.

В конструктор будем передавать указатель на элемент массива хранящийся в 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; }; 

template<typename ValueType> OwnIterator<ValueType>::OwnIterator(ValueType *p) :     p(p) {  }  template<typename ValueType> OwnIterator<ValueType>::OwnIterator(const OwnIterator& it) :     p(it.p) {  }  template<typename ValueType> bool OwnIterator<ValueType>::operator!=(OwnIterator const& other) const {     return p != other.p; }  template<typename ValueType> bool OwnIterator<ValueType>::operator==(OwnIterator const& other) const {     return p == other.p; }  template<typename ValueType> typename OwnIterator<ValueType>::reference OwnIterator<ValueType>::operator*() const {     return *p; }  template<typename ValueType> OwnIterator<ValueType> &OwnIterator<ValueType>::operator++() {     ++p;     return *this; } 

На этом можно было бы и остановиться, но в библиотеке boost есть базовый класс для создания итераторов, и о нем то же хочу сказать пару слов.

Итератор унаследованный от boost::iterator_facade

Контейнер отличается только типами на которые ссылаются iterator и 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; }; 

OwnContainerBBI::OwnContainerBBI(std::initializer_list<int> values) :     size(values.size()),     data(new int[size]) {     std::copy(values.begin(), values.end(), data.get()); }  OwnContainerBBI::iterator OwnContainerBBI::begin() {     return iterator(data.get()); }  OwnContainerBBI::iterator OwnContainerBBI::end() {     return iterator(data.get() + size); }  OwnContainerBBI::const_iterator OwnContainerBBI::begin() const {     return const_iterator(data.get()); }  OwnContainerBBI::const_iterator OwnContainerBBI::end() const {     return const_iterator(data.get() + size); } 

Итератор наследуется от шаблонного типа boost::iterator_facade. Это шаблонный класс, первый параметр — тип наследника, второй тип значения, третий тип итератора. В качестве типа итератора может выступать тип используемый в std::iterator, так и специфичные для boost (в описании такой вариант обозначен как old-style), я возьму тот же тип, что и для std::iterator. boost::iterator_facade реализует необходимые методы: operator*, operator++, operator-> и т.д. Но их реализация базируется на вспомогательных методах, которые нужно реализовать в нашем итераторе, а именно dereference, equal, increment, decrement, advance, distance. В простом случе (как наш) потребуются только equal, increment и dereference. Так как эти методы используются для релизации интерфейса итератора, то разместим их в секции privat, а класс их использующий (boost::iterator_core_access) объявим другом.

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; }; 

template<typename ValueType> OwnIteratorBB<ValueType>::OwnIteratorBB(ValueType *p) :     p(p) {  }  template<typename ValueType> OwnIteratorBB<ValueType>::OwnIteratorBB(const OwnIteratorBB &it) :     p(it.p) {  }  template<typename ValueType> bool OwnIteratorBB<ValueType>::equal(const OwnIteratorBB &it) const {     return p == it.p; }  template<typename ValueType> void OwnIteratorBB<ValueType>::increment() {     ++p; }  template<typename ValueType> typename OwnIteratorBB<ValueType>::reference OwnIteratorBB<ValueType>::dereference() const {     return *p; } 

Заключение

Итератор можно создать и использовать без контейнера, а иногда контейнер не нужен вовсе. Итераторы могут служить обертками над другими итераторами и модифицировать их поведение, например выдавать элементы через один. Или отдельно хранятся данные, а отдельно контейнер с некоторыми ключами или значениями полей. И можно организовать итератор, который будет проходится по всем желементам, но возвращать только те что соответвуют некотрому условию основанному на значениях второго контейнера. Еще идеи можно почерпнуть в статье Недооценённые итераторы написанной k06a.

Для простых итераторов использование boost::iterator_facade не очень актуально, но для более сложных позволяет сократить количество кода, естественно, если библиотека boost уже используется, тянуть её только ради iterator_facade смысла нет.

Ссылки

1. Описание Iterator library на cppreference,com.
2. Описание boost::iterator_facade
3. Репозиторий c примером на github. Проект использует Qt5 (для тестов), так как используется boost, то нужно объявить переменную окружения BOOST с путем к каталогу с boost.

ссылка на оригинал статьи http://habrahabr.ru/post/265491/