Не часто возникает необходимость создать свой итератор и хотелось бы иметь под рукой небольшой 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::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. Сам по себе этот класс не реализует никаких методов, но объявляет необходимые типы, которые используются в стандартных алгоритмах.

std::iterator

Как он определе в g++ 4.9

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

Реализация методов OwnIterator

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

Реализация методов OwnIteratorBB

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.

Делаем свой итератор