позиции происходит за постоянное время, а недостаток заключается в отсутствии произвольного доступа к элементам. Список STL может быть просто реализован в виде двусвязного списка, как показано на рисунке 3.3. Поскольку каждый узел этого списка содержит ссылку на предыдущий и последующий узлы, операции - и ++ для итераторов будут выполняться эффективно, то есть за постоянное время. Напротив, передвижение от узла к узлу, отстоящему на п позиций в списке, потребует времени 0(п).

Рисунок 3.3. Двусвязный список

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

Если узлы добавляются в список, все итераторы, ссылающиеся на узлы этого списка, продолжают оставаться действительными; как мы знаем, для векторов и двусторонних очередей это правило не соблюдается.

Многие функции-члены, такие как конструкторы и функции вставки, используются так же, как и функции векторов и двусторонних очередей, но, как мы только что упоминали, для списка добавление элементов занимает постоянное время. У списка отсутствует оператор доступа по индексу [], ведь доступ по индексу связан с итераторами произвольного доступа, а итераторы списка только двунаправленные.

Функции-члены sort и unique

В разделе 1.4 было сказано, что алгоритм sort не работает со списками. Вместо этого для списков определена функция-член sort. Другой специфичной для списка функцией-членом является unique, которая удаляет повторяющиеся последовательные элементы. Эти две функции определены в классе list таким образом:

void sort(); void unique();

Следующая программа демонстрирует использование этих функций:

listl.cpp: Функции-члены класса list: sort и unique. #include <iostream> iinclude <list> using namespace std;

void out(char *s, const list<int> &L) { cout s;

copy(L.begin() , L.endO,

ostream iterator<int>(cout, ));

cout endl;

int mainO

{ list<int> L(5, 123); L.push back(100) L.push back(123) L.push back(123) out( Initial contents: , L) L.unique();

out( After L.unique(): , L) L.sort();

out ( After L.sortO : , L) return 0;

Вывод этой программы показывает, что функция unique учитывает только последовательные элементы, в результате получается два элемента 123: один до и другой после элемента 100.

Initial contents: 123 123 123 123 123 100 123 123 After L.unique О: 123 100 123 After L.sortO : 100 123 123

Если бы мы вызвали две функции-члена в другом порядке

L.sortO; L.uniqueO; окончательный результат содержал бы всего два элемента

100 123 Сцепка

Другая операция, специфичная для списков,- сцепка (splicing), перемещение одного или более последовательных элементов из одного списка в другой, без освобождения либо выделения памяти для этих элементов. Существуют три функции-члена splice, которые объявлены в классе list так, как показано ниже. В сопутствующем обсуждении ЬиМ означают список одного и того же типа:

void splice(iterator position, list<T>& x);

Если i является допустимым итератором для L, следующая операция вставляет содержимое М перед i в список L и оставляет М пустым. Эта операция не работает, если ЬиМ являются одним и тем же списком:

L.splice(i, М); void splice(iterator position, list<T>& x, iterator j);

Если i является допустимым итератором для L, aj - таковым для М, следующая операция удаляет элемент, на который ссылается j, и вставляет его перед г. Эта операция работает, даже если L и М являются одним и тем же списком:

L.splice (i , М, j);

void splice(iterator position, list<T>& x, iterator first, iterator last);

Если i является допустимым итератором для L, а \ji,j2) является допустимым диапазоном для М, следующая операция удаляет элементы этого диапазона и вставляет их перед i в L. Эта операция также работает, если L иМявляются одним и тем же списком:

L.spliced, М, jl, j2) ;

Мы покажем, как работает последняя из функций splice, изменив список так, как изображено на рисунке 3.4.

J1 J2 i

Л-- *

10 ( 20 30 40) 50 60 70 80

Рисунок 3.4. Сцепка

Элементы 20, 30, 40 из последовательности 10, 20, 30, 40, 50, 60, 70, 80 перемещаются на новое место между 60 и 70. Результатом является последовательность

10 50 60 20 30 40 70 80

которая совпадает с выводом нижеследующей программы:

splice.срр: Сцепка, iinclude <iostream> iinclude <list> using namespace std;