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

Есть класс, хранящий позицию элемента некоторой последовательности чисел:
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; // Расстояние до другой позиции. };
Как при помощи этого класса написать итератор, так чтобы его можно было использовать в алгоритмах стандартной библиотеки?

Ответ

Написание итератора можно слегка упростить при помощи стандартного шаблона класса 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); }
>>> Здесь можно посмотреть весь код полностью <<<