Since C++20, a random-access iterator can be implemented in the following way.
Interface
template <typename T, typename Ptr>
struct Iterator
{
using value_type = T;
using pointer = Ptr;
using elt_pointer. = typename std::pointer_traits<Ptr>::rebind</* internal type */>;
using reference = std::iter_reference_t<Ptr>;
using difference_type = std::ptrdiff_t;
using iterator_category = std::random_access_iterator_tag;
Iterator();
explicit Iterator(elt_pointer);
template <std::convertible_to<Ptr> PtrR>
Iterator(const Iterator<PtrR>&);
reference operator*() const;
pointer operator->() const;
reference operator[](difference_type) const;
Iterator& operator++();
Iterator operator++(int);
Iterator& operator--();
Iterator operator--(int);
Iterator& operator+=(difference_type);
Iterator& operator-=(difference_type);
};
template <typename T, typename PtrL, typename PtrR>
bool operator==(const Iterator<T, PtrL>&, const Iterator<T, PtrR>&);
template <typename T, typename PtrL, typename PtrR>
auto operator<=>(const Iterator<T, PtrL>&, const Iterator<T, PtrR>&);
template <typename T, typename Ptr>
Iterator<T, Ptr> operator+(const Iterator<T, Ptr>&, Iterator<T, Ptr>::difference_type);
template <typename T, typename Ptr>
Iterator<T, Ptr> operator+(Iterator<T, Ptr>::difference_type, const Iterator<T, Ptr>&);
template <typename T, typename Ptr>
Iterator<T, Ptr> operator-(const Iterator<T, Ptr>&, Iterator<T, Ptr>::difference_type);
template <typename T, typename PtrL, typename PtrR>
auto operator-(const Iterator<T, PtrL>&, const Iterator<T, PtrR>&);
Design choices
1. iterator / const-iterator
The first aspect of the iterator concerns the implementation of iterator and const-iterator. Although these can be implemented in two different classes, the approach requires duplication of much of the code, since the only difference between the two interfaces concerns the const-qualification of the pointer and reference types.
A common design is to create a single class that adds a boolean template parameter, which allows to specify whether the iterator should be const-qualified. In this way, the const-qualified version of the pointer and reference types, and possibly other internal types, is selected through a meta-programmaing switch. For simplicity, this can be done with a standard type trait, std::conditional.
The Iterator class takes an alternative of the previous approach, replacing the boolean parameter with a Ptr template parameter. It allows the pointer type to be specified, while the reference type is deduced from the previous one. In this way, the original const-qualification is maintained: if the template parameter Ptr is a pointer to const T, the class will be of type const-iterator; otherwise, the class will be of type iterator.
One vulnerability of this design arises from the possibility of the user specializing the class for a pointer type that is not compatible with T. Indeed, this requirement is only implicitly assumed by the implementation. To make the mandate explicit, it is possible to add a static assertion, which results in a compile-time error if the above condition is violated.
Example:
static_assert(std::is_same_v<T, std::iter_value_t<Ptr>>, "The Ptr element_type must be the same as value_type");
2. Fancy pointers
The technique is also designed to support fancy pointers. Indeed, the template parameter Ptr allows to specify any type that model both NullablePointer and LegacyRandomAccessIterator.
These are the general requirements that the Standard imposes for a type to be called a fancy pointer. However, each iterator may have less strict requirements, covering only supported operations. For example, a double-linked list iterator might require only that the pointer type models LegacyBidirectionalIterator.
To handle fancy pointers properly, the class works through the std::pointer_traits interface and std::iter_* group of aliases. It is important to note that, to truly allow the support of fancy pointers, the implementation must appropriately use certain functions, like pointer_to(), which creates a fancy pointer from the reference to an already-existing object, and std::to_address(), which returns a raw pointer representing the same address as the fancy pointer does.
To define the internal pointer type, which may not be the same as the pointer type, it is rebound through std::pointer_traits. As for whether the original const-qualification can also be propagated to the internal pointer type, this is an implementation choice: if the rebound pointer type is always const-unqualified, instances of the internal pointer are perfectly inter-operable between iterator and const-iterator, but this requires performing some cast operations; otherwise, the const-qualification of the pointer type and internal pointer types is syncronized, but operations between iterator and const-iterator may require to introduce conversions or additional pre-conditions.
3. Lightweight
The iterator is supposed to be a lightweight wrapper around one or more pointers. This is an important aspect to ensure that the use of the iterator, even if a raw pointer would be perfectly interchangeable, does not cause any overhead at run-time. Ideally, the iterator should just be a C-style structure that contains a certain number of pointers and provides a set of member functions and overloaded operators to support all the required operations.
The Iterator class was designed to model TrivialType and StandardLayoutType if the internal pointer types also meet the above requirements. This also requires that, to ensure that the class be trivial even if two constructors have been declared by the user, the default constructor must be marked as default.
4. Conversion constructor
The conversion constructor is the most commonly used approach to allow implicit conversion from iterator to const-iterator. Specifically, the const-iterator class must declare an extended copy constructor that accepts an iterator as an argument. Since the Iterator class may represent both the iterator and const-iterator, the conversion constructor must be declared as a function that takes an instance of the class with a different pointer type.
template <typename PtrR>
Iterator(const Iterator<T, PtrR>&);
This declaration seems robust, but it may leads to subtle bugs. Indeed, it is not possible to determine at compile-time whether a Iterator specialization is convertible to another: if the above is tested via a type trait, such as std::is_convertible, the result will be positive even if the operation is not really possible. This occurs because the type trait verifies only whether a certain expression, which in this case is the implicit construction, is well-formed. To summarize, since the constructor takes unconditionally an instance of the class for any different pointer type, the check will be always successful.
To resolve the issue, it is sufficient to constraint the constructor. In particular, only pointer types that are implicitly convertible to the current pointer type are accepted.
template <std::convertible_to<Ptr> PtrR>
Iterator(const Iterator<T, PtrR>&);
5. Explicit constructor
Before proceeding with the explanation, it is necessary to understand when a constructor must be declared explicit. In this regard, it is possible to quote the last section of the post Most C++ constructors should be explicit¹, by Arthur O'Dwyer.
- A(const A&) and A(A&&) should always be implicit.
- A(std::initializer_list) should always be implicit. If you have both A(std::initializer_list) and A(), then A() should also be implicit. Example: vector.
- Whenever std::tuple_size_v exists, the corresponding A(X,Y,Z) should be implicit. That is, the well-formedness of auto [x,y,z] = a should imply the well-formedness of A a = {x,y,z}. Examples: pair, tuple.
- Type-erasure types intended as drop-in replacements in APIs should have implicit constructor templates from the types they replace. Examples: string_view, function, any.
- Every other constructor (even the zero-argument constructor!) should be explicit or have a very well-understood domain-specific reason why not. Example: string(const char*).
- operator bool should always be explicit. Other operator Ts probably need to be implicit in order to do their job; but you should prefer named getter methods, anyway.
Thus, the conversion constructor must remain implicit, but the other user-declared constructor should be declared explicit.
