How to correctly implement custom Iterators with Inheritance

Question

I reinvented the STL vector for practice and understanding. Naturally I also had to implement an Iterator System. For re-usability I wanted to implement all Iterator Categorys with Inheritance (for example: class random_access_iterator : public bidirectional_iterator<T, Container>).

Now I ran into a huge problem. Consider following snippet:

custom_vector<int>::iterator it_start = container.begin(), it_end = container.end();
custom_vector<int> other_container(it_start, --(--it_end));

Since the decrement operator has the category bidirectional Iterator I also implemented it there.

template <class T, class Container>
class bidirectional_iterator : public forward_iterator<T, Container>
{
    // ...
    public:
        /* Decrement Operators */
        bidirectional_iterator &operator--() { /* code */ }
        bidirectional_iterator operator--(int) { /* code */ }
    // ...
}

Considering that, the following code will not work since the first argument will be of type random_access_iterator and the second argument will be of type bidirectional_iterator. Since the Decrement Operators return an bidirectional_iterator.

custom_vector<int> other_container(it_start, --(--it_end));

Since it would not make sense to have a constructor with two different Iterator Types (and since the STL Vector also does not have such a constructor) I will not implement such a constructor, which leads to an compilation error.

error: no matching constructor for initialization of 'custom_vector<int>'
        custom_vector<int> other_container(it_start, --(--it_end));
                           ^               ~~~~~~~~~~~~~~~~~~~~~~
candidate constructor not viable: no known conversion from 'custom_vector<int>::iterator' (aka 'random_access_iterator<int, custom_vector<int> >') to 'custom_vector<int>::size_type' (aka 'unsigned long') for 1st argument
                explicit custom_vector(size_type n, const value_type &val = value_type(), const allocator_type &alloc = allocator_type()) : _capacity(n), _alloc(alloc)
                         ^
note: candidate template ignored: deduced conflicting types for parameter 'InputIterator' ('random_access_iterator<int, custom_vector<int> >' vs. 'bidirectional_iterator<int, custom_vector<int> >')
                custom_vector(InputIterator first, InputIterator last, const allocator_type &alloc = allocator_type(),
                ^
note: candidate constructor not viable: allows at most single argument 'alloc', but 2 arguments were provided
                explicit custom_vector(const allocator_type &alloc = allocator_type()) : _capacity(), _alloc(alloc), _content() {}
                         ^
note: candidate constructor not viable: requires single argument 'x', but 2 arguments were provided
                custom_vector(const custom_vector &x) : _capacity(x.capacity()), _alloc(x.get_allocator()), _content()
                ^
1 error generated.

1. Is my Iterator implementation with Inheritance correct? Does it make sense to stick to that implementation or would it be better to just implement for each Container a specific Iterator?
2. Is there a way to implement an "Iterator Converter" that automatically converts for example my bidirectional_iterator to an random_access_iterator when needed?

Answer 1

I am not convinced that inheritance is a good solution to implement the different iterators. Furthermore, the iterator category expresses nothing about its implementation. Fot example, both std::vector and std::deque containers support random access, but the double-ended queue does not guarantee contiguity in memory and expects a specific implementation to access individual elements by their index.

Conversely, the idea of creating generic iterators based on the memory model they operate on is a design that allows a certain flexibility and robustness. Provided that you are working only with STL-like containers, iterators could be implemented depending on the data structure they are used on, dividing them in five types: ArrayIterator, DequeIterator, ForwardListIterator, ListIterator, SetIterator. It is important to note that the last type is named to indicate that it performs only in-order traversal on the binary search tree, since the name "BinaryTreeIterator" would not suggest which of the different traverse operations is performed.

A basic implementation may be the following:

template <typename T, typename Ptr>
struct Iterator
{
  using value_type.        = T;
  using pointer            = Ptr;
  using elt_pointer.       = typename std::pointer_traits<Ptr>::rebind</* type */>;
  using reference          = std::iter_reference_t<Ptr>;
  using difference_type    = std::ptrdiff_t;
  using iterator_category  = /* implementation-defined */;

  Iterator();
  explicit Iterator(elt_pointer);

  template <std::convertible_to<Ptr> PtrR>
  Iterator(const Iterator<T, PtrR>&);

  reference operator*() const;
  pointer operator->() const;

  Iterator& operator++();
  Iterator operator++(int);
};

template <typename T, typename PtrL, typename PtrR>
bool operator==(const Iterator<T, PtrL>&, const Iterator<T, PtrR>&);

It is possible to specialize the class to represent an iterator or const-iterator by specifying a non-constant or constant pointer type, respectively. Other than avoiding the duplication of the interface to create an iterator or const-iterator, this design allows to use fancy pointers because the pointer members are rebound via std::pointer_traits. Furthermore, the conversion constructor allows to construct a const-iterator from an iterator.