Скотт Мейерс - Эффективное использование STL

auto_ptr pw1(new Widget); //pw1 ссылается на Widget

auto_ptr pw2(pw1); //pw2 ссылается на объект Widget,

//принадлежащий pw1; pw1 присваивается

//NULL (таким образом, объект Widget

//передается от pw1 к pw2)

pwl = pw2; //pw1 снова ссылается на Widget:

//pw2 присваивается NULL

Конечно, такое поведение необычно и даже по-своему интересно, но для пользователя STL в первую очередь важно то, что оно приводит к крайне неожиданным последствиям. Рассмотрим внешне безобидный фрагмент, который создает вектор auto_ptrи сортирует его функцией, сравнивающей значения Widget:

bool WidgetAPCompare(const auto_ptr& lhs, const auto_ptr& rhs) {

return *lhs < *rhs; // Предполагается, что для объектов Widget

// существует оператор <

}

vector > widgets; // Создать вектор и заполнить его

… // указателями auto_ptr на Widget.

// Помните, что этот фрагмент

// не должен компилироваться!

sort(widgets.begin(), widgets.end(), // Отсортировать вектор

widgetAPCompare);

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

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

template

class Compare> // прямо из Стандарта

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) {

// typedef описывается ниже

typedef typename iterator_traits::value_type ElementType;

RandomAccessIterator i;

... // Присвоить i указатель на опорный элемент

ElementType pivotValue(*i);// Скопировать опорный элемент в локальную

... // временную переменную; см. далее комментарий.

// Остальная сортировка

}

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

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

ElementType pivotValue(*i);

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

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

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

Допустим, у нас имеется стандартный контейнер STL с, содержащий числа типа int:

контейнер с;

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