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

bool WidgetAPCompare(const auto_ptr<Widget>& lhs, const auto_ptr<Widget>& rhs) {
 return *lhs < *rhs; // Предполагается, что для объектов Widget
 // существует оператор <
}
vector<auto_ptr<Widget> > widgets; // Создать вектор и заполнить его
… // указателями auto_ptr на Widget.
 // Помните, что этот фрагмент
 // не должен компилироваться!
sort(widgets.begin, widgets.end, // Отсортировать вектор
 widgetAPCompare);

Пока все выглядит вполне разумно, да и с концептуальной точки зрения все действительно разумно — но результат разумным никак не назовешь. Например, в процессе сортировки некоторым указателям auto_ptr, хранящимся в Widget, может быть присвоено значение NULL. Сортировка вектора приводит к изменению его содержимого! Давайте разберемся, как это происходит.

Оказывается, реализация sort часто строится на некой разновидности алгоритма быстрой сортировки. Работа этого алгоритма строится на том, что некоторый элемент контейнера выбирается в качестве «опорного», после чего производится рекурсивная сортировка по значениям, большим и меньшим либо равным значению опорного элемента. Реализация такого алгоритма в sort может выглядеть примерно так:

template<class RandomAccessIterator, // Объявление sort скопировано
 class Compare> // прямо из Стандарта
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) {
 // typedef описывается ниже
 typedef typename iterator_traits<RandomAccessIterator>::value_type ElementType;
 RandomAccessIterator i;
 ... // Присвоить i указатель на опорный элемент
 ElementType pivotValue(*i); // Скопировать опорный элемент в локальную
 ... // временную переменную; см. далее комментарий.
 // Остальная сортировка
}

Если вы не привыкли читать исходные тексты STL, этот фрагмент выглядит жутковато, но в действительности в нем нет ничего страшного. Нетривиально здесь выглядит только запись iterator_traits<RandomAccessIterator>::value_type, но это всего лишь принятое в STL обозначение типа объекта, на который указывают итераторы, переданные sort. Перед ссылкой iterator_traits<RandomAccessIterator>::value_type должен стоять префикс typename, поскольку это имя типа, зависящее от параметра шаблона (в данном случае RandomAccessIterator), — дополнительная информация приведена на с. 20.

Проблемы возникают из-за следующей команды, которая копирует элемент из сортируемого интервала в локальный временный объект:

ElementType pivotValue(*i);

В данном случае элементом является auto_ptr<Widget>, поэтому в результате скопированному указателю auto_ptr (тому, который хранится в векторе) присваивается NULL. Более того, когда pivotValue выходит из области видимости, происходит автоматическое удаление объекта Widget, на который pivotValue ссылается. Итак, после вызова sort содержимое вектора изменяется и по меньшей мере один объект Widget удаляется. Вследствие рекурсивности алгоритма быстрой сортировки существует вероятность того, что сразу нескольким элементам вектора будет присвоено значение NULL и сразу несколько объектов Widget будут удалены, поскольку опорный элемент копируется на каждом уровне рекурсии.

Подобные ловушки весьма зловредны, и Комитет по стандартизации постарался, чтобы вы заведомо не попадались в них. Уважайте их труд и никогда не создавайте контейнеры 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).