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

• Название: Эффективное использование STL
• Автор: Скотт Мейерс
• Издательство: Питер
• Жанр: Программирование
• Год: 2002
• ISBN: ISBN 5-94723-382-7

В этой книге известный автор Скотт Мейерс раскрывает секреты настоящих мастеров, позволяющие добиться максимальной эффективности при работе с библиотекой STL.

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

---

Если заменить *i в цикле на **i, возможно, вы получите нужный результат — но скорее всего, этого не произойдет. Да, строки будут выведены, но вероятность их следования в алфавитном порядке равна всего 1 /24. Контейнер ssp хранит свои элементы в отсортированном виде, однако он содержит указатели, поэтому сортироваться будут значения указателей, а не строки. Существует 24 возможных перестановки для четырех указателей, то есть 24 разных последовательности, из которых лишь одна отсортирована в алфавитном порядке[2].

Подходя к решению этой проблемы, нелишне вспомнить, что объявление

set<string*> ssp;

представляет собой сокращенную запись для объявления

set<string*.less<string*> > ssp;

Строго говоря, это сокращенная запись для объявления

set<string*.less<string*>.allocator<string*> > ssp;

но в контексте данного совета распределители памяти несущественны.

Если вы хотите сохранить указатели string* в контейнере set так, чтобы их порядок определялся значениями строк, стандартный функтор сравнения less<string*> вам не подойдет. Вместо этого необходимо написать собственный функтор сравнения, который получает указатели string* и упорядочивает их по содержимому строк, на которые они ссылаются. Пример:

struct StringPtrLess:

public binary_function<const string*, // Базовый класс

const string*, // описан в совете 40

bool> {

bool operator() (const string *ps1, const string *ps2) const

{

return *ps1<*ps2:

}

};.

После этого StringPtrLess используется в качестве типа критерия сравнения ssp:

typedef set<string*, StringPtrLess> StringPtrSet;

StringPtrSet ssp; // Создать множество с объектами string

// и порядком сортировки, определяемым

// критерием StringPtrLess

// Вставить те же четыре строки

Теперь приведенный выше цикл будет работать именно так, как предполагалось (при условии, что ошибка была исправлена и вместо *i используется **i).

for(StringPtrSet::const _iterator i = ssp.begin();

i != ssp.end();// Порядок вывода:

++i) // "Anteater", "Lemur",

cout«**i«endl; // "Pengun". "Wombat"

Если вы предпочитаете использовать алгоритм, напишите функцию, которая разыменовывает указатели string* перед выводом, а затем используйте ее в сочетании с for_each:

void print(const string *ps)// Вывести в cout объект.

{// на который ссылается ps

cout «*ps « endl;

}

for_each(ssp.begin(),ssp.end(),print); // Вызвать print для каждого

// элемента ssp

Существует более изощренное решение — обобщенный функтор разыменования, используемый с transform и ostream_iterator:

// Функтор получает Т* и возвращает const Т&

struct Dereference{

template<typename T>

const T& operator() (const T* ptr) const

{

return *ptr;

}

};

transform(ssp.begin(),ssp.end(),// "Преобразовать" каждый

ostream.iterator<string>(cout,"\n"). // элемент ssp посредством

Dereference());// разыменования и записать

// результаты в cout

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

Обратите внимание на термин «тип сравнения». Возможно, вас интересует, зачем возиться с созданием функтора вместо того, чтобы просто написать функцию сравнения для контейнера set? Например, так:

bool stringPtrLess(const string* psl, // Предполагаемая функция сравнения

const string* ps2) // для указателей string*.

{ // сортируемых по содержимому строки

return *psl<*ps2:

}

set<string.stringPtrLess> ssp; // Попытка использования stringPtrLess

// в качестве функции сравнения ssp.

// Не компилируется!!!

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

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

