Daily bit(e) C++. std::list, std::forward_list

Daily bit(e) C++ #214, структуры данных для представления связанных списков: std::list и std::forward_list.

std::list и std::forward_list – это контейнеры с идеальной стабильностью итераторов и поддержкой объединения контейнеров элементов со сложностью O(1).

Единственная ситуация, которая делает итератор недействительным, – это удаление элементов, и только для удаленных элементов, даже при сращивании между контейнерами.

Следовательно, перемещение std::list и std::forward_list происходит примерно в 5–10 раз медленнее, чем std::vector.

#include <list>
#include <forward_list>

std::list<int> data{1,2,3,4,5};
std::list<int> other{6,7,8,9};

// Получить итератор на третий элемент.
// Обратите внимание, что это линейная операция:
// т.е. auto it = std::next(std::next(data.begin()));
auto it = std::next(data.begin(), 2);

// Передать третий элемент из data перед первым элементом other
other.splice(other.begin(), data, it); // операция O(1)
// он всё еще действителен, *it == 3
// data == {1, 2, 4, 5}, other == {3, 6, 7, 8, 9}

// std::list обеспечивает поддержку только двунаправленных итераторов,
// а std::forward_list - только однонаправленных операторов.

// Но оба предоставляют распространенные алгоритмы в качестве методов:
std::forward_list<int> list{5,2,1,4,3};

list.sort(); // примерно n*logn
// list == {1, 2, 3, 4, 5}

list.reverse(); // O(n)
// list == {5, 4, 3, 2, 1}

// std::forward_list предоставляет необычный интерфейс из-за структуры
// однонаправленного списка (можно вставлять/удалять только после элемента).
list.insert_after(list.before_begin(), 42); // O(1)
// то же, что и list.push_front(42);
// list == {42, 5, 4, 3, 2, 1}

list.erase_after(list.begin()); // O(1)
// list == {42, 4, 3, 2, 1}

Открыть пример на Compiler Explorer.

Теги