CODEWITHSUNDEEP
c++inheritancestliteratorc++98
toni
toni

Reputation: 152

How to correctly implement custom Iterators with Inheritance

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?

Upvotes: 0

Views: 520

Answers (2)

LoS
LoS

Reputation: 1833

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.

Upvotes: 1

Caleth
Caleth

Reputation: 63162

Is my Iterator implementation with Inheritance correct?

No. C++ doesn't use inheritance for it's iterators, it uses concepts. A type is a std::random_access_iterator if it provides the random access iterator methods ([], +, -, etc). This includes pointer types, which can't inherit from some base class.

Each container's iterator is particular to that container. The different categories exist because some operations can't be (efficiently) implemented for those containers.

Upvotes: 2

Related Questions