Как реализованы const_iterators? - PullRequest
Новая
       22

Как реализованы const_iterators?

0 голосов
/ 18 апреля 2020 
#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 T. Итератор может быть для односвязного списка или двусвязного списка, и большинство функций в них одинаковы (разыменование или сравнение, например). Поэтому я извлек общие функции и поместил их в общую структуру. Я хочу иметь возможность назначать обычные итераторы константным итераторам. Поэтому я передаю константный итератор обычному итератору в качестве аргумента шаблона и определяю оператор преобразования из обычного итератора в константный итератор. Этот способ работает, но он требует от меня всегда передавать константный итератор вместе с обычным итератором в качестве аргумента шаблона.

Есть ли лучший способ реализовать const_iterators? вместо передачи константного итератора везде. Как реализованы const_iterators, например, в контейнерах STL?

1 Ответ

1 голос
/ 18 апреля 2020

Как реализованы const_iterators, например, в контейнерах STL?

Вероятно, вы можете заглянуть в заголовочные файлы вашей реализации, чтобы увидеть, как они решили это сделать. Это будет зависеть от типа контейнера и его внутренней структуры данных. Но распространенный шаблон, который я видел, состоит в том, что есть какой-то закрытый шаблон, который может принимать неконстантные T или const T, и который будет использоваться в качестве основы или члена реальных различных типов итераторов. Одна из них заключается в том, что необходимо использовать определенный c тип из структуры данных независимо от типа, который предоставляют классы итераторов. В вашем примере Node<T> и Node<const T> не совместимы, поэтому SomeComonFunctionsBetweenIterators может работать, но, вероятно, должен иметь тип узла в качестве аргумента шаблона, независимого от типа значения T.

Но для простой способ определения типов итераторов, я всегда обращаюсь к Boost.Iterator's iterator_facade или iterator_adaptor. Они заботятся о многих технических требованиях к итераторам, позволяя автору просто заполнить поведенческие фрагменты. iterator_facade предназначен для реализации чего-либо «с нуля», а iterator_adaptor - для общего случая итератора, который содержит и упаковывает другой итератор.

Документация Boost для 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(); }

    // ...
};
...