Двунаправленный список ( list ) по своей внутренней структуре (рис. 26.1)принципиально отличается от вектора и дека. Каждый элемент двунаправленного списка кроме значений, помещаемых в контейнер, содержит ссылки (указатели) на предыдущий и последующий элементы. Такая организация позволяет вставлять и удалять данные не только в начало и конец списка, но и в произвольное место в нём с одной и той же скоростью.
Рис. 26.1 Двунаправленный список
Списки не поддерживают итераторы произвольного доступа, в них не определены ни оператор индексирования [ ], ни метод at(). Список – структура данных последовательного доступа. Для обращения к i-тому элементу списка необходимо перебрать все предшествующие (i-1) элемент. В связи с этим списки не поддерживают работу с некоторыми алгоритмами. В частности, со списком не может быть реализован алгоритм сортировки, однако список имеет собственные методы сортировки.
Операции со списками приведены по группам в табл. 26.1 – 26.7.
Таблица 26.1
Конструкторы, деструктор
Операция | Назначение |
list<T> lst | Конструктор по умолчанию, создает пустой список |
list<T> lst1(lst) | Копирующий конструктор, создает новый список как копию спискаlst(копируются все элементы) |
list<T> lst1=lst | Копирующий конструктор, создает новый список как копию спискаlst(копируются все элементы) |
list<T> lst(n) | Создает список изn элементов, созданных конструктором их типа по умолчанию |
list<T> lst(n,elem) | Создает список, инициа-лизированный n копиями элемента elem |
list<T> lst(beg,end) | Создает список, инициа-лизированный элементами интервала[beg,end) любого контейнера, в том числе и из элементов простого массива |
list<T> lst(initlist) | Создает список, инициа-лизированный элементами списка инициализации initlist (стандарт С++ 11) |
list<T> lst=initlist | Создает список, инициа-лизированный элементами списка инициализации initlist (стандарт С++ 11) |
lst.~list() | Уничтожает все элементы списка и освобождает память |
Таблица 26.2