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

Для удаления элементов в списках предусмотрены специализированные версии алгоритмов removeO (см. с. 371). Эти функции работают быстрее алгоритмов removeO, потому что используют вместо элементов только внутренние указатели. Следовательно, в отличие от векторов или деков операцию remove() для списков следует вызывать в форме функции класса, а пе алгоритма (см, с. 163). Чтобы удалить все элементы с заданным значением, воспользуйтесь следующей конструкцией (за подробностями обращайтесь на с. 127):

std: :list<Elem> соП;

Удаление всех элементов со значением val col 1.removeCval):

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

Функция removejf позволяет определить критерий удаления элементов в виде функции или объекта функции. Она удаляет каждый элемент, для которого передаваемая операция возвращает true. Пример использования remove if() для удаления всех элементов с четными значениями:

11st.remove if (notl(bind2nd(modulus<int>().2))):

Если команда кажется непонятной, не огорчайтесь. Подробности приводятся на с. 306, а дополнительные примеры использования функций remove() и removeJf() можно найти на с. 372.

Функции врезки

Как отмечалось выше, одним из достоинств связанных списков является возможность удаления и вставки элементов в произвольной позиции с постоянным временем. При перемещении элементов из одного контейнера в другой это достоинство проявляется еще сильнее, потому что операция вьшолняется переназначением нескольких внутренних указателен (рис. 6.5).

Рис. 6.5. Операции врезки изменяют порядок следования элементов списка

Для обеспечения этой возможностп спискам необходимы дополнительные модифицирующие фушкции, которые бы изменяли порядок следования и мро-

Функция remove if() обычно неработоспособна в системах, пе поддерживающих шаблонные функции классов.

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

Таблица 6.18. Специальные операции модификации списков

Операция

Описание

c.uniqueO c.unique(op)

cl.splice(pos,c2) cl.splice(pos,c2,c2pos)

cl.splice(pos,c2c2beg,c2end)

c.sortO

c.sort(op)

cl.merge(c2)

cl.merge(c2,op)

c.reverse()

Удаляет дубликаты (элементы с одинаковыми значениями)

Удаляет дубликаты (элементы с одинаковыми значениями), для которых ор возвращает true

Перемещает все элементы с2 в с1 перед поэицией итератора pos

Перемещает все элементы с2, начиная с позиции итератора c2pos, в список с1 перед позицией итератора pes

Перемещает все элементы интервала [c2beg,c2end) списка с2 перед позицией итератора pes в список с1 (с1 и с2 могут совпадать)

Сортирует все элементы оператором <

Сортирует все элементы по критерию ор

Перемещает все элементы с2 в с1 с сохранением сортировки (предполагается, что оба контейнера содержат отсортированные элементы)

Перемещает все элементы с2 в с1 с сохранением сортировки по ор() (предполагается, что оба контейнера содержат элементы, отсортированные по критерию ор())

Переставляет все элементы в обратном порядке

Обработка исключений

Из всех стандартных контейнеров STL списки наиболее надежны в отношении исключений. Практически все операции над списками либо завершаются успешно, либо не вносят изменений. Такая гарантия не предоставляется только операторами присваивания и функцией sort() (они дают лишь обычную базовую гарантию отсутствия утечки ресурсов и нарушения контейнерных инвариантов при возникновении исключений). Функции merge(), remove(), remove if() и unique() предоставляют гарантии при условии, что исключения не будут сгенерированы при сравнении элементов оператором == или предикатом. Таким образом, в терминологии программирования баз данных можно сказать, что списки обладают тралзакциоипой безопасностью, если не использовать операцию присваивании и функцию sort(), а также проследить за тем, чтобы исключения пе генерировались при сравнении. В табл. 6.19 перечислены все операции, предоставляющие специальные гарантии в отношении исключений. Обработка исключений в STL более подробно рассматривается на с. 148.

Таблица 6.19. Операции над списками, предоставляющие особые гаранши в отношении исклк>чений

Операция Описание

push back() Либо завершается успешно, либо не вносит изменений

push front() Либо завершается успешно, либо не вносит изменений

insert() Либо завершается успешно, либо не вносит изменений

рор Ьаск() Не генерирует исключений

pop front() Не генерирует исключений

eraseO Не генерирует исключений

ciearQ Не генерирует исключений

resizeO Либо завершается успешно, либо не вносит изменений

removeO генерирует исключений, если они не будут сгенерированы при сравнении

элементов

removeJfO Не генерирует исключений, если они не будут сгенерированы предикатом

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

spiiceO Не генерирует исключений

mergeO Либо завершается успешно, либо не вносит изменений (если исключения

не будут сгенерированы при сравнении элементов)

reverse() Не генерирует исключений

swapO Не генерирует исключений

Примеры использования списков

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

cont/l1stl,cpp #1nclude <iostredm> #1nclude <l1st> #include <dlgorithrr> using namespace std;

void printLlsts (const list<int>& U, const llst<1nt>& 12) {

cout 11stl: :

copy (11.beginO, ll.endO. ostream iterator<int>(cout. )); cout endl 11st2; ;

copy (12.beginO, 12,end(), ostream 1terator<1nt>(cout. )): cout endl endl;

Int mainO