Построение структур данных: связные списки, стеки и очереди
Реализуем односвязный список, стек и очередь с нуля с помощью указателей, умных указателей и шаблонов
std::vector, std::list, std::stack и std::queue. Но именно собственная реализация помогает по-настоящему понять, как хранятся и извлекаются данные и почему каждый контейнер имеет ту производительность, которую имеет. В этой теме вы собираете три классические структуры из одного кирпичика - узла - и видите, где каждая из них является правильным инструментом.
- построить односвязный список из узлов, связанных
std::unique_ptr, - реализовать стек (последним пришёл - первым ушёл) и очередь (первым пришёл - первым ушёл) поверх этого списка,
- сделать каждую структуру обобщённой с помощью шаблона класса, чтобы она хранила любой тип,
- рассуждать о компромиссах и выбирать подходящую структуру для задачи.
Это опирается на предыдущие темы курса: Умные указатели, Шаблоны функций и классов, Семантика перемещения и Правило пяти. Их не обязательно держать перед глазами, но мы будем на них опираться.
Узел: одно звено цепи
Узел - это маленькая структура, хранящая одно значение и указатель на следующий узел. Весь список - это просто узлы, сцепленные вместе; последний узел не указывает ни на что (nullptr), что обозначает конец.
Классический способ из языка C - сырой указатель Node*. В современном C++ мы позволяем каждому узлу владеть следующим через std::unique_ptr. Владение исключительное - каждый узел владеет ровно тем хвостом, что за ним, - и когда голова уничтожается, деструкторы срабатывают вниз по цепи и освобождают каждый узел автоматически. Никаких ручных delete, никаких утечек.
#include <memory>
struct Node {
int value; // полезная нагрузка
std::unique_ptr<Node> next; // владеет остатком цепи
Node(int v) : value(v), next(nullptr) {}
};Поскольку next - это unique_ptr, узел является только перемещаемым: вы не можете случайно скопировать цепь, и у каждого звена ровно один владелец. Именно такую гарантию и хочет список.