const_iterators是如何实现的？

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';
}

在这段代码中，我有一个链表和一个迭代器。我还有一个 const 迭代器，它继承自普通迭代器，当取消引用时，returns a const T。迭代器可以用于单向链表或双向链表，并且两者中的大多数功能都是相同的（例如取消引用或比较）。所以我提取了公共函数并将其放在一个公共结构中。我希望能够将普通迭代器分配给 const 迭代器。所以我将 const 迭代器作为模板参数传递给普通迭代器，并定义一个从普通迭代器到 const 迭代器的转换运算符。这种方式可行，但它要求我始终将 const 迭代器作为模板参数与普通迭代器一起传递。

有没有更好的实现方式const_iterators？而不是到处传递 const 迭代器。 const_iterators 如何在 STL 容器中实现？

Answer 1

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

您或许可以查看您的实现的头文件，看看他们是如何选择这样做的。这将取决于容器类型及其内部数据结构。但我见过的常见模式是，有一些私有模板可以采用非常量 T 或 const T，并将用作实际不同迭代器类型的基础或成员。一个问题是需要使用数据结构中的特定类型，与迭代器类公开的类型无关。在您的示例中，Node<T> 和 Node<const T> 不可互操作，因此 SomeComonFunctionsBetweenIterators 可以工作，但应该将节点类型作为独立于值类型 T 的模板参数。

但是对于定义迭代器类型的简单方法，我总是求助于 Boost.Iterator 的 iterator_facade 或 iterator_adaptor。他们处理了很多关于迭代器的技术要求，让作者只需填写行为位。 iterator_facade 用于实现某些东西 "from scratch"，而 iterator_adaptor 用于包含并包装另一个迭代器的迭代器的常见情况。

The Boost documentation for iterator_facade 讨论了一种定义相关 iterator 和 const_iterator 类型的方法。（尽管他们决定让迭代器只要指针可以转换就可以互操作，这可能不适合来自容器的迭代器。）

使用 iterator_facade 还将提供算法可能期望迭代器提供的一些东西，但在您显示的代码中缺失，例如使 std::iterator_traits 工作、相等和不等以及其他繁琐的细节。

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

    // ...
};

const_iterators是如何实现的？

How const_iterators are implemented?

c++

iterator

const-iterator