Списки (Лабораторная работа №1)

Списки

Список (если быть более точным – связанный список) - это структура данных, которая может хранить элементы списка в областях памяти с произвольным размещением. В отличие от векторов, списки не предоставляют такого количества способов произвольного доступа к своим элементам, как векторы, но с другой стороны, функции insert() и erase() исполняются очень быстро.

Большинство алгоритмов работы с векторами не применимы к спискам, в особенности это относится к функциям sort() и binary_search(), по причине того, что списки не обладают возможностью быстрого доступа к произвольному элементу. Сортировка STL-списков выполняется функцией sort().

Класс списка в STL называется как std::list<T>, и определен в заголовке <list>. Например: list<Film> films;

Новый элемент может быть добавлен в список вызовом функции push_back() или insert(). В отличие от векторов, вставка элемента в начало или в середину списка выполняется так же быстро, как и добавление элемента в конец списка.

В STL, списки не имеют оператора "[ ]", поэтому, для выбора нужного элемента приходится использовать итераторы. Синтаксис и порядок использования аналогичен векторам, например:

list<Film>::const_iterator it = films.begin();

while (it != films.end())

{

cerr << (*it).title().ascii() << endl;

++it;

}

Списки предоставляют практически тот же набор функций, что и векторы, включая empty(), size(), erase() и clear(). Функция find() также имеется.