Custom linked list const_iterator cannot traverse non-const instance of list

Question

As an exercise in learning C++, I'm trying to write a custom iterator for a linked list.

Nodes in the list are added using the following struct:

template <class T> struct Node {
  T val;
  Node* next;
  Node* prev;
  Node(const T& new_val): val(new_val), next(0), prev(0) { }
};

And here are the relevant parts of the iterator:

template <class T> class LList_iterator {
public:
  //...
  LList_iterator(Node<T>* p): node(p) { }
  //...
private:
  Node<T>* node;
};

The linked list provides a typedef for both an iterator and a const_iterator:

template <class T> class LList {
public:
  typedef LList_iterator<T> iterator;
  typedef LList_iterator<const T> const_iterator;

  iterator begin() { return iterator(head); }
  const_iterator cbegin() const { return const_iterator(head); }

  iterator end() { return iterator(0); }
  const_iterator cend() const { return const_iterator(0); }
  //...
private:
  Node<T>* head;
};

I'm can use iterator correctly, but the compiler throws an error whenever I call the constructor of const_iterator and pass a pointer to the first node in the (non-const) linked list (when I call cbegin() and cend()):

LList<int> l;
l.push_back(10);
for (LList<int>::const_iterator i = l.cbegin(); i != l.cend(); ++i)
  std::cout << *i << std::endl;

error: no matching functional-style cast from Node<int> *const to LList<int>::const_iterator (aka LList_iterator<const int>)

I believe this could be because the Node type expected by const_iterator (const int) is different than the type in the list I am traversing (of type int). If this is the case, is there any way for me to "temporarily" convert the LList template parameter to be const int? Or am I misguided in my understanding of the error?

Node<T> is indeed completely unrelated to Node<const T> and is the reason of your error. Most of the time the solution is to bite the bullet and rewrite an entire iterator class for the const case. — Passer By
– Passer By, Commented Jul 17, 2018 at 23:55
Or, maybe you could have 1 iterator class with 2 template paarameters - 1 for the Node data type (T), and 1 for the iterator's value_type (T or const T) that operators act on. — Remy Lebeau
– Remy Lebeau, Commented Jul 18, 2018 at 0:17

Mark Lakata · Accepted Answer · 2018-07-18 01:59:31Z

2

I think you need to do this:

template <class T> class LList_const_iterator {
public:
  //...
  LList_iterator(const Node<T>* p): node(p) { }
  //...
private:
  const Node<T>* node;
};

and change your typedef

// from
typedef LList_iterator<const T> const_iterator;
// to
typedef LList_const_iterator<T> const_iterator;

answered Jul 18, 2018 at 1:59

Mark Lakata

21.1k6 gold badges114 silver badges128 bronze badges

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

1 Comment

iRove Over a year ago

Yeah, I guess writing another iterator class would be the way to go. This worked for me!

Collectives™ on Stack Overflow

Custom linked list const_iterator cannot traverse non-const instance of list

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related