Эффективное использование STL
вернуться

Мейерс Скотт
Шрифт:

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

auto_ptr
, даже если ваша платформа STL это позволяет.

Впрочем, это вовсе не исключает возможности создания контейнеров умных указателей. Контейнеры умных указателей вполне допустимы. В совете 50 описано, где найти умные указатели, хорошо работающие в контейнерах STL, просто

auto_ptr
не относится к их числу.

Совет 9. Тщательно выбирайте операцию удаления

Допустим, у нас имеется стандартный контейнер STL

с
, содержащий числа типа
int
:

контейнер<int> с;

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

Для блоковых контейнеров (

vector
,
deque
или
string
— см. совет 1) оптимальный вариант построен на использовании идиомы
erase-remove
(совет 32):

c.erase(remove(c.begin, c.end, 1963), // Идиома erase-remove хорошо

 c.end); // подходит для удаления элементов

// с заданным значением

// из контейнеров vector, string

//и deque

Приведенное решение работает и для контейнеров

list
, но как будет показано в совете 44, функция
remove
контейнера
list
работает эффективнее:

с.remove(1963); // Функция remove хорошо подходит для удаления

// элементов с заданным значением из списка

Стандартные ассоциативные контейнеры (такие как

set
,
multiset
,
map
и
multimap
) не имеют функции
remove
с именем
remove
, а использование алгоритма
remove
может привести к стиранию элементов контейнера (совет 32) и возможной порче его содержимого. За подробностями обращайтесь к совету 22, где также объясняется, почему вызовы remove для контейнеров
map/multimap
не компилируются никогда, а для контейнеров
set/multiset
— компилируются в отдельных случаях.

Для ассоциативных контейнеров правильным решением будет вызов

erase
:

c.erase(1963); // Функция erase обеспечивает оптимальное

// удаление элементов с заданным значением

// из стандартных ассоциативных контейнеров

Функция

erase
не только справляется с задачей, но и эффективно решает ее с логарифмической сложностью (вызовы
remove
в последовательных контейнерах обрабатываются с линейной сложностью). Более того, в ассоциативных контейнерах функция
erase
обладает дополнительным преимуществом — она основана на проверке эквивалентности вместо равенства (это важное различие рассматривается в совете 19).

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

true
:

bool badValue(int х); // Возвращает true для удаляемых объектов

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

vector
,
string
,
deque
и
list
) достаточно заменить
remove
на
remove_if
:

c.erase(remove_if(c.begin, c.end, badValue), // Лучший способ уничтожения

 c.end); // объектов, для которых badValue

// возвращает true, в контейнерах

// vector, string и deque

с.remove_if(badValue); // Оптимальный способ уничтожения

// объектов, для которых badValue

// возвращает true, в контейнере

// list

Со стандартными ассоциативными контейнерами дело обстоит посложнее. Существуют два решения: одно проще программируется, другое эффективнее работает. В первом решении нужные значения копируются в новый контейнер функцией

remove_copy
, после чего содержимое двух контейнеров меняется местами:

АссоцКонтейнер<int> с;//с - один из стандартных

… // ассоциативных контейнеров