C++. Сборник рецептов

Когсуэлл Джефф

Для удаления элементов из начала или конца

list

используйте

pop_front

или

pop_back

(без аргументов). Несмотря на их имя, методы «pop» не возвращают извлекаемый элемент, как это можно ожидать, исходя из обычной семантики стеков.

Обычно

list

выглядит так, как показано на рис. 6.2. Каждый узел содержит (по меньшей мере) три части: объект, в нем содержащийся, указатель на предыдущий узел и указатель на следующий узел. В оставшейся части рецепта я буду ссылаться на указатели на следующий и предыдущий узлы как

next_

и

prev_

.

Рис. 6.2.

Список с двунаправленными связями

Когда вы увидите, как реализован

list

, станет очевидно, почему некоторые операции имеют сложность, отличную от их сложности для

vector

. Добавление элемента в любое место

list

требует только изменения указателей

next_

и

prev_

предыдущего и следующего элементов. Приятным моментом в

list

является то, что при вставке и удалении элементов в помощью

insert

и

erase

устаревают значения только тех итераторов, которые указывают на затрагиваемый(е) объект(ы). Итераторы для других элементов не теряют актуальности.

Методы вставки и удаления — это

insert

и

erase

,

insert

в качестве первого аргумента принимает итератор, а в качестве второго — либо объект типа

T

, либо количество и затем объект типа

T

, либо начальный и конечный итераторы. Первый аргумент-итератор указывает на элемент, непосредственно перед которым должна произойти вставка. Перегрузки

insert

используются вот так.

list<string> strlst;

list<string>::iterator p;

// ...

string s = "Scion";

p = find(strLst.begin, strLst.end, // std::find из <algorithm>

 "Toyota");

strLst.insert(p, s); // Вставить s сразу перед p

strLst.insert(p, 16, s); // Вставить 16 копий s непосредственно перед p

strLst insert(p, myOtherStrLst.begin, // Вставить все, что содержится

 myOtherStrLst.end); // в myOtherStrLst, перед p

Удаление элементов аналогично.

p = find(strLst.begin, strLst.end, // std::find из <algorithm>

 "Toyota");

strLst1.erase(p); // Удаляем этот элемент

strLst2.erase(p, strLst.end); // Удаляем от p до конца

strLst3.clear; // Удаляем все элементы

В дополнение к методам стандартных контейнеров

list

предоставляет несколько своих. Первый — это

splice

.

splice

делает то, что означает его имя: он объединяет два

list

в один. Вот как можно объединить

lstTwo

с

lstOne

из примера 6.5.

list<string>::iterator p = // Находим, куда вставить второй

 std::find(lstOne.begin, // список

lstOne.end, "Green");

lstOne.splice(p, lstTwo); // Вставляем lstTwo непосредственно перед "Green"

p

— это итератор, который указывает на элемент в

lstOne

.

lstTwo

вставляется в

lstTwo

непосредственно перед

p

. Как и в случае со вставкой, все, что здесь требуется сделать, — это изменить указатели

next_

и

prev_

соответствующих узлов, так что эта операция занимает постоянное время. После объединения

lstTwo

с

lstOne

первый очищается, и именно поэтому этот параметр не объявлен как

const

. Также можно вставить в

lstOne

один элемент или диапазон элементов из

lstTwo

. В обоих случаях элементы, объединяемые с другим списком, удаляются из первоначального.

Если списки отсортированы (

list

содержит свой собственный метод

sort

,

std::sort

с

list

не работает) и требуется объединить их в один, сохранив их порядок, то вместо

splice

используйте

merge

.

merge

объединяет два списка в один, и если два элемента оказываются одинаковыми, то в конечную версию попадает элемент из

lstOne

. Как и в случае со

splice

, список, переданный в качестве аргумента, по окончании объединения очищается.

Также

list

содержит несколько удобных операций для удаления элементов. Представьте, что вам требуется удалить все вхождения какого-либо элемента. Все, что для этого требуется сделать, это вызвать

remove

, передав такой аргумент, который при сравнении с элементами

list

будет давать

(*p == item) != false

, где

p

— это итератор

list

.

remove

вызывается вот так.

strLst.remove("Harry");

В результате из

strLst

будут удалены все элементы, у которых

el == "Harry"

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

remove_if

.

bool inline even(int n) {

 return(n % 2 == 0);

}

list<int> intLst;

// Fill up intLst...

intLst.remove_if(even); // Удаляет все элементы, для которых even(*p)

// != false

Если предикаты более сложные, то попробуйте использовать какие-то из функторов из

<functional>

. Например, если требуется удалить элементы, которые больше определенного значения, используйте в

remove_if

объединение из

greater

(из

<algorithm>

) и

bind2nd

.

intLst.remove_if(std::bind2nd(std::greater<int>, 2));

В результате этого из

intLst

будут удалены все значения, которые больше 2. Эта запись несколько необычна, но ничего сложного в ней нет.

bind2nd

принимает два аргумента — объект функции (назовем ее

f

) и значение (

v

) — и возвращает объект функции, который принимает один аргумент (

arg

) и вызывает

f(arg, v)

.

bind2nd

— это простой способ делать подобные вещи без необходимости писать набор небольших функций.