Эффективное использование 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> с;//с - один из стандартных

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

АссоцКонтейнер<int> goodValues: // Временный контейнер для хранения

// элементов, оставшихся после удаления

remove_copy_if(c.begin, c.end, // Скопировать оставшиеся элементы

 inserter(goodValues, // из с в goodValues

 goodValues.end), badValue);

с.swap(goodValues);// Поменять содержимое с и goodValues

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

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

remove_if

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

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