iterators implementation in STL containers

Question

This is the sample code I've written, just a simple version to test out an iterator implementation:

template <typename T>
struct ArrayIterator {
  using value_type = typename T::value_type;
  using pointer = value_type*;
  using reference = value_type&;
  using self = ArrayIterator;
  
  pointer ptr;
  
  ArrayIterator() : ptr{nullptr} {}
  ArrayIterator(pointer ptr) : ptr{ptr} {}
  
  reference operator*() {
    return *ptr;
  }
  
  bool operator==(self const& other) const {
    return ptr == other.ptr;
  }
  
  bool operator!=(self const& other) const {
    return !(*this == other);
  }
  
  self operator++() {
    ++ptr;
    return *this;
  }
  
  self operator++(int) {
    auto copy = *this;
    ++ptr;
    return copy;
  }
  
};

template <typename T, size_t size>
struct Array {
  T arr[size];
  
  using value_type = T;
  using iterator = ArrayIterator<Array<T, size>>;
  
  iterator begin() {
    return iterator(arr);
  }
  
  Array() : arr{1, 3, 4, 22, 3} {}
  
  iterator end() {
    return iterator(arr + size);
  }
};

int main() {
  using array = Array<int, 5>;
  array arr;
}

Assuming everything is public, and we only pass int as type parameter, and the array has the default constructor just to test range-based for loop. It works.

My question is, why can't we use inheritance? Something like this:

template <typename T, size_t size>
struct Array : ArrayIterator<Array<T, size>> {}

If used, I get the following error (compiler is clang 11):

first.cpp:46:34: error: no type named 'value_type' in 'Array<int, 5>'
  using value_type = typename T::value_type;
                     ~~~~~~~~~~~~^~~~~~~~~~
first.cpp:82:16: note: in instantiation of template class 'ArrayIterator<Array<int, 5>>' requested here
struct Array : ArrayIterator<Array<T, size>> {
               ^
first.cpp:101:9: note: in instantiation of template class 'Array<int, 5>' requested here
  array arr;
        ^
1 error generated

I can’t understand what's going on.

please always add the language tag. It helps your question to be seen by people following the tag and enabled syntax highlighting for code. — bolov
– bolov, Commented Jan 18, 2021 at 6:19
Wait, why do you want to inherit the Array from ArrayIterator? An array is not an iterator. — user202729
– user202729, Commented Jan 18, 2021 at 6:57
If you want the array to be able to be used as an iterator, just write a conversion operator. — user202729
– user202729, Commented Jan 18, 2021 at 6:59

Remy Lebeau · Accepted Answer · 2021-01-18 07:05:44Z

2

You can’t use inheritance like you want because the code will have a catch-22 if you try. ArrayIterator will try to define its value_type as an alias of the array’s value_type before the latter has been defined yet. That is why you are getting the compiler error.

Your iterator has no need to access the Array class itself, so there is no point in passing the Array class type to the iterator’s template parameter. Just pass the array’s value_type instead of Array itself, and change the iterator’s value_type to be just T instead of typename T::value_type:

template <typename T>
struct ArrayIterator {
  using value_type = T;
  using pointer = value_type*;
  using reference = value_type&;
  using self = ArrayIterator;
  
  pointer ptr;
  
  ArrayIterator() : ptr{nullptr} {}
  ArrayIterator(pointer ptr) : ptr{ptr} {}
  
  reference operator*() {
    return *ptr;
  }
  
  bool operator==(self const& other) const {
    return ptr == other.ptr;
  }
  
  bool operator!=(self const& other) const {
    return ptr != other.ptr;
  }
  
  self& operator++() {
    ++ptr;
    return *this;
  }
  
  self operator++(int) {
    auto copy = *this;
    ++ptr;
    return copy;
  }
};

template <typename T, size_t size>
struct Array {
  using value_type = T;
  using iterator = ArrayIterator<T>;

  T arr[size];

  iterator begin() {
    return iterator(arr);
  }
  
  iterator end() {
    return iterator(arr + size);
  }
};

int main() {
  using array = Array<int, 5>;
  array arr{1, 3, 4, 22, 3};
  for (auto val : arr) {
    cout << val << endl;
  }
}

answered Jan 18, 2021 at 7:05

Remy Lebeau

609k36 gold badges516 silver badges875 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Vegeta Over a year ago

Thanks for the reply. But I don't get why it can't access because template instantiation happens at compile time. ``` template <typename T> struct Rat { using value_type = typename T::value_type; }; struct Cat: Rat<Cat> { using value_type = std::string; }; ```

Remy Lebeau Over a year ago

@Vegeta like I said, because Array::value_type hasn’t been defined yet, because the contents of Array haven’t been defined yet, when ArrayIterator tries to access them. And that is exactly what the error message is telling you.

Collectives™ on Stack Overflow

iterators implementation in STL containers

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related