struct DereferenceLess {

template <typename PtrType>

bool operator()(PtrType pTl, // Параметры передаются по значению.

PtrType рТ2) const // поскольку они должны быть

{ // указателями (или по крайней мере

return *рТ1<*рТ2:// вести себя, как указатели)

}

};

Данный шаблон снимает необходимость в написании таких классов, как StringPtrLess, поскольку вместо них можно использовать DereferenceLess:

set<string*.DereferenceLess> ssp; // Ведет себя так же. как

// set<string*,stringPtrLess>

И последнее замечание. Данный совет посвящен ассоциативным контейнерам указателей, но он в равной степени относится и к контейнерам объектов, которые ведут себя как указатели (например, умные указатели и итераторы). Если у вас имеется ассоциативный контейнер умных указателей или итераторов, подумайте, не стоит ли задать тип сравнения и для него. К счастью, решение, приведенное для указателей, работает и для объектов-аналогов. Если определение DereferenceLess подходит в качестве типа сравнения для ассоциативного контейнера Т*, оно с большой вероятностью подойдет и для контейнеров итераторов и умных указателей на объекты Т.

Совет 21. Следите за тем, чтобы функции сравнения возвращали false в случае равенства

Сейчас я покажу вам нечто любопытное. Создайте контейнер set с типом сравнения less_equal и вставьте в него число 10:

set<int,less_equal<int> > s; // Контейнер s сортируется по критерию "<="

s.insert(10); // Вставка числа 10

Теперь попробуйте вставить число 10 повторно:

s.insert(10);

При этом вызове insert контейнер должен выяснить, присутствует ли в нем число 10. Мы знаем, что такое число уже есть, но контейнер глуп как пробка и все проверяет лично. Чтобы вам было проще понять, что при этом происходит, назовем первоначально вставленный экземпляр 10А, а новый экземпляр — 10в.

Контейнер перебирает свои внутренние структуры данных и ищет место для вставки 10в. В итоге ему придется проверить 10А и сравнить его с 10в. Для ассоциативного контейнера «сравнение» сводится к проверке эквивалентности (см. совет 19), поэтому контейнер проверяет эквивалентность объектов 10А и 10в. Естественно, при этой проверке используется функция сравнения контейнера set; в нашем примере это функция operator<=, поскольку мы задали функцию сравнения less_equal, a less_equal означает operator<=. Затем контейнер проверяет истинность следующего выражения:

!(10a<=10b)&&!(10b<=10a) // Проверка эквивалентности 10A и 10в

Оба значения, 10А и 10в, равны 10, поэтому условие 10А<=10В заведомо истинно. Аналогично истинно и условие 10В<=10А. Приведенное выше выражение упрощается до !(true) &&!(true), то есть false && false — результат равен false. Другими словами, контейнер приходит к выводу, что 10А и 10в не эквивалентны, и вставляет 10в в контейнер наряду с 10А. С технической точки зрения эта попытка приводит к непредсказуемым последствиям, но на практике в контейнере set появляются два экземпляра значения 10, а это означает утрату одного из важнейших свойств set. Передача типа сравнения less_equal привела к порче контейнера! Более того, любая функция сравнения, которая возвращает true для равных значений, приведет к тем же последствиям. Равные значения по определению не эквивалентны! Здорово, не правда ли?

Мораль: всегда следите за тем, чтобы функции сравнения для ассоциативных контейнеров возвращали false для равных значений. Будьте внимательны, поскольку это ограничение очень легко упустить из виду.

Например, в совете 20 рассказано о том, как написать функцию сравнения для контейнеров указателей string* обеспечивающую автоматическую сортировку содержимого контейнера по значениям строк, а не указателей. Приведенная функция сравнения сортирует строки по возрастанию, но давайте предположим, что вам понадобилась функция для сортировки по убыванию. Естественно, вы возьмете существующий код и отредактируете его. Но если не проявить достаточной осторожности, у вас может получиться следующий результат (изменения выделены жирным шрифтом):