На этом шаге мы перечислим отличительные особенности списков.
По своей внутренней структуре списки полностью отличаются от векторов и деков. Важнейшие различия перечислены ниже.
- Список не поддерживает произвольный доступ к элементам. Например, чтобы обратиться к пятому элементу, необходимо перебрать первые четыре элемента по цепочке ссылок. Это означает, что обращение к произвольному элементу списка выполняется относительно медленно.
- Вставка и удаление элементов в любой позиции выполняются быстро, причем не только с концов контейнера. Вставка и удаление всегда выполняются с постоянным временем, поскольку не требуют перемещения других элементов. Во внутренней реализации изменяются только значения нескольких указателей.
- В результате вставки и удаления элементов указатели, ссылки и итераторы, относящиеся к другим элементам, остаются действительными.
- Обработка исключений в списках реализована так, что практически каждая операция завершается успешно или не вносит изменений. Иначе говоря, список не может оказаться в промежуточном состоянии, в котором операция завершена только наполовину. Эти принципиальные различия отражены в функциях списков, что делает их непохожими на функции векторов и деков.
- Поскольку списки не поддерживают произвольный доступ к элементам, в них не определены ни оператор индексирования, ни функция at().
- Списки не поддерживают операции, связанные с емкостью и перераспределением памяти, потому что такие операции просто не нужны. У каждого элемента имеется собственная память, которая остается действительной до удаления элемента.
- Списки поддерживают много специальных функций для перемещения элементов. Эти функции класса представляют собой оптимизированные версии одноименных универсальных алгоритмов. Оптимизация основана на замене указателей вместо копирования и перемещения значений.
Со следующего шага мы начнем знакомиться с операциями над списками.
