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

Мейерс Скотт

if (s.find("persephone") != s.end)… // Каким будет результат проверки?

Функция

find

использует проверку равенства, но если проигнорировать второй вызов

insert

для сохранения детерминированного порядка элементов

s

, проверка даст отрицательный результат — хотя строка «persephone» была отвергнута как дубликат!

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

сравнения. Поначалу такой подход выглядит несколько странно (особенно когда вы видите, что внутренняя и внешняя версии

find

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

Но стоит отойти от сортированных ассоциативных контейнеров, как ситуация изменяется, и проблему равенства и эквивалентности приходится решать заново. Существуют две общепринятые реализации для нестандартных (но широко распространенных) ассоциативных контейнеров на базе хэш-таблиц. Одна реализация основана на равенстве, а другая — на эквивалентности. В совете 25 приводится дополнительная информация об этих контейнерах и тех принципак, на которых они основаны.

Совет 20. Определите тип сравнения для ассоциативного контейнера, содержащего указатели

Предположим, у нас имеется контейнер

set

, содержащий указатели

string*

, и мы пытаемся включить в него несколько новых элементов:

set<string*> ssp; // ssp = "set of string ptrs"

ssp.insert(new string("Anteater"));

ssp.insert(new string("Wombat"));

ssp.insert(new string("Lemur"));

ssp.insert(new string("Penguin"));

Следующий фрагмент выводит содержимое

set

. Предполагается, что строки будут выведены в алфавитном порядке — ведь содержимое контейнеров

set

автоматически сортируется!

for (set<string*>::const_iterator i = ssp.begin; // Предполагаемый

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

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

 cout << *i << endl; // "Penguin", "Wombat"

Однако на практике ничего похожего не происходит. Вместо строк выводятся четыре шестнадцатеричных числа — значения указателей. Поскольку в контейнере

set

хранятся указатели,

*i

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

copy

:

copy(ssp.begin, ssp.end, // Скопировать строки.

 ostream_iterator<string>(cout,"\n")); //содержащиеся в ssp, в cout

//(не компилируется!)

не только делает программу более компактной, но и помогает быстрее обнаружить ошибку, поскольку вызов

copy

не компилируется. Итератор

ostream_iterator

должен знать тип выводимого объекта, поэтому когда компилятор обнаруживает расхождение между заданным в параметре шаблона типом

string

и типом объекта, хранящегося в

ssp(string*)

, он выдает ошибку. Еще один довод в пользу сильной типизации…

Если заменить

*i

в цикле на

**i

, возможно, вы получите нужный результат — но скорее всего, этого не произойдет. Да, строки будут выведены, но вероятность их следования в алфавитном порядке равна всего 1/24. Контейнер

ssp

хранит свои элементы в отсортированном виде, однако он содержит указатели, поэтому сортироваться будут значения указателей, а не строки. Существует 24 возможных перестановки для четырех указателей, то есть 24 разных последовательности, из которых лишь одна отсортирована в алфавитном порядке [2] .

2

Строго говоря, не все 24 перестановки равновероятны, так что вероятность 1/24 не совсем точна. Тем не менее, остается бесспорный факт: существуют 24 разные перестановки, и вы можете получить любую из них.

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

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