Implement a random access iterator from scratch
The first thing I do when I have to write an iterator is … to try to avoid it as much as possible.
There are multiple reasons; the first is that there are many types of iterators (bidirectional, random access, input, output, …), so it can be confusing to know exactly what one needs to implement.
Then, at least some types of iterators have a broad interface, so you have to implement a lot of functions even if you might be using only a small subset. They use a tagging mechanism, which you are not going to use, but some algorithms might, and it is easy to forget to implement.
Last but not least, most of the interface of an iterator is defined by operators, not named functions. Which means that if something does not compile, error messages tend to be more difficult to understand. And since those error messages might pop up when using an algorithm from the standard library, they are even less clear.
Thus, avoid it at all costs. Wrap the data in a span, or copy it in a container of the standard library, use something that is not really an iterator but good enough, and so on.
For the same reason, I always try to write a specialized container; writing an iterator for it requires a lot of work.
So far, I’ve always managed to avoid writing one.
Until I needed to write one. Once I wrote it, I noticed how much code duplication there was, and how many non-obvious errors orthogonal to the functionality I did.
Before I need to write another iterator, I decided to encapsulate everything I could in some tools I could reuse next time.
Iterator categories
In my case, I wanted a random access iterator 🗄️, which of course has a very broad interface.
Since C++20, with concepts and ranges, there are new iterator categories, the names are almost the same, I still want a random access iterator 🗄️.
From here, I will only reference the new categories, but the techniques do not depend on the iterator categories.
The plan I followed is simple; I first implemented an input iterator 🗄️ (and thus also a input or output iterator 🗄️).
Once I had something, I added the missing functionalities until I had a forward iterator 🗄️.
Then, I added what I needed to get a bidirectional iterator 🗄️.
Finally, I implemented the random access iterator 🗄️.
On top of a random access iterator, one can implement a contiguous iterator 🗄️, but it was not my case.
In these notes, I’m going to use as an example an iterator that points to a container and accesses its elements through an index.
Implementing a random access iterator
The final implementation looks more or less like the following:
#include <cstddef>
class index_iterator {
std::size_t index = 0;
std::vector<int>* data = nullptr;
public:
index_iterator() = default;
explicit index_iterator( std::size_t index_, std::vector<int>* data_ )
: index( index_ )
, data( data_ )
{}
//! API of input_or_output_iterator
using difference_type = std::ptrdiff_t;
int operator*() const {
return data->at(index);
}
index_iterator& operator++() {
++index;
return *this;
}
//void operator++(int);
//! API of input_iterator
using value_type = int;
//! API of forward_iterator
index_iterator operator++( int ) {
auto tmp = *this;
++index;
return tmp;
}
bool operator==( const index_iterator& other ) const = default;
//! API of bidirectional_iterator
index_iterator& operator--() {
--index;
return *this;
}
index_iterator operator--( int ) {
auto tmp = *this;
--*this;
return tmp;
}
//! API of random_access_iterator
auto operator<=>( const index_iterator& other ) const {
return this->index <=> other.index;
}
int operator[]( difference_type n ) const {
return data->at(n);
}
index_iterator& operator+=( difference_type n ) {
index += n;
return *this;
}
index_iterator& operator-=( difference_type n ) {
index -= n;
return *this;
}
friend index_iterator operator+( index_iterator it, difference_type n ) {
it += n;
return it;
}
friend index_iterator operator+( difference_type n, index_iterator it ) {
it += n;
return it;
}
friend index_iterator operator-( index_iterator it, difference_type n ) {
it -= n;
return it;
}
friend difference_type operator-( const index_iterator& a, const index_iterator& b ) {
return a.index - b.index;
}
};
static_assert( std::input_or_output_iterator<index_iterator> );
static_assert( std::input_iterator<index_iterator> );
static_assert( std::forward_iterator<index_iterator> );
static_assert( std::bidirectional_iterator<index_iterator> );
static_assert( std::random_access_iterator<index_iterator> );It is a lot of code, nearly 80 lines, without any tests except for the five static_assert. Granted, I wrote some comments, but considering that in 100 lines it is possible to get a decent test suite from scratch it feels like a lot, especially considering that index_iterator is just a proxy which adds no functionality.
And if you look at the implementation, there are a lot of similar functions. At least we could default operator==, and there is no need to write operator!=. Once you have implemented operator()`, there is little reason why the compiler could not write a defaulted `operator(int). And the same holds for operator--, operator+=, operator -= and a symmetric operator+.
It would be nice to be able to write:
index_iterator& operator++() {
++index;
return *this;
}
index_iterator operator++( int ) = default;or just
index_iterator& operator++() {
++index;
return *this;
}and have it functionally equivalent to
index_iterator& operator++() {
++index;
return *this;
}
index_iterator operator++( int ) {
auto tmp = *this;
++(*this);
return tmp;
}Similarly, it would be great to be able to write something like
index_iterator& operator+=( difference_type n ) {
index += n;
return *this;
}
friend index_iterator operator+( index_iterator it, difference_type n ) = default;and have it behave like
index_iterator& operator+=( difference_type n ) {
index += n;
return *this;
}
friend index_iterator operator+( index_iterator it, difference_type n ) {
it += n;
return it;
}
friend index_iterator operator+( difference_type n, index_iterator it ) {
it += n;
return it;
}As a bonus, the signatures would be consistent (const, constexpr, noexcept, return by reference/value, …) and as efficient as possible (pass by value, reference, …).
| Note 📝 | Many functions can be made constexpr and noexcept. For brevity and readability, I marked no function as such. |
Since those functions would be generated by the compiler, the compiler has less code to analyze and optimize, possibly improving both compilation times and the quality of the generated code.
I suppose that since most classes do not need all those functions, there is little motivation to add other special rules to the language.
Nevertheless, I decided I needed to encapsulate as much functionality as possible, ideally without macros.
Implementing a random access iterator with CRTP
The first approach is to use the CRTP pattern; encapsulate in a base class functionalities that depend on a functionality defined in a derived class.
The helper structure looks like the following:
#include <cstddef>
//! part of the API of forward_iterator
//! relies on operator++ for defining operator++(int)
template <class I>
struct forward_iterator_api {
I operator++(int) {
auto tmp = *static_cast<I*>(this);
++(*static_cast<I*>(this));
return tmp;
}
};
//! part of the API of bidirectional_iterator
//! relies on operator-- for defining operator--(int)
template <class I>
struct bidirectional_iterator_api {
I operator--(int) {
auto tmp = *static_cast<I*>(this);
--(*static_cast<I*>(this));
return tmp;
}
};
//! part of the API of random_access_iterator
//! relies on operator+= for defining symmetrical operator+
//! relies on operator-= for defining operator-
template <class I>
struct random_access_iterator_api {
friend I operator+(I it, std::ptrdiff_t n) {
it += n;
return it;
}
friend I operator+(std::ptrdiff_t n, I it) {
it += n;
return it;
}
friend I operator-(I it, std::ptrdiff_t n) {
it -= n;
return it;
}
};And the usage looks like
class index_iterator
: public forward_iterator_api<index_iterator>
, public bidirectional_iterator_api<index_iterator>
, random_access_iterator_api<index_iterator>
{
std::size_t index = 0;
std::vector<int>* data = nullptr;
public:
index_iterator() = default;
explicit index_iterator( std::size_t index_, std::vector<int>* data_ )
: index( index_ )
, data( data_ )
{}
//! API of input_or_output_iterator
using difference_type = std::ptrdiff_t;
int operator*() const {
return data->at(index);
}
index_iterator& operator++() {
++index;
return *this;
}
//void operator++(int);
//! API of input_iterator
using value_type = int;
//! API of forward_iterator
using forward_iterator_api<index_iterator>::operator++;
bool operator==(const index_iterator& other) const {
return this->index == other.index and this->data == other.data;
}
//! API of bidirectional_iterator
index_iterator& operator--() {
--index;
return *this;
}
using bidirectional_iterator_api<index_iterator>::operator--;
//! API of random_access_iterator
auto operator<=>( const index_iterator& other ) const {
return this->index <=> other.index;
}
int operator[]( difference_type n ) const {
return data->at(n);
}
index_iterator& operator+=( difference_type n ) {
index += n;
return *this;
}
index_iterator& operator-=( difference_type n ) {
index -= n;
return *this;
}
friend difference_type operator-( const index_iterator& a, const index_iterator& b ) {
return a.index - b.index;
}
};
static_assert( std::input_or_output_iterator<index_iterator> );
static_assert( std::input_iterator<index_iterator> );
static_assert( std::forward_iterator<index_iterator> );
static_assert( std::bidirectional_iterator<index_iterator> );
static_assert( std::random_access_iterator<index_iterator> );The class is already 30 lines shorter, but I did not get there without scratching my head a couple of times.
The first error I had was caused by
constexpr bool operator==(const index_iterator& other) const = default;Since index_iterator now has a base class, no matter that it is stateless, operator== can still be defaulted, but it will do something different. The error message caused by static_assert( std::input_or_output_iterator<index_iterator> ) was unclear, but if you remove the static_assert and try to use the operator, you’ll get a much better error message:
[…] is implicitly deleted because the default definition would be ill-formed
The issue is fixed by writing operator== explicitly; at least you do not have to write operator!= since C++20.
All things considered, it is a small price to pay, although it would be better if it would Just Work™ as before.
The second error was caused by the fact that operator++ and operator++(int) are overloads.
Thus, the overload in the derived class hides the one in the base class. Again, the error message from static_assert was rather unhelpful; writing a minimal test gave a much better error message.
The issue is fixed by bringing the overload in scope again:
using forward_iterator_api<index_iterator>::operator++;
using bidirectional_iterator_api<index_iterator>::operator--;Unfortunately, this has to be done every time.
If it sounds unacceptable, the only workaround is to define in the leaf class another function for advancing, and implement both operator++ and operator++(int) in the base class; something like:
//! part of the API of forward_iterator
//! relies on advance for defining operator++() and operator++(int)
template <class I>
struct forward_iterator_api {
I& operator++() {
return advance();
}
I operator++(int) {
auto tmp = *static_cast<I*>(this);
advance();
return tmp;
}
};The disadvantage is that now there is an additional member function called advance.
Last but not least, I derived with private visibility; in my first iteration, I wrote:
class index_iterator
: forward_iterator_api<index_iterator>
, bidirectional_iterator_api<index_iterator>
, random_access_iterator_api<index_iterator>
{
// ...
}Interestingly, none of the static_assert failed, but trying to actually use, for example, operator++(int), would lead to a compilation error, as static_cast<I*>(this) does not compile, as the hierarchy is not public.
The possible solutions are to add:
friend forward_iterator_api<index_iterator>;
friend bidirectional_iterator_api<index_iterator>;inside index_iterator, or derive with public visibility from forward_iterator_api and bidirectional_iterator_api.
Note that deriving with private visibility from random_access_iterator_api is fine, because none of the functions in random_access_iterator_api need to cast to the derived type, and rely only on the public API.
Reduce the amount of code even further
If you look at index_iterator, you’ll still see different functions that are extremely similar and in part depend on each other. For example, operator[] and operator* must return the same type.
It is not sufficient for the return types to be "similar" or one convertible to another. For example int operator[]( difference_type n ) const and const int& operator*() const would trigger an error in static_assert( std::random_access_iterator<index_iterator> );.
Also, operator+ and operator- are similar; it is the same operation with a negated number!
A more heavy-lifting random_access_iterator_api would look like the following:
//! part of the API of random_access_iterator
//! relies on operator+= for defining symmetrical operator+, operator-=, operator-
//!
//! Ensure that I defines difference_type as std::ptrdiff_t for consistency!
template <class I>
struct random_access_iterator_api {
friend I operator+(I it, std::ptrdiff_t n) {
it += n;
return it;
}
friend I operator+(std::ptrdiff_t n, I it) {
it += n;
return it;
}
I& operator-=( std::ptrdiff_t n ) {
return *this += ( -n );
}
friend I operator-( I it, std::ptrdiff_t n ){
it += ( -n );
return it;
}
};To cover operator[] too, with the assumption that copying and iterating is cheap (which for a random access iterator should be the case), random_access_iterator_api could look like the following
//! part of the API of random_access_iterator
//! relies on operator+= for defining symmetrical operator+, operator-=, operator-
//! relies on operator* and operator+= for defining operator[]
//!
//! Ensure that I defines difference_type as std::ptrdiff_t for consistency!
template <class I>
struct random_access_iterator_api {
friend I operator+(I it, std::ptrdiff_t n) {
it += n;
return it;
}
friend I operator+(std::ptrdiff_t n, I it) {
it += n;
return it;
}
I& operator-=( std::ptrdiff_t n ) {
return *this += ( -n );
}
friend I operator-( I it, std::ptrdiff_t n ){
it += ( -n );
return it;
}
decltype(auto) operator[](std::ptrdiff_t n) const {
I copy = *static_cast<const I*>(this);
copy += n;
return *copy;
}
decltype(auto) operator[](std::ptrdiff_t n) {
I copy = *static_cast<const I*>(this);
copy += n;
return *copy;
}
};The usage of the last helper would look like the following (note that in this case it is important to derive with public visibility from random_access_iterator_api):
class index_iterator
: public forward_iterator_api<index_iterator>
, public bidirectional_iterator_api<index_iterator>
, public random_access_iterator_api<index_iterator>
{
std::size_t index = 0;
std::vector<int>* data = nullptr;
public:
index_iterator() = default;
explicit index_iterator( std::size_t index_, std::vector<int>* data_ )
: index( index_ )
, data( data_ )
{}
//! API of input_or_output_iterator
using difference_type = std::ptrdiff_t;
int operator*() const {
return data->at(index);
}
index_iterator& operator++() {
++index;
return *this;
}
//void operator++(int);
//! API of input_iterator
using value_type = int;
//! API of forward_iterator
using forward_iterator_api<index_iterator>::operator++;
bool operator==(const index_iterator& other) const {
return this->index == other.index and this->data == other.data;
}
//! API of bidirectional_iterator
index_iterator& operator--() {
--index;
return *this;
}
using bidirectional_iterator_api<index_iterator>::operator--;
//! API of random_access_iterator
auto operator<=>( const index_iterator& other ) const {
return this->index <=> other.index;
}
index_iterator& operator+=( difference_type n ) {
index += n;
return *this;
}
friend difference_type operator-( const index_iterator& a, const index_iterator& b ) {
return a.index - b.index;
}
};
static_assert( std::input_or_output_iterator<index_iterator> );
static_assert( std::input_iterator<index_iterator> );
static_assert( std::forward_iterator<index_iterator> );
static_assert( std::bidirectional_iterator<index_iterator> );
static_assert( std::random_access_iterator<index_iterator> );This more or less halves the amount of code "inside" index_iterator compared to the original implementation.
Implementing a random access iterator with deducing this
Since C++23, it is possible to deduce this 🗄️.
It should give faster compiler times, better error messages, fewer casts, less code generated by the compiler, and less code to write. There seems to be no drawbacks.
So this is how the code could look since C++23:
#include <cstddef>
//! part of the API of forward_iterator
//! relies on operator++ for defining operator++(int)
struct forward_iterator_api {
template <typename Self>
auto operator++(this Self&& self, int) {
auto tmp = self;
++self;
return tmp;
}
};
//! part of the API of bidirectional_iterator
//! relies on operator-- for defining operator--(int)
struct bidirectional_iterator_api {
template <typename Self>
auto operator--(this Self&& self, int) {
auto tmp = self;
--self;
return tmp;
}
};
//! part of the API of random_access_iterator
//! relies on operator+= for defining one of the two operator+
//! relies on operator-= for defining operator-
struct random_access_iterator_api {
template <typename Self>
auto operator+(this Self self, std::ptrdiff_t n) {
self += n;
return self;
}
template <typename Self>
auto operator-(this Self self, std::ptrdiff_t n) {
self -= n;
return self;
}
};This is how it should be used:
class index_iterator
: public forward_iterator_api
, public bidirectional_iterator_api
, public random_access_iterator_api
{
std::size_t index = 0;
std::vector<int>* data = nullptr;
public:
index_iterator() = default;
explicit index_iterator( std::size_t index_, std::vector<int>* data_ )
: index( index_ )
, data( data_ )
{}
//! API of input_or_output_iterator
using difference_type = std::ptrdiff_t;
int operator*() const {
return data->at(index);
}
index_iterator& operator++() {
++index;
return *this;
}
//void operator++(int);
//! API of input_iterator
using value_type = int;
//! API of forward_iterator
using forward_iterator_api::operator++;
bool operator==(const index_iterator& other) const {
return this->index == other.index and this->data == other.data;
}
//! API of bidirectional_iterator
index_iterator& operator--() {
--index;
return *this;
}
using bidirectional_iterator_api::operator--;
//! API of random_access_iterator
auto operator<=>( const index_iterator& other ) const {
return this->index <=> other.index;
}
int operator[]( difference_type n ) const {
return data->at(n);
}
index_iterator& operator+=( difference_type n ) {
index += n;
return *this;
}
index_iterator& operator-=( difference_type n ) {
index -= n;
return *this;
}
friend difference_type operator-( const index_iterator& a, const index_iterator& b ) {
return a.index - b.index;
}
friend index_iterator operator+( difference_type n, index_iterator it ) {
it += n;
return it;
}
};
static_assert( std::input_or_output_iterator<index_iterator> );
static_assert( std::input_iterator<index_iterator> );
static_assert( std::forward_iterator<index_iterator> );
static_assert( std::bidirectional_iterator<index_iterator> );
static_assert( std::random_access_iterator<index_iterator> );The first error I made was writing:
struct random_access_iterator_api {
template <typename Self>
auto operator+(this Self&& self, std::ptrdiff_t n) {
self += n;
return self;
}
template <typename Self>
auto operator-(this Self&& self, std::ptrdiff_t n) {
self -= n;
return self;
}
};instead of
struct random_access_iterator_api {
template <typename Self>
auto operator+(this Self self, std::ptrdiff_t n) {
self += n;
return self;
}
template <typename Self>
auto operator-(this Self self, std::ptrdiff_t n) {
self -= n;
return self;
}
};In this case, both Clang and GCC provided error messages with the static_assert that were good enough to understand what the actual error was.
My second error was to still derive with private visibility from random_access_iterator_api. Since, contrary to CRTP, random_access_iterator implements member functions, they are affected by the visibility. Thus either add
using random_access_iterator_api::operator-;
using random_access_iterator_api::operator+;inside the index_iterator class, or derive with public visibility. Note that, contrary to CRTP, it is possible to derive with private visibility from forward_iterator_api and bidirectional_iterator_api, and without making the classes friends, as there are no casts anymore, and you already need
using forward_iterator_api::operator++;
using bidirectional_iterator_api::operator--;or the provided operators are hidden by the other overload.
A heterogeneous operator+ is best implemented as a set of free functions (eventually friend) to ensure symmetry. It is normally expected that both a+b and b+a, with b and a having different types, work the same way.
This is not possible to implement with a member function, and thus, for this operation, deducing this falls short. It can provide only one of the two functions. For operator-, this is not an issue, as subtraction is normally not a symmetric operation.
Thus, the code for the helper classes got simpler, but I had to replace friend functions with member functions. The class index_iterator also got slightly simpler; there are fewer templates, but the amount of code slightly increased, as one needs to implement friend index_iterator operator+( difference_type n, index_iterator it ).
Implementing a random access iterator with tags
Since "deducing this" does not work with free functions, I tried to use a tagging mechanism for adding the necessary free functions.
template <typename T>
struct make_random_access_iterable : public std::false_type {};
template <typename T>
concept make_random_access_iterator = make_random_access_iterable<T>::value;
template <typename I> requires make_random_access_iterator<I>
constexpr I operator+(I i, std::ptrdiff_t n) {
i += n;
return i;
}
template <typename I> requires make_random_access_iterator<I>
constexpr I operator+(std::ptrdiff_t n, I i) {
i += n;
return i;
}
template <typename I> requires make_random_access_iterator<I>
constexpr I operator-(I i, std::ptrdiff_t n) {
i -= n;
return i;
}to opt-in, write
template <>
struct make_random_access_iterable<index_iterator> : public std::true_type{};after declaring index_iterator.
It is also possible to implement operator++ and others as free functions, but I do not see any real advantage over using "deducing this". Actually, I’m not convinced it offers a particular advantage over CRTP, except that it does require fewer casts.
Tests
An iterator looks like a simple type of object. Compare with == and !=; iterate with ++, what could go wrong?
The function signatures are easy to get wrong, it is easy to tag things incorrectly, it is easy to implement one of the equivalent functions inconsistently, …
And since all those function calls are hidden, it is easy to overlook them when something does not work.
Granted, many things are covered by the static_asserts (all functions are present, the signatures are more or less correct), but there are still many things that can go wrong.
This is a minimal test suite; it is incomplete, but it already covers most functions to see if an iterator implemented with the helpers seems to behave correctly:
class dummyiterator /* */ {
std::vector<int>* data = nullptr;
std::size_t index = 0;
public:
dummyiterator() = default;
dummyiterator( std::vector<int>* data_, std::size_t index_ )
: data( data_ )
, index( index_ )
{}
// ...
};
struct dummycontainer {
std::vector<int> v = { 1, 2, 3, 4, 5 };
auto begin()
{
return dummyiterator( &v, 0 );
}
auto end()
{
return dummyiterator( &v, v.size() );
}
int size() const
{
return static_cast<int>( v.size() );
}
};
TEST_CASE( "dummyiterator behaves like a forward iterator" ) {
dummycontainer data;
SECTION( "operator* dereferences content" ) {
auto it = data.begin();
for ( int i = 0; i != data.size(); ++i )
{
REQUIRE( *it == i + i );
++it;
}
}
SECTION( "operator++(int) returns current status" ) {
auto it = data.begin();
auto old = it++;
REQUIRE( old == data.begin() );
auto old2 = it++;
REQUIRE( old2 == ++old );
}
SECTION( "for-range loop iterates on all elements" ) {
std::vector<int> copy;
copy.reserve( data.size() );
for ( const auto& i : data )
{
copy.push_back( i );
}
REQUIRE( data.v == copy );
}
}
TEST_CASE( "dummyiterator behaves like a bidirectional iterator" ) {
dummycontainer data;
auto it = data.begin();
SECTION( "operator--() navigates backward" )
{
++it;
REQUIRE( it != data.begin() );
--it;
REQUIRE( it == data.begin() );
}
SECTION( "operator--(int) returns current status" )
{
++it;
auto old = it--;
REQUIRE( old == ++data.begin() );
auto old2 = it--;
REQUIRE( old2 == data.begin() );
}
}
TEST_CASE( "dummyiterator behaves like a random access iterator" ) {
dummycontainer data;
SECTION( "operator+ is like repated operator++" )
{
auto it = data.begin();
for ( int i = 0; i != data.size(); ++i )
{
REQUIRE( data.begin() + i == it );
++it;
}
}
SECTION( "operator+ is symmetric" )
{
for ( int i = 0; i != data.size(); ++i )
{
REQUIRE( data.begin() + i == i + data.begin() );
}
}
SECTION( "operator- is like repeated operator--" )
{
auto it = data.end();
for ( int i = 0; i != data.size(); ++i )
{
REQUIRE( data.end() - i == it );
--it;
}
}
SECTION( "operator+=" ) {}
SECTION( "operator-=" ) {}
SECTION( "operator[] dereferences" )
{
auto it = data.begin();
for ( int i = 0; i != data.size(); ++i )
{
REQUIRE( it[i] == i + 1 );
}
}
}Conclusion
Iterators are not fun to write; there is a lot of code bloat.
With some tooling, it is possible to reduce the bloat considerably, without even resorting to macros.
I think the best approach is to use "deducing this" for forward_iterator_api and bidirectional_iterator_api.
For random_access_iterator_api, because of operator+, it is not possible to implement both overloads as member functions. Thus, for that case, using CRTP with friend functions is a more sensible approach, like the tagging mechanism.
Given a class that already uses forward_iterator_api and bidirectional_iterator_api, using CRTP makes the code look more consistent. I did not verify if, between CRTP and the tagging mechanism, there is less generated code, or if compilation times differ.
My current final implementation looks like the following.
The helper classes:
#include <cstddef>
//! part of the API of forward_iterator
//! relies on operator++ for defining operator++(int)
struct forward_iterator_api {
template <typename Self>
auto operator++(this Self&& self, int) {
auto tmp = self;
++self;
return tmp;
}
};
//! part of the API of bidirectional_iterator
//! relies on operator-- for defining operator--(int)
struct bidirectional_iterator_api {
template <typename Self>
auto operator--(this Self&& self, int) {
auto tmp = self;
--self;
return tmp;
}
};
//! part of the API of random_access_iterator
//! relies on operator+= for defining symmetrical operator+, operator-=, operator-
//! relies on operator* and operator+= for defining operator[]
//!
//! Ensure that I defines difference_type as std::ptrdiff_t for consistency!
template <class I>
struct random_access_iterator_api {
friend I operator+(I it, std::ptrdiff_t n) {
it += n;
return it;
}
friend I operator+(std::ptrdiff_t n, I it) {
it += n;
return it;
}
I& operator-=( std::ptrdiff_t n ) {
return *this += ( -n );
}
friend I operator-( I it, std::ptrdiff_t n ){
it += ( -n );
return it;
}
template <typename Self>
decltype(auto) operator[](this Self copy, std::ptrdiff_t n) {
copy += n;
return *copy;
}
};And how they can be used
class index_iterator
: public forward_iterator_api
, public bidirectional_iterator_api
, public random_access_iterator_api<index_iterator>
{
std::size_t index = 0;
std::vector<int>* data = nullptr;
public:
index_iterator() = default;
explicit index_iterator( std::size_t index_, std::vector<int>* data_ )
: index( index_ )
, data( data_ )
{}
//! API of input_or_output_iterator
using difference_type = std::ptrdiff_t;
int operator*() const {
return data->at(index);
}
index_iterator& operator++() {
++index;
return *this;
}
//void operator++(int);
//! API of input_iterator
using value_type = int;
//! API of forward_iterator
using forward_iterator_api::operator++;
bool operator==(const index_iterator& other) const {
return this->index == other.index and this->data == other.data;
}
//! API of bidirectional_iterator
index_iterator& operator--() {
--index;
return *this;
}
using bidirectional_iterator_api::operator--;
//! API of random_access_iterator
auto operator<=>( const index_iterator& other ) const {
return this->index <=> other.index;
}
index_iterator& operator+=( difference_type n ) {
index += n;
return *this;
}
friend difference_type operator-( const index_iterator& a, const index_iterator& b ) {
return a.index - b.index;
}
};
static_assert( std::input_or_output_iterator<index_iterator> );
static_assert( std::input_iterator<index_iterator> );
static_assert( std::forward_iterator<index_iterator> );
static_assert( std::bidirectional_iterator<index_iterator> );
static_assert( std::random_access_iterator<index_iterator> );
If you have questions, comments, or found typos, the notes are not clear, or there are some errors; then just contact me.