Последовательности типа list
Контейнеры типа list представляют собой двусвязные списки, то есть упорядоченные последовательности, допускающие проходы как вперед, так и назад. Операции вставки и удаления одинаково эффективны в любое место списка. Однако операции поиска и выбора элементов линейны относительно размера контейнера. Выбор по индексу вовсе невозможен. Важным свойством списка является то, что операции вставки не портят итераторы, связанные с ним, а удаление делает недействительным только тот итератор, который указывал на удаленный элемент.
В шаблоне класса list определены методы merge, reverse, unique, remove и remove_if, которые оптимизированы для списков. Не путайте их с одноименными шаблонами функций, которые определены в алгоритмах. В примере, который приведен ниже, обратите внимание на операции слияния как списков, так и контейнеров различной природы. При исследовании списков не забудьте вставить директиву #include <list>, а также приведенный выше набор объектов класса Man:
void main 0
{
list<Man> men;
men.push_front(zorah);
men.push_back(mela);
men.push_back(joy);
pr(men,"Man List");
//======== Поиск объекта
list<Man>::iterator p = find (men.begin(),men.end(),mela);
//======== Вставка перед элементом
p = men.insert (p,joe);
// одного объекта men.insert(p,2,joe);
// двух объектов pr(men,"After inserting 3 joes");
//======== Удаление всех вхождений joe
men.remove(j oe);
men.sort(less<Man>());
pr(men,"After removing all joes and sort");
//======== Создаем второй список
list<Man> li(3,simon);
//======== Сливаем его с первым
.men.merge (li, less<Man>'());
pr(men,"After merging with simons list");
//==== После слияния второй список полностью исчез
cout " "\n\tAfter merging simons li.size: "
<< li.size() << endl;
men.remove(s imon);
//======== Создаем очередь
deque<Man> d(men.size());
//======== Копируем в нее список
copy(men.begin(), men.end(), d.begin());
pr(d,"Deque copied from list");
//======== Создаем вектор
vector<Man> v (men .size () + d.sizeO);
//==== Соединяем список и очередь и помещаем в вектор
merge(men.begin(),men.end(),d.begin(),d.end(), v.begin());
pr(v,"Vector after merging list and deque");
pr(d,"Deque after merging with list");
cout <<"\n\n";
}
После слияния (merge) двух списков (men и li) размер второго списка стал нулевым, так как он полностью влился в первый. При слиянии методом list:emerge элементы не копируются, а вливаются в список-мишень операции. При слиянии с помощью алгоритма merge контейнеры операнды остаются невредимыми, так как они копируются в контейнер-мишень. Если операнды операции слияния упорядочены, то при слиянии методом list::merge упорядоченность не нарушается, чего не наблюдается при слиянии шаблоном функции merge.