How to write a const iterator idiomatically?

Question

I am writing a linked list implementation, but I've gotten stuck on how to implement a const iterator accessed through cbegin() alongside the normal iterator. Here's my attempt at a solution:

#include <iostream>

using namespace std;

template <typename T>
class ListNode {
public:
    ListNode<T>* next_;
    ListNode<T>* prev_;
    T data_;

    ListNode():
        next_(nullptr),
        prev_(nullptr)
    {}
};

template <typename T>
class ListIterator
{
    typedef ListNode<T> node;
    typedef ListNode<T>* pointer;
    pointer p_;

public:
    ListIterator(pointer p) : p_(p) {}
    T& operator*() { return p_->data_; }
};

template<typename T>
class List
{
public:
    typedef ListNode<T> node;
    typedef ListNode<T>* pointer;
    typedef ListIterator<T> iterator;
    typedef ListIterator<const T> constIterator;

    List() :
        head_(nullptr),
        tail_(nullptr),
        size_(0)
    {}

    void pushBack(pointer p) {
        p->next_ = nullptr;
        p->prev_ = nullptr;

        if (size_ == 0) {
            head_ = p;
        } else {
            tail_->next_ = p;
            p->prev_ = tail_;
        }

        tail_ = p;
        ++size_;
    }

    iterator begin() { return head_; }
    iterator end() { return nullptr; }
    constIterator cbegin() { return head_; }
    constIterator cend() { return nullptr; }

private:
    pointer head_;
    pointer tail_;
    unsigned int size_;
};

class Dog {
public:
    int age;
};

int main() {
    auto list = List<Dog>();
    auto dogNode = ListNode<Dog>();
    list.pushBack(&dogNode);
    auto b = list.cbegin();
}

When I try to run this, I get the error error: no viable conversion from returned value of type 'List<Dog>::pointer' (aka 'ListNode<Dog> *') to function return type 'List<Dog>::constIterator' (aka 'ListIterator<const Dog>')

This error makes sense to me, but I can't figure out a good workaround that doesn't involve writing a separate ConstListIterator class (this works, but it feels wrong to copy-pasta all the operator overloading code from ListIterator--most of it omitted from this sample).

In this question, the author uses the approach of parametrizing ListIterator with TNode, which in this context would be ListNode<Dog> rather than Dog. The problem with this approach is that then the operator* can't return an actual Dog, because the ListIterator class doesn't know about the typename Dog. So that solution just hardcodes in the type of data_, so you lose all the benefits of the metaprogramming.

Is there a trick to make this work nicely, or should I just have a separate ConstListIterator class?

Thank you!

Answer 1

The reason for your error is that you are trying to return head, which is of type ListNode<T>* from a function with the return type constIterator AKA ListIterator<const T>.

To answer your question, the only difference between an iterator and a const_iterator is that a const_iterator returns a const reference to the value_type of the container instead of just a reference. Therefore, passing const T as the template argument should result in the desired functionality. Since operator* returns T&, if T is instead const T, then it returns const T&, which is correct. It seems that the issue you were having was because you were returning the wrong types from your iterator functions, as noted above.

Your iterator functions should instead look like this:

iterator begin() { return iterator{head_}; }
iterator end() { return iterator{nullptr}; }
constIterator cbegin() { return constIterator{head_}; }
constIterator cend() { return constIterator{nullptr}; }

This returns iterator and constIterator objects that are constructed using the pointers head_ and nullptr, which is what you want.

The template parameter you used for the iterators, the value_type of the list, is correct.

Answer 2

Having the node type be a template argument for the iterator is reasonable and allows

using constIterator=ListIterator<const ListNode<T>>;

which conveniently precludes structural modifications as well as content modifications. It allows cbegin to work as written (implicitly adding const to head_’s type). It also allows T to be const itself (which works for a linked list: it never needs to relocate anything).

To define operator*, you can just use auto:

auto& operator*() const {return p_->data_;}

The constness of *p_ carries over to data_ and thence to the return type.

Before C++14

In C++11, you can equip ListNode with

using value_type=T;

and use type traits like is_const and conditional to derive const T from const ListNode<T>.

In C++03, you can directly write a SFINAE-based trait for the purpose.