Ежедневный бит (е) C ++ # 140, связанные списки C ++ в задачах интервью.
Сегодня мы немного отойдем от типичного расписания содержания интервью и вместо проблемы собеседования рассмотрим немного теории и поговорим о связанных списках.
Хотя в практических приложениях связанные списки встречаются редко, в интервью они часто появляются. Отчасти это связано с тем, что структура узлов позволяет формулировать сложные задачи, подобные деревьям и графам, без дополнительной топологической сложности.
std::list и std::forward_list
Стандартная библиотека предлагает два типа списков: std::list — двусвязный список и std::forward_list — односвязный список. Прямой список существует в первую очередь как оптимизация пространства, экономя 8 байтов на элемент в 64-битных архитектурах.
Оба обеспечивают идеальную стабильность итераторов и ссылок, т. е. единственная операция, которая делает недействительными итераторы или ссылки, — это стирание элемента и только для удаленного элемента. Стабильность распространяется даже на перемещение элементов между списками.
#include <list>
std::list<int> first{1,2,3};
std::list<int> second{4,5,6};
// Get iterator to the element with value 2
auto it = std::next(first.begin());
// Move the element to the begining of the second list
second.splice(second.begin(), first, it);
// first == {1, 3}, second == {2,4,5,6}
// iterator still valid
// *it == 2
Откройте пример в Compiler Explorer.
Стабильность итератора — это один из вариантов использования std::list или std::forward_list в практических приложениях. Единственной разумной альтернативой было бы обертывание каждого элемента в std::unique_ptr, что обеспечивает стабильность ссылок (но не стабильность итератора) независимо от контейнера-оболочки.
#include <vector> #include <memory> std::vector<std::unique_ptr<int>> stable; stable.push_back(std::make_unique<int>(1)); stable.push_back(std::make_unique<int>(2)); stable.push_back(std::make_unique<int>(3)); // get a stable weak reference (or pointer) to an element int *it = stable[1].get(); stable.erase(stable.begin()); // invalidates all iterators // it still valid, *it == 2
Откройте пример в Compiler Explorer.
Конечно, за эту стабильность мы платим производительностью. Связанные списки — это контейнеры на основе узлов, что означает, что каждый элемент размещается в отдельном узле, потенциально очень удаленном друг от друга в памяти. Когда мы объединяем это с неотъемлемыми издержками косвенного обращения, обход std::list может регулярно заканчиваться в 5–10 раз медленнее, чем эквивалентный плоский std::vector.
Помимо стабильности итератора, мы также получаем доступ к набору операций O(1), которые потенциально могут перевесить накладные расходы, присущие std::list.
#include <list>
std::list<int> data{1,2,3,4,5};
// O(1) splicing between lists, or within one list
// effectively rotate left by one element
data.splice(data.end(), data, data.begin());
// data == {2,3,4,5,1}
// O(1) erase
// iterator to element with value 4
auto it = std::next(data.begin(), 2);
data.erase(it);
// data == {2,3,5,1}
// O(1) insertion
// effectively push_front()
data.insert(data.begin(), 42);
// data = {42,2,3,5,1}
Откройте пример в Compiler Explorer.
Мы не можем использовать некоторые стандартные алгоритмы, потому что std::list предоставляет только двунаправленные итераторы, а std::forward_list — только прямые итераторы. Оба списка предоставляют пользовательские реализации сортировки, уникального, объединения, обратного, удаления. и remove_if в качестве функций-членов.
#include <list>
std::list<int> data{1,2,3,4,5};
data.reverse();
// data = {5,4,3,2,1}
data.sort();
// data = {1,2,3,4,5}
data.remove_if([](int v) { return v % 2 == 0; });
// data == {1,3,5}
Откройте пример в Compiler Explorer.
У std::forward_list есть еще одна особенность; поскольку мы можем стирать и вставлять только после итератора, std::forward_list предлагает модифицированный интерфейс.
#include <forward_list>
std::forward_list<int> data{1,2,3,4,5};
// before_begin() iterator
auto it = data.before_begin();
// insert and erase only possible after the iterator
data.insert_after(it, 42);
// data == {42,1,2,3,4,5}
data.erase_after(it);
// data == {1,2,3,4,5}
Откройте пример в Compiler Explorer.
Пользовательские списки
При реализации простого пользовательского связанного списка у вас может возникнуть соблазн использовать простую реализацию с использованием std::unique_ptr.
#include <memory>
struct Node {
int value;
std::unique_ptr<Node> next;
};
std::unique_ptr<Node> head = std::make_unique<Node>(20,nullptr);
head->next = std::make_unique<Node>(42,nullptr);
// head->value == 20
// head->next->value == 42
Откройте пример в Compiler Explorer.
К сожалению, этот подход неприменим. Основная проблема здесь — дизайн. Мы смешиваем право собственности со структурной информацией. В данном случае эта проблема проявляется при разрушении. Поскольку мы связали владение со структурой, уничтожение списка будет рекурсивным, что может привести к исчерпанию стека и сбою.
#include <memory>
struct Node {
int value;
std::unique_ptr<Node> next;
};
{
std::unique_ptr<Node> head = std::make_unique<Node>(0,nullptr);
// Depending on the architecture/compiler, the specific number
// of elements we can handle without crash will differ.
Node* it = head.get();
for (int i = 0; i < 100000; ++i)
it = (it->next = std::make_unique<Node>(0,nullptr)).get();
} // BOOM
Откройте пример в Compiler Explorer.
Если нам нужны как операции O(1), так и стабильность итератора, единственный вариант — полагаться на ручное управление ресурсами (в этот момент мы могли бы также использовать std::list или std::forward_list).
Если мы хотим зафиксировать структуру связанного списка со стабильностью ссылок, мы можем положиться на вышеупомянутую комбинацию std::vector и std::unique_ptr.
#include <vector>
#include <memory>
struct List {
struct Node {
int value;
Node* next;
};
Node *head = nullptr;
Node *new_after(Node* prev, int value) {
nodes_.push_back(std::make_unique<Node>(value, nullptr));
if (prev == nullptr)
return head = nodes_.back().get();
else
return prev->next = nodes_.back().get();
}
private:
std::vector<std::unique_ptr<Node>> nodes_;
};
List list;
auto it = list.new_after(nullptr, 1);
it = list.new_after(it, 2);
it = list.new_after(it, 3);
// list.head->value == 1
// list.head->next->value == 2
// list.head->next->next->value == 3
Откройте пример в Compiler Explorer.
Принципиальное отличие от предыдущего подхода заключается в том, что списку принадлежат все узлы, а структура кодируется только с использованием слабых указателей.
Наконец, если нам не нужны стабильные итераторы или ссылки, но требуются операции O(1), мы можем использовать метод плоского списка. Мы можем хранить все узлы непосредственно в std::vector. Единственной проблемной операцией в этом случае является erase(), которая по своей сути является линейной для std::vector.
Однако связанный список уже по своей сути кодирует порядок элементов, поэтому вместо стирания с середины std::vector мы всегда можем стереть с конца, заменив местами удаляемый элемент. с последним элементом в std::vector.
#include <vector>
inline constexpr ptrdiff_t nill = -1;
struct List {
struct Node {
int value;
ptrdiff_t next;
ptrdiff_t prev;
};
ptrdiff_t new_after(ptrdiff_t prev, int value) {
storage.push_back({value, nill, prev});
if (prev != nill)
storage[prev].next = std::ssize(storage)-1;
else
head = std::ssize(storage)-1;
return std::ssize(storage)-1;
}
void erase(ptrdiff_t idx) {
// move head
if (idx == head)
head = storage[idx].next;
// unlink the erased element
if (storage[idx].next != nill)
storage[storage[idx].next].prev = storage[idx].prev;
if (storage[idx].prev != nill)
storage[storage[idx].prev].next = storage[idx].next;
// relink the last element
if (idx != std::ssize(storage)-1) {
if (storage.back().next != nill)
storage[storage.back().next].prev = idx;
if (storage.back().prev != nill)
storage[storage.back().prev].next = idx;
}
// swap and O(1) erase
std::swap(storage[idx],storage.back());
storage.pop_back();
}
ptrdiff_t get_head() { return head; }
Node& at(ptrdiff_t idx) { return storage[idx]; }
private:
ptrdiff_t head = nill;
std::vector<Node> storage;
};
List list;
ptrdiff_t idx = list.new_after(nill, 1);
idx = list.new_after(idx, 2);
idx = list.new_after(idx, 3);
idx = list.new_after(idx, 4);
idx = list.new_after(idx, 5);
// list == {1,2,3,4,5}
idx = list.get_head();
list.erase(idx);
// list == {2,3,4,5}
Откройте пример в Compiler Explorer.
Основные операции
При разработке решения проблемы кодирования три наиболее частые операции со связанными списками:
- объединить два отсортированных списка
- перевернуть отсортированный список
- сканирование с двумя итераторами
И std::list, и std::forward_list имеют встроенную операцию слияния.
#include <list>
#include <forward_list>
{
std::list<int> left{2,4,5};
std::list<int> right{1,3,9};
left.merge(right);
// left == {1,2,3,4,5,9}
// right == {}
}
{
std::forward_list<int> left{2,4,5};
std::forward_list<int> right{1,3,9};
left.merge(right);
// left == {1,2,3,4,5,9}
// right == {}
}
Откройте пример в Compiler Explorer.
Тем не менее, реализовать его с нуля также не особенно сложно. Мы потребляем объединенный список по одному элементу за раз, перемещая позицию вставки по мере необходимости.
#include <forward_list>
std::forward_list dst{1, 3, 5, 6};
std::forward_list src{2, 4, 7};
auto dst_it = dst.begin();
while (!src.empty()) {
if (std::next(dst_it) == dst.end() ||
*std::next(dst_it) >= src.front()) {
dst.splice_after(dst_it, src, src.before_begin());
} else {
++dst_it;
}
}
// dst == {1,2,3,4,5,6,7}
// src == {}
Откройте пример в Compiler Explorer.
Та же ситуация применима и к обращению списка. Оба списка предоставляют встроенную обратную операцию с настраиваемой реализацией, даже более простой, чем слияние.
#include <forward_list>
std::forward_list<int> src{1,2,3,4,5,6,7};
std::forward_list<int> dst;
while (!src.empty())
dst.splice_after(dst.before_begin(), src, src.before_begin());
// dst == {7,6,5,4,3,2,1}
// src == {}
dst.reverse();
// dst == {1,2,3,4,5,6,7}
Откройте пример в Compiler Explorer.
Наконец, сканирование с использованием двух итераторов — распространенный метод поиска последовательности элементов, соответствующих определенному свойству. Пока это свойство вычисляется строго из элементов, входящих и исходящих из последовательности, нам не нужно обращаться к элементам, которые в данный момент находятся в последовательности.
#include <forward_list>
std::forward_list<int> data{4,2,1,1,1,3,5};
// find the longest subsequence with sum less than 4
// two iterators denoting the sequence [left, right)
auto left = data.begin();
auto right = data.begin();
int sum = 0;
int len = 0;
int max = 0;
while (right != data.end()) {
// extend right, until we break the property
while (sum < 4 && right != data.end()) {
max = std::max(max, len);
++len;
sum += *right;
++right;
}
// shrink from left, until the property is restored
while (sum >= 4 && left != right) {
sum -= *left;
--len;
++left;
}
}
// max == 3, i.e. {1,1,1}
