Списки
Списки — двусвязные линейные структуры данных, т. е. каждый элемент имеет два указателя для ссылки на два других элемента. Списки занимают ровно столько памяти, сколько необходимо для хранения наличных элементов. Вставка и удаление из списка очень эффективны. Слабым местом списка является доступ к элементам. Прямой доступ, как в векторах, невозможен. Для поиска нужного элемента приходится двигаться по списку, начиная с самого начала.
Создание списков
Существуют различные способы конструирования списков.
#include <list>
list<int>ilist;
list<double>dlist(20, 1.0);
list<MyType>mtlist(10) ;
Эти объявления имеют тот же смысл, что и соответствующие объявления для векторов. Так же как и вектор, список можно конструировать, инициализировав содержимым другого контейнера:
int iarr[5] = {1, 2, 3, 4, 5};
…
list<int> linti(iarr, iarr + 5);
В списке можно хранить любой тип данных, при условии, что он поддерживает те функции-элементы (конструкторы и проч.), о которых говорилось выше при обсуждении векторов.
Действия над списками
Поскольку список занимает ровно столько памяти, сколько необходимо, для него не имеет смысла понятие вместимости. Поэтому у списков нет функций capacity () и reserve (). Невозможно и обращение к элементам по индексу.
В остальном над списками можно производить все те операции, что описывались в предыдущем параграфе о векторах. Но следует упомянуть о некоторых дополнительных возможностях списков.
Помимо известных вам уже методов push back() и pop back (), имеются функции push_front () и pop_front () для добавления или удаления элемента в начале списка.
Функция remove () удаляет из списка все элементы с указанным значением.
Функция unique () удаляет все повторяющиеся элементы (стоящие;
подряд, поэтому функцию имеет смысл применять только на сортированных списках), оставляя только первое вхождение элемента с данным значением.
Функция reverse () обращает порядок элементов в списке.
Функция sort () (без аргумента) производит сортировку списка в соответствии с операцией “меньше”, т. е. в восходящем порядке. Можно задать в качестве аргумента функциональный объект, реализующий отношение, в соответствии с которым нужно сортировать список:
#intlude <functional> linti.sort(greater_equal<int>());

Функция sort() сохраняет относительный порядок следования повторяющихся элементов. Такого рода сортировку называют стабильной.
Функция merge () выполняет слияние сортированного списка с другим сортированным списком. Элементы второго списка удаляются. Как и в случае sort (), можно задать второй аргумент — функциональный объект, определяющий отношение сортировки.

Заметим, что списки нельзя сортировать с помощью стандартных алгоритмов, поскольку для них требуется прямой доступ к элементам контейнера.
Функция splice () является специальным вариантом вставки. Она удаляет вставляемый элемент или элементы списка, из которого производится вставка.
Описанные функции частично иллюстрирует следующая программа.
#include <iostream>
#include <list>
#pragma hdrstop
#include <condefs.h>
using namespace std;
//
// Операция передачи списка в поток.
//
template<class T>
ostream &operator“(ostream &os, const list<T> &c)
{
cout << "{ ";
copy (c. begin (), c.end(),
ostream_iterator<T> (os, " "));
os << "} Size: " “ c.size();
return os;
}
int main() {
int iarrl[5] = {5, 7, 3, 1, 9};
list<int> lintl(iarr1, iarr1 + 5);
cout<< "Initial list : "<< linti << endl;
linti.sort (); // Сортировка.
cout << "After sort : "<< lint1 << end1;
int iarr2[6] = {6, 2, 4, 8, 2, 6};
list<int> lint2(iarr2, iarr2 + 6);
cout << "Second list : " << lint2 << end1;
lint2.sort () ;
lint2.unique(); // Удаление повторов.
cout<< "Sorted unique: " << lint2 “ endl;
linti.merge(lint2); // Слияние.
cout <<"After merge : " << lint1 “ end1;
linti.reverse (); // Обращение порядка.
cout << "After reverse: "<< lint1 << end1;
return 0;
}
Программа выводит:
Initial list : {57319} Size: 5
After sort : {13579} Size: 5
Second list : {624826} Size: 6
Sorted unique:(2468) Size: 4
After merge :{123456789} Size:9
After reverse:{987654321}Size:9