How const_iterators are implemented?

Question

#include <iostream>

template <typename T>
struct Node
{
    T value;
    Node<T>* next;
};

template <typename T>
struct LinkedList
{
    // head, tail....
    // some implementation...
};

template<
    template<typename> typename node,
    typename T,
    template<typename> typename iterator,
    template<typename> typename const_iterator
>
struct SomeComonFunctionsBetweenIterators
{
    node<T>* ptr;

    // some implementation...

    SomeComonFunctionsBetweenIterators(node<T>* ptr) : ptr(ptr) {}

    T& operator*() { return ptr->value; }

    iterator<T> GetIterator() { return iterator<T>(ptr); }

    // doesn't work. want some way like this instead of passing the
    // const iterator as a template argument.

    //operator const_iterator<T>() { return iterator<const T>(ptr) ; }

    operator const_iterator<T>() { return const_iterator<T>(ptr); }
};

template <typename T>
struct LinkedListConstIterator;

template <typename T>
struct LinkedListIterator
    : public SomeComonFunctionsBetweenIterators<Node, T, LinkedListIterator, LinkedListConstIterator>
{
    LinkedListIterator(Node<T>* ptr)
        : SomeComonFunctionsBetweenIterators<Node, T, LinkedListIterator, LinkedListConstIterator>(ptr) {}

    // some implementation...
};

template <typename T>
struct LinkedListConstIterator : public LinkedListIterator<T>
{
    LinkedListConstIterator(Node<T>* ptr) : LinkedListIterator<T>(ptr) {}

    const T& operator*() { return static_cast<const T&>(this->ptr->value); }
};

int main()
{
    Node<int> node{ 5, nullptr };

    LinkedListIterator<int> it(&node);
    std::cout << *it << '\n';

    LinkedListConstIterator<int> cit = it;
    std::cout << *cit << '\n';
}

In this code I have a linked list and an iterator to it. Also I have a const iterator which inherits from the normal iterator and when dereferenced, returns a const T. The iterator can be for a singly linked list or a doubly linked list and most of the functions in both of them are the same (dereferencing or comparing for example). So I extracted the common functions and put it in a common struct. I want to be able to asign normal iterators to const iterators. So I pass the const iterator to the normal iterator as a template argument and define a conversion operator from the normal iterator to const iterator. This way works but it requires me to always pass the const iterator alongside the normal iterator as a template argument.

Is there any better way to implement const_iterators? instead of passing the const iterator everywhere. How the const_iterators are implemented for example in the STL containers?

Answer 1

How the const_iterators are implemented for example in the STL containers?

You can probably look in your implementation's header files to see how they chose to do it. It will depend on the container type and its internal data structure. But the common pattern I've seen is that there's some private template that can take either non-const T or const T, and that will be used as a base or member of the actual distinct iterator types. One catch is that a specific type from the data structure needs to be used, independently of the type the iterator classes expose. In your example, Node<T> and Node<const T> are not interoperable, so SomeComonFunctionsBetweenIterators could work, but should probably have the node type as a template argument independent of the value type T.

But for an easy way to define iterator types, I always turn to Boost.Iterator's iterator_facade or iterator_adaptor. They take care of a lot of the technical requirements about iterators, letting the author just fill in the behavioral bits. iterator_facade is for implementing something "from scratch", and iterator_adaptor is for the common case of an iterator that contains and wraps another iterator.

The Boost documentation for iterator_facade discusses a way to define related iterator and const_iterator types. (Though their decision to make the iterators interoperable as long as the pointers can convert probably wouldn't be appropriate for iterators from containers.)

Using iterator_facade will also give a bunch of things algorithms may expect of iterators but missing from your code shown, like making std::iterator_traits work, equality and inequality, and other fiddly details.

#include <boost/iterator/iterator_facade.hpp>
#include <type_traits>

template <typename T>
struct Node
{
    T value;
    Node* next;
};

template <typename NodeType, typename ValueType, typename ContainerType>
class TLinkedListIterator :
    public boost::iterator_facade<
        TLinkedListIterator<NodeType, ValueType, ContainerType>, // CRTP Derived type
        ValueType,                  // Iterator's value_type
        std::forward_iterator_tag   // Category
    >
{
public:
    TLinkedListIterator() : m_node(nullptr) {}

protected:
    explicit TLinkedListIterator(NodeType* node) : m_node(node) {}

private:
    friend boost::iterator_core_access;
    friend ContainerType;
    template <typename N, typename V, typename C> friend class TLinkedListIterator;

    ValueType& dereference() const { return m_node->value; }
    void increment() { m_node = m_node->next; }

    // Templating allows comparison between iterator and const_iterator
    // in any combination.
    template <typename OtherValueType>
    bool equal(const TLinkedListIterator<NodeType, OtherValueType, ContainerType>& iter)
    { return m_node == iter.m_node; }

    NodeType m_node;
};

template <typename T>
class LinkedList
{
public:
    using iterator = TLinkedListIterator<Node<T>, T, LinkedList>;

    class const_iterator
        : public TLinkedListIterator<Node<T>, const T, LinkedList>
    {
    private:
        using BaseType = TLinkedListIterator<Node<T>, const T, LinkedList>;
    public:
        const_iterator() = default;

        // Converting constructor for implicit conversion from iterator
        // to const_iterator:
        const_iterator(const iterator& iter)
            : BaseType(iter.m_node) {}

    protected:
        explicit const_iterator(Node<T>* node)
            : BaseType(node) {}

        friend LinkedList<T>;
    };

    iterator begin() { return iterator(get_head()); }
    iterator end() { return iterator(); }
    const_iterator begin() const { return const_iterator(get_head()); }
    const_iterator end() const { return const_iterator(); }
    const_iterator cbegin() const { return begin(); }
    const_iterator cend() const { return end(); }

    // ...
};