Как написать свой RandomAccess итератор?

#cpp

Есть класс, хранящий позицию элемента некоторой последовательности чисел:

struct Position {
    int& dereference() const; // Получение текущего элемента.
    bool equal(const Position& other) const; // Проверка на равенство.
    void increment(); // Перемещение вперед.
    void decrement(); // Перемещение назад.
    void advance(std::ptrdiff_t n);  // Перемещение на "n" элементов.
    std::ptrdiff_t distance_to(const Position& other) const; // Расстояние до другой
позиции.
};


Как при помощи этого класса написать итератор, так чтобы его можно было использовать
в алгоритмах стандартной библиотеки?
    

Ответы

Ответ 1

Написание итератора можно слегка упростить при помощи стандартного шаблона класса
std::iterator, куда надо передать категорию итератора и тип элемента последовательности.

В зависимости от выбранной категории итератора, те или иные операции можно не реализовывать.

struct iterator : std::iterator {
    // Вложенный объект Position, и конструктор для него.
    Position pos;
    iterator(Position pos) : pos(pos) {}

    // Операции, необходимые для всех категорий итераторов.
    iterator() = default;
    iterator(const iterator&) = default;
    iterator& operator=(const iterator&) = default;
    ~iterator() = default;
    reference operator*() const { return pos.dereference(); }
    iterator& operator++() { pos.increment(); return *this; }
    iterator operator++(int) { auto old = *this; ++(*this); return old; }

    // Операции, необходимые для InputIterator.
    pointer operator->() const;

    // Операции, необходимые для BidirectionalIterator.
    iterator& operator--() { pos.decrement(); return *this; }
    iterator operator--(int) { auto old = *this; --(*this); return old; }

    // Операции, необходимые для RandomAccessIterator.
    reference operator[](difference_type n) const { auto tmp = *this; tmp += n; return
*tmp; }
    iterator& operator+=(difference_type n) { pos.advance(n); return *this; }
    iterator& operator-=(difference_type n) { return *this += -n; }
};

// Операции, необходимые для всех категорий итераторов.
void swap(iterator& a, iterator& b) { std::swap(a.pos, b.pos); }

// Операции, необходимые для InputIterator.
bool operator==(const iterator& lhs, const iterator& rhs) { return lhs.pos.equal(rhs.pos); }
bool operator!=(const iterator& lhs, const iterator& rhs) { return !(lhs == rhs); }

// Операции, необходимые для RandomAccessIterator.
bool operator<(const iterator& lhs, const iterator& rhs) { return lhs.pos.distance_to(rhs.pos)
> 0; }
bool operator>(const iterator& lhs, const iterator& rhs) { return rhs < lhs; }
bool operator<=(const iterator& lhs, const iterator& rhs) { return !(rhs > lhs); }
bool operator>=(const iterator& lhs, const iterator& rhs) { return !(lhs < rhs); }
iterator operator+(iterator it, iterator::difference_type n) { it += n; return it; }
iterator operator+(iterator::difference_type n, iterator it) { return it + n; }
iterator operator-(iterator it, iterator::difference_type n) { it -= n; return it; }
iterator::difference_type operator-(const iterator& lhs, const iterator& rhs) { return
rhs.pos.distance_to(lhs.pos); }


>>> Здесь можно посмотреть весь код полностью <<<


Ответ 2

Вместо того чтобы руками перегружать все операторы, можно воспользоваться библиотекой
Boost.Iterator, а именно шаблоном boost::iterator_facade.

Как и std::iterator, шаблон boost::iterator_facade - это базовый класс, однако в
нем есть не только определения типов, но также и все перегруженные операторы необходимые
для итератора.

Класс-наследник должен определить минимальный набор операций, зависящий от его категории.
Список этих операций - такой же как и у класса Position, который приведен в вопросе.

Пример использования выглядит следующим образом:
(Этот итератор проверяет при сравнении что он принадлежит к одному и тому же массиву)

#include 

class iterator : public boost::iterator_facade<
                            iterator, // Тип наследника iterator_facade
                            int, // Тип элемента
                            std::random_access_iterator_tag // Категория итератора
                        >
{
    int* base;
    int i;
public:
    iterator(int* b, int i) : base(b), i(i) {}

    // Операции, необходимые для всех категорий итераторов.
    reference dereference() const { return base[i]; }
    bool equal(const iterator& other) const {
        assert(base == other.base);
        return i == other.i;
    }
    void increment() { ++i; }

    // Операции, необходимые для BidirectionalIterator.
    void decrement() { --i; }

    // Операции, необходимые для RandomAccessIterator.
    void advance(std::ptrdiff_t n) { i += n; }
    std::ptrdiff_t distance_to(const iterator& other) const {
        assert(base == other.base);
        return other.i - i;
    }
};