How to Correctly Implement Custom Iterators and Const_Iterators

How to correctly implement custom iterators and const_iterators?

Choose type of iterator which fits your container: input, output, forward etc.
Use base iterator classes from standard library. For example, std::iterator with random_access_iterator_tag.These base classes define all type definitions required by STL and do other work.
To avoid code duplication iterator class should be a template class and be parametrized by "value type", "pointer type", "reference type" or all of them (depends on implementation). For example:
```
// iterator class is parametrized by pointer type
template <typename PointerType> class MyIterator {
    // iterator class definition goes here
};

typedef MyIterator<int*> iterator_type;
typedef MyIterator<const int*> const_iterator_type;
```
Notice iterator_type and const_iterator_type type definitions: they are types for your non-const and const iterators.

What is the correct way to implement iterator and const_iterator in C++17?

The point of the second implementation is something you didn't copy: to make it easy to implement a specific requirement. Namely, an iterator must be implicitly convertible to a const_iterator.

The difficulty here lies in preserving trivial copyability. If you were to do this:

template<class T>
class ContainerIterator {
    using pointer = T*;
    using reference = T&;
    ...
    ContainerIterator(const ContainerIterator &) = default; //Should be trivially copyable.
    ContainerIterator(const ContainerIterator<const T> &) {...}
};

That doesn't work. const const Typename resolves down to const Typename. So if you instantiate ContainerIterator with a const T, then you now have two constructors that have the same signature, one of which is defaulted. Well, this means that the compiler will ignore your defaulting of the copy constructor and thus use you non-trivial copy constructor implementation.

That's bad.

There are ways to avoid this by using some metaprogramming tools to detect the const-ness of the T, but the easiest way to fix it is to specify the const-ness as a template parameter:

template<class T, bool IsConst>
class ContainerIterator {
    using pointer = std::conditional_t<IsConst, const T*, T*>;
    using reference = std::conditional_t<IsConst, const T&, T&>;
    ...

    ContainerIterator(const ContainerIterator &) = default; //Should be trivially copyable.
    template<bool was_const = IsConst, class = std::enable_if_t<IsConst || !was_const>>>
    ContainerIterator(const ContainerIterator<T, was_const> &) {...}
};

Templates are never considered to be copy constructors, so this won't interfere with trivial copyability. This also uses SFINAE to eliminate the converting constructor in the event that it is not a const iterator.

More information about this pattern can be found as well.

Constructing const_iterator from iterator

You can simply provide an implicit conversion operator which converts the non-const version of your iterator to the const version. A short example :

template<class T>
class my_iter
{
public:
    // Non-const iterator can be implicitly converted to const
    operator my_iter<const T>() const {
        // Replace this with however your iterator is constructed
        return {};
    }
};

Edit :
This solution does not allow a typical comparison operator to interoperate between const and non-const iterators, which is a problem. A work around is to force the comparison operator to only accept a const iterator as argument. It will implicitly use the conversion operator when passed a non-const iterator. Example :

bool operator==(const my_iter<std::add_const_t<T>> & p_other) const 
{
    // Compare...
}

This still has the down side that the privates of the argument are not accessible. One work around is to make iterator<const T> a friend class of iterator<T> :

#include <type_traits>

template<class T>
class my_iter
{
public:
    // Non-const iterator can be implicitly converted to const
    operator my_iter<const T>() const {
        // Replace this with however your iterator is constructed
        return {};
    }

    bool operator==(const my_iter<std::add_const_t<T>> & p_other) const 
    {
        return state == p_other.state; // Works even if `state` is `private`
    }

private:
    // Some iterator implementation detail
    T * state = nullptr;

    // `iter<T>` and `iter<const T>` are friends of each other
    friend class my_iter<std::remove_const_t<T>>;
    friend class my_iter<std::add_const_t<T>>;
};

Another is to explicitly convert *this to an iterator<const T>& and only actually implement operator== for iterator<T> with iterator<T> where both objects' private members are accessible.

bool operator==(const my_iter<std::add_const_t<T>> & p_other) const 
{
    if constexpr (std::is_same_v<std::decay_t<decltype(p_other)>, my_iter<T>>) {
        // `*this` and `p_other` are both `const T` iterators
        // You may access the private members of both objects here
        return state == p_other.state; // Works even if `state` is `private`
    }
    else {
        // The `p_other` is not the same type as `*this`
        return static_cast<const my_iter<const T> &>(*this) == p_other;
    }
}

Whichever solution is used, it can be repeated for operator<. Fromoperator< you can construct to other comparison operators. For example operator>(a, b) can be implemented as return b < a; and operator==(a, b) can be implemented as return !(a<b) && !(b<a);

How const_iterators are implemented?

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(); }

    // ...
};

How to avoid code duplication implementing const and non-const iterators?

[The best answer was, unfortunately, deleted by a moderator because it was a link-only answer. I understand why link-only answers are discouraged; deleting it, however, has robbed future seekers of very useful information. The link has remained stable for more than seven years and continues to work at the time of this writing.]

I strongly recommend the original Dr. Dobb's Journal article by Matt Austern entitled "The Standard Librarian: Defining Iterators and Const Iterators", January 2001. Should that link go bad, now that Dr. Dobb's has ceased operating, it's also available here.

To prevent this replacement answer from being deleted, I will summarize the solution.

The idea is to implement the iterator once as a template that takes an extra template parameter, a boolean that says whether or not this is the const version. Anywhere in the implementation where the const and non-const versions differ, you use a template mechanism to select the correct code. Matt Austern's mechanism was called choose. It looked like this:

template <bool flag, class IsTrue, class IsFalse>
struct choose;

template <class IsTrue, class IsFalse>
struct choose<true, IsTrue, IsFalse> {
   typedef IsTrue type;
};

template <class IsTrue, class IsFalse>
struct choose<false, IsTrue, IsFalse> {
   typedef IsFalse type;
};

If you had separate implementations for const and non-const iterators, then the const implementation would include typedefs like this:

typedef const T &reference;
typedef const T *pointer;

and the non-const implementation would have:

typedef T &reference;
typedef T *pointer;

But with choose, you can have a single implementation that selects based on the extra template parameter:

typedef typename choose<is_const, const T &, T &>::type reference;
typedef typename choose<is_const, const T *, T *>::type pointer;

By using the typedefs for the underlying types, all the iterator methods can have an identical implementation. See Matt Austern's complete example.

Custom Iterators

I haven't compiled this, but the problem appears to be that operator bool(); it provides an implicit conversion to bool, which is, in turn, convertible to int. Iterators in general don't provide their own validation, so this is unusual. If you need it, mark it explicit. That will prevent the implicit conversion.

How to Correctly Implement Custom Iterators and Const_Iterators