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

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

Впрочем, не исключено, что переносимость вас не волнует. Если это так, позвольте напомнить об уникальном (а по мнению некоторых — нелепом) смысле операции копирования

auto_ptr
.

При копировании

auto_ptr
право владения объектом, на который ссылается указатель, переходит к копии, а исходному указателю присваивается NULL. Да, вы не ошиблись: копирование указателя auto_ptr приводит к его модификации.

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

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

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

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

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

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

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

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

auto_ptr<Widget>
и сортирует его функцией, сравнивающей значения Widget:

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
будут удалены, поскольку опорный элемент копируется на каждом уровне рекурсии.