Блог

Мы можем определить a LinkedListNode , как показано ниже:

 template <typename T>
struct LinkedListNode {
    T val;
    LinkedListNode* next;
    LinkedListNode() : val{}, next(nullptr) {}
    LinkedListNode(T x) : val{ x }, next(nullptr) {}
    LinkedListNode(T x, LinkedListNode* next) : val{ x }, next(next) {}
};
 

Если мы хотим определить функцию, которая принимает «Связанный список», у нас есть два варианта. Во-первых, мы могли бы передать a LinkedListNode* функции.

 template <typename T>
int func(LinkedListNode<T>* node);
 

Во-вторых, мы могли бы определить LinkedList класс, который содержит указатель на «головной» узел. Тогда мы могли бы определить функцию, которая принимает LinkedList .

 template <typename T>
struct LinkedList {
    LinkedListNode<T>* head;
    // other member functions
};

template <typename T>
int func(LinkedList<T>amp; llist);
 

Одна из причин, по которой вторая представляется предпочтительной, поскольку она может обеспечить лучшую инкапсуляцию функций, которые изменяют «Связанный список». Например, a FindMax , который принимает a LinkedListNode* , может лучше подходить как функция-член LinkedList , чем как функция-член LinkedListNode .

Какие конкретные причины есть, чтобы предпочесть одно другому?Меня особенно интересуют причины, по которым вы можете предпочесть просто использовать LinkedListNode* s.

Я думаю, прежде чем вы решите использовать односвязный список, у вас должна быть какая-то причина использовать его поверх обычного std::vector . Вам нужны реальные тесты, которые показывают, что односвязный список улучшит производительность в конкретном приложении, которое вы имеете в виду; вы были бы удивлены, насколько часто это ухудшает, а не улучшает ситуацию. Подсказка: теоретическая вычислительная сложность ортогональна шаблонам доступа к памяти, а на современных процессорах шаблоны доступа к памяти определяют производительность — большинство вычислений по существу бесплатны, поскольку не требуют дополнительного времени: они скрываются под всеми промахами кэша.

Тогда у вас должна быть причина не использовать std::forward_list . Но, возможно, вам нужны навязчивые связанные списки: тогда приведите доводы в пользу отказа от использования boost::intrusive::slist<T> или аналогичного существующего и хорошо протестированного типа библиотеки.

Если вы все еще продолжаете свою собственную реализацию, то самым первым шагом будет использование в std::unique_ptr качестве указателя владельца для дочерних узлов вместо ручного управления памятью — таким образом, будет очень легко показать, что утечка памяти не происходит — код становится корректным по конструкции, а утечки памяти требуютдополнительные усилия по сравнению с пропуском.

Другими словами: не изобретайте велосипед, если у вас нет четко сформулированной причины для этого. Конечно, вы можете реализовать связанные списки сколько угодно в качестве упражнения, но имейте в виду, что вы, скорее всего, реализуете контейнер, который будете использовать в наименьшей степени, поэтому я бы сказал, что вы узнаете намного больше о том, как работает C , реализуя, например, контейнер vector / array.

Если вы используете std::unique_ptr или даже управляете памятью вручную, вы, вероятно, столкнетесь с ловушкой взрыва стека деструктора. Рассмотрим

 template <typename T>
struct LinkedListNode1 {
    T val;
    std::unique_ptr<LinkedListNode1> next;
};

template <typename T>
struct LinkedListNode2 {
    T val;
    LinkedListNode2* next = nullptr;
    ~LinkedListNode2() { delete next; }
};
 

In both cases, the destructor gets invoked recursively, and if the list is sufficiently long, you’ll run out of stack. Recursion is also usually less efficient than a loop. To prevent that, you must be never deallocating nodes that have non-null next .

 template <typename T>
struct LinkedListNode1 {
    T val;
    std::unique_ptr<LinkedListNode1> next;
    ~LinkedListNode1() {
      auto node = std::move(next);
      while (node)
        node = std::move(node->next);
      assert(!next);
    }
};

template <typename T>
struct LinkedListNode2 {
    T val;
    LinkedListNode2* next = {};
    ~LinkedListNode2() {
      using std::swap;
      LinkedListNode2* node = {};
      swap(node, next);
      while (node) {
        LinkedListNode2* tmp = {};
        swap(tmp, node);
        assert(!node);
        swap(node, tmp->next);
        assert(!tmp->next);
        delete tmp;
      }
      assert(!next);
    }
};
 

Интеллектуальные указатели значительно упрощают код. Я написал версию необработанного указателя с заменами, чтобы было проще показать, что утечка памяти отсутствует: правильно используемая замена никогда не «теряет» значение.

Например, a FindMax , который принимает LinkedListNode*

Это снова изобретение колеса. В C идиома для «нахождения максимального элемента» — std::max_element from #include <algorithm> . Вы должны использовать алгоритмы, предоставляемые стандартной библиотекой (и любые другие, которые могут вам понадобиться, например, из библиотек Boost или только для заголовков).

Для этого вам нужен итератор для списка. Это будет, по необходимости, LegacyForwardIterator . Здесь is a имеет строгое техническое значение: это краткий способ сказать: «ваш итератор будет соответствовать концепции и соблюдать контракт LegacyForwardIterator«.

Такой итератор будет выглядеть очень примерно следующим образом:

 template <typename T>
class LinkedListNode1 {
    std::unique_ptr<LinkedListNode1> next;

    template <typename V> class iterator_impl {
        LinkedListNode1 *node = {};
        using const_value_type = std::add_const_t<V>;
        using non_const_value_type = std::remove_const_t<V>;
    public:
        using value_type = V;
        using reference = Vamp;;
        using pointer = V*;

        iterator_impl() = default;
        template <typename VO>
        iterator_impl(const iterator_impl<VO> amp;o) : node(o.operator->()) {}
        explicit iterator_impl(LinkedListNode1 *node) : node(node) {}

        auto *operator->() const { return node; }
        pointer operatoramp;() const { return amp;(node->val); }
        reference operator*() const { return node->val; }
        iterator_impl amp;operator  () { node = node->next.get(); return *this; }
        iterator_impl operator  (int) {
            auto retval = *this;
            this->operator  ();
            return retval;
        }
        bool operator==(const iterator_impl amp;o) const { return node == o.node; }
        bool operator!=(const iterator_impl amp;o) const { return node != o.node; }
    };
public:
    T val;
    using iterator = iterator_impl<T>;
    using const_iterator = iterator_impl<const T>;
 

next Указатель можно сделать закрытым. Тогда базовая функциональность будет включать:

     LinkedListNode1() = default;
    LinkedListNode1(const T amp;val) : val(val) {}
    ~LinkedListNode1() {
      auto node = std::move(next);
      while (node)
        node = std::move(node->next);
    }

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

    iterator insert_after(const_iterator pos, const Tamp; value) {
        auto next = std::make_unique<LinkedListNode1>();
        next->val = value;
        auto retval = iterator(next.get());
        pos->next = std::move(next);
        return retval;
    }
 

Можно было бы использовать insert_after для расширения списка. Конечно, необходимо добавить другие подобные методы.

Тогда мы, вероятно, также захотим поддерживать списки инициализаторов:

     LinkedListNode1(std::initializer_list<T> init) {
        auto src = init.begin();
        if (src == init.end()) return;
        val = *src  ;
        for (auto dst = iterator(this); src != init.end();   src)
            dst = insert_after(dst, *src);
    }
};
 

Теперь вы можете предварительно заполнить список списком инициализаторов, выполнить итерацию с использованием range-for и использовать его со стандартными алгоритмами:

 #include <iostream>

int main() {
    LinkedListNode1<int> list{1, 3, 2};
    for (auto const amp;val : list)
        std::cout << val << 'n';
    assert(*std::max_element(list.begin(), list.end()) == 3);
}
 

Но теперь мы подходим к самому важному вопросу:

Какие конкретные причины есть, чтобы предпочесть один другому

По умолчанию — отправной точкой — является предоставление контейнера, поскольку это абстракция, с которой мы имеем дело: «вещь», о которой вы думаете, — это связанный список, а не узел списка. Структура данных, о которой вы узнаете, — это, опять же, связанный список. И по уважительной причине: тип узла — это деталь реализации, поэтому вам нужно будет придумать причины, зависящие от конкретного приложения, для раскрытия типа узла, и любой приведенный аргумент должен выдерживать проверку при работе с итераторами. Вам действительно нужно раскрывать эти узлы, или то, что вы на самом деле хотите, просто удобный способ перебора элементов, хранящихся в коллекции, возможно, разделить список и т. Д.? Доступ к узлу не требуется ни для одного из них. Это решаемая проблема, как вы узнаете, прочитав документацию std::forward_list .

Вы также хотели бы рассмотреть поддержку распределителя. Я бы не стал беспокоиться о распределителях C 98, но полиморфные распределители (наконец-то!) Действительно пригодны для использования, поэтому вы захотите их реализовать ( std::pmr::polymorphic_allocator например, и std::pmr пространство имен в целом).

Для полной функциональности вам в значительной степени потребуется добавить большинство std::forward_list методов и конструкторов. Так что это небольшая работа, и есть много деталей, чтобы заставить его работать хорошо, независимо от типа значения. И, таким образом, мы проходим полный круг: реальные контейнеры, которые должны быть полезными, не беспокоясь о низкоуровневых деталях, требуют много работы, но их приятно использовать — и они совсем не похожи на большинство учебников «обучающего» кода.

Связанный список часто используется при обучении структурам данных — true . Тем не менее, большинство книг по C , используемых в обучении, крайне неадекватны в демонстрации того, что влечет за собой современная, полностью функциональная структура данных / контейнер — они даже не могут получить это право для чего-то столь «простого», как односвязный список.

Разрыв между C-подобным односвязным списком — именно тем, с чего вы начали в вопросе, — и контейнером C с односвязным списком составляет порядка пары тысяч строк кода и тестов. Это то, чему они обычно не учат, и именно здесь на самом деле самые важные биты: это разница между игрушечным кодом и производственным кодом.

Даже без тестов полнофункциональный односвязный контейнер списка составляет ~ 500 строк без поддержки полиморфного распределителя и, вероятно, по крайней мере вдвое больше, чем при такой поддержке, а тесты удвоили бы размер кода в несколько раз — хотя, если вы были умны, вы могли бы повторно использовать множество тестов, используемых различными STLреализации 🙂

И, кстати: достойная реализация связанного списка на C также не заставит вас вручную обрабатывать узлы. Сам список — контейнер — будет абстрактным типом данных с набором функций, которые обеспечивают функциональность, а также с некоторой абстракцией для итераторов (хотя они будут просто указателями в некоторой типобезопасной маскировке). В этом опять же разница между обучающим кодом и простым в правильном использовании и сложным в неправильном использовании производственным кодом. Один из примеров, который я могу привести прямо сейчас, — это растянутые буферы, реализованные в проекте Bitwise ion. Это ссылка на видео, где они реализованы вживую, и они служат достойным примером того, как абстракции работают на C (а также того, как вы определенно не должны писать это на C — C и C — разные языки!).