Реализация stl совместимых итераторов

Хочу реализовать список который предоставляет stl-совместимые итераторы, то есть те которые можно использовать в stl алгоритмах. Вот что у меня получилось:

template<class T>
class Node
{
public:
    using UsingType = T;

    Node(const UsingType& v) : value(v), previous(nullptr), next(nullptr)
    {
    }
    Node(const UsingType& v, const std::shared_ptr<Node<UsingType>>& p, const std::shared_ptr<Node<UsingType>>& n) : value(v), previous(p), next(n) {}

    UsingType value;
    std::shared_ptr<Node<UsingType>> previous;
    std::shared_ptr<Node<UsingType>> next;
};

template<class T> class LinkedList;

template<class T>
class Iterator
{
public:
    using UsingType = T;
    friend class LinkedList<UsingType>;


    Iterator(const std::shared_ptr<Node<UsingType>>& node) : _node(node)
    {
    }

    Iterator& operator++()
    {
        _node = _node->next;
        return *this;
    }

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

    bool operator!=(const Iterator& it)
    {
        return _node != it._node;
    }

private:
    std::shared_ptr<Node<UsingType>> _node;
};



template<class T>
class LinkedList
{
public:
    using SizeType = unsigned int;
    using UsingType = T;

public:
    LinkedList() : _size(0), _begin(nullptr), _end(nullptr) 
    {
    }

    void pushBack(const UsingType& value)
    {
        std::shared_ptr<Node<UsingType>> node = std::make_shared<Node<UsingType>>(value);

        if (_size == 0)
        {
            _end = std::make_shared<Node<UsingType>>( UsingType() );

            _begin = node;
            _begin->next = _end;
            _end->previous = _begin;
        }
        else
        {
            node->previous = _end->previous;
            node->previous->next = node;
            node->next = _end;
            _end->previous = node;
        }
        ++_size;
    }

    Iterator<UsingType> begin()
    {
        return Iterator(_begin);
    }

    Iterator<UsingType> end()
    {
        return Iterator(_end);
    }


private:
    SizeType _size;
    std::shared_ptr<Node<UsingType>> _begin;
    std::shared_ptr<Node<UsingType>> _end;
};

Мне здесь не нравится вставка элемента, т.к. проверяется условие на пустой контейнер, которое будет верно только при первой вставке. Этого можно избежать если сразу, при создании контейнера, создавать два элемента которые будут располагаться перед началом и перед концом, но мне кажется это будет еще хуже.

Я смотрел стандартную реализацию, и, насколько я смог понять, там точно не происходит динамического выделения памяти для пустого контейнера и вставка элемента выполняется одинакового как для пустого контейнера так и не для пустого.

Вопрос: подскажите как нормально реализовать stl-совместимые итераторы? Это нормальный подход что итератор содержит указатель на Nodestd::list вроде так и сделано, но конечно гораздо хитрее ), если да то как правильно обозначить конец списка и начало? а если такой подход не верный то как сделать лучше?

Вот здесь отвечают на похожий вопрос, но ответ мне не нравится по приведенным выше причинам, так что это не дубликат.


Ответы (0 шт):