Контейнер list в C++: урок для школьников с примерами STL

std::list — контейнер стандартной библиотеки C++, обычно устроенный как двусвязный список. Он подходит для учебных задач, где нужно вставлять и удалять отдельные элементы рядом с уже найденной позицией. Такая операция занимает O(1), если нужный итератор известен. Поиск позиции требует обхода и может занять O(n). Прямого доступа по индексу у list нет. В этом уроке для школьников разберём список на небольших примерах C++17: вставку, перенос узлов и сортировку.

Создание и обход

#include <list>
#include <iostream>

int main() {
    std::list<int> lst = {10, 20, 30};
    lst.push_back(40);        // 40 в конец
    for (int x : lst) {
        std::cout << x << ' ';
    }                          // выведет: 10 20 30 40
}

Обход работает через двунаправленные итераторы: операторы ++ и -- есть, а произвольный сдвиг на k позиций (ит += k) — нет, потому что узлы разбросаны по памяти и попасть в k-й можно только обходом.

Вставка и устойчивость итераторов

Вставка через insert не делает существующие итераторы и ссылки недействительными. При erase недействительными становятся только итераторы и ссылки на удалённые элементы. При splice итератор перенесённого элемента сохраняется и относится уже к принимающему списку. Эти правила нельзя автоматически переносить на присваивание или замену всего контейнера. Это принципиально отличает list от vector, где вставка в середину сдвигает элементы и делает старые итераторы недействительными.

Пример 1. Итератор переживает вставку. Код держит итератор на первый элемент, вставляет новый узел сразу после него — и итератор по-прежнему указывает на прежнее значение:

Следующие строки продолжают первую программу перед закрывающей скобкой main. Для std::next добавьте в начало файла #include <iterator>.

auto it = lst.begin();      // узел со значением 10
lst.insert(std::next(it), 15); // вставка между 10 и 20
// *it по-прежнему равно 10; список: 10 15 20 30 40
lst.erase(std::next(it));   // удаляем узел 15

splice: перенос узлов без копирования

Сигнатурная операция списка — splice: она «перешивает» указатели так, что узел переходит из одного списка в другой, значения элементов не копируются и не перемещаются конструкторами, а ссылки и итераторы на перенесённый элемент сохраняются. Для двух списков аллокаторы должны сравниваться равными; у обычных std::list<int> из примера это условие выполнено. При переносе диапазона внутри одного списка позиция вставки не должна находиться в переносимом диапазоне.

Пример 2. Перенос первого элемента. Этот фрагмент можно поместить внутрь main; нужны заголовки <list> и <iterator>.

std::list<int> a = {10, 15, 30, 40};
std::list<int> b = {7, 8};
a.splice(std::next(a.begin()), b, b.begin());
// a: 10 7 15 30 40
// b: 8

В результате список b содержит только 8, а a — последовательность 10, 7, 15, 30, 40. У splice есть и другие формы: перенос целого другого списка или диапазона [first, last). Перенос одного элемента и целого другого списка занимает O(1); перенос диапазона между разными списками может потребовать линейного времени по длине диапазона.

Сортировка и поиск

Алгоритм std::sort требует итераторов произвольного доступа, поэтому со списком он не работает — попытка std::sort(lst.begin(), lst.end()) не скомпилируется. Вместо него у list есть собственная член-функция lst.sort() (устойчивая сортировка, примерно n log n сравнений; конкретный алгоритм и расход дополнительной памяти здесь не предполагаются): после неё список {10, 7, 15, 30, 40} превращается в {7, 10, 15, 30, 40}. Для std::find нужен заголовок <algorithm>. Поиск значения — линейный std::find(lst.begin(), lst.end(), x) со сложностью O(n), а вот удаление всех вхождений значения lst.remove(x) — встроенная операция, которая тоже проходит по списку за O(n). Вставка или удаление диапазона зависит от количества вставленных или удалённых элементов, поэтому правило O(1) относится к одной операции над одним элементом при известной позиции. Из других член-функций списка полезны unique() (убирает соседние дубликаты), remove_if (удаление по условию) и merge (слияние двух списков, заранее отсортированных с тем же правилом сравнения; аллокаторы должны быть равны).

Когда list, а когда другой контейнер

Если нужен именно доступ по индексу и обход целиком — выбирают vector; если поток вставок и удалений в известных позициях — list. Похожая логика выбора структуры существует и в Java, где коллекции описаны в нашем материале об иерархии коллекций Java.

Упражнения

Задание 1

Почему выражение std::sort(lst.begin(), lst.end()) для std::list не скомпилируется?

Ответ 1: std::sort требует итераторы произвольного доступа (random access), а у list только двунаправленные. Для списка предусмотрена член-функция lst.sort().

Задание 2

Чему равен размер списка b в примере 2 после вызова splice?

Ответ 2: 1. Перенесён один узел (бывший первый элемент b, значение 7); в b остался только 8.

Задание 3

Что выведет обход списка a после полного примера 2 и вызова a.sort()?

Ответ 3: 7 10 15 30 40. Перед сортировкой список имел вид {10, 7, 15, 30, 40}; сортировка член-функцией упорядочивает значения по возрастанию.

Задание 4

Итератор it указывает на элемент списка. После lst.insert(std::next(it), 99) можно ли безопасно продолжать разыменовывать it?

Ответ 4: да. Вставка в list не инвалидирует существующие итераторы и ссылки — портится только итератор удалённого элемента. Узел, на который указывает it, остался на месте.

Задание 5

Нужно хранить 100000 целых чисел и 5000 раз обращаться к элементу с номером 50000. Подходит ли std::list?

Ответ 5: нет. Доступ к 50000-му элементу list — обход примерно 50000 узлов, то есть O(n) на каждое обращение; 5000 таких обращений — сотни миллионов шагов. Здесь нужен vector или deque с доступом за O(1); list оправдан, когда позиции известны итераторами и операции — вставки/удаления.

Источники и материалы

• C++ working draft: list.overview
• C++ working draft: list.modifiers
• C++ working draft: list.ops