if (s.find("persephone") != s.end())... // Каким будет результат проверки?
Функция find использует проверку равенства, но если проигнорировать второй вызов insert для сохранения детерминированного порядка элементов s, проверка даст отрицательный результат — хотя строка «persephone» была отвергнута как дубликат!
Мораль: используя одну функцию сравнения и принимая решение о «совпадении» двух значений на основании их эквивалентности, мы избегаем многочисленных затруднений, возникающих при использовании двух функций сравнения. Поначалу такой подход выглядит несколько странно (особенно когда вы видите, что внутренняя и внешняя версии find возвращают разные результаты), но в перспективе он избавляет от всевозможных затруднений, возникающих при смешанном использовании равенства и эквивалентности в стандартных ассоциативных контейнерах.
Но стоит отойти от сортированных ассоциативных контейнеров, как ситуация изменяется, и проблему равенства и эквивалентности приходится решать заново. Существуют две общепринятые реализации для нестандартных (но широко распространенных) ассоциативных контейнеров на базе хэш-таблиц. Одна реализация основана на равенстве, а другая — на эквивалентности. В совете 25 приводится дополнительная информация об этих контейнерах и тех принципак, на которых они основаны.
Совет 20. Определите тип сравнения для ассоциативного контейнера, содержащего указатели
Предположим, у нас имеется контейнер set, содержащий указатели string*, и мы пытаемся включить в него несколько новых элементов:
set 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::const_iterator i = ssp.begin(); // Предполагаемый
i!=ssp.end();
++i)
cout <<*i << endl;
Однако на практике ничего похожего не происходит. Вместо строк выводятся четыре шестнадцатеричных числа — значения указателей. Поскольку в контейнере set хранятся указатели, *i является не строкой, а указателем на строку. Пусть этот урок напоминает, чтобы вы следовали рекомендациям совета 43 и избегали написания собственных циклов. Использование алгоритма сору:
copy(ssp.begin(),ssp.end(),// Скопировать строки.
ostream_iterator(cout,"\n")); //содержащиеся в ssp. в cout
//(не компилируется!)
не только делает программу более компактной, но и помогает быстрее обнаружить ошибку, поскольку вызов сору не компилируется. Итератор ostream_iterator должен знать тип выводимого объекта, поэтому когда компилятор обнаруживает расхождение между заданным в параметре шаблона типом string и типом объекта, хранящегося в ssp (string*), он выдает ошибку. Еще один довод в пользу сильной типизации...
Если заменить *i в цикле на **i, возможно, вы получите нужный результат — но скорее всего, этого не произойдет. Да, строки будут выведены, но вероятность их следования в алфавитном порядке равна всего 1 /24. Контейнер ssp хранит свои элементы в отсортированном виде, однако он содержит указатели, поэтому сортироваться будут значения указателей, а не строки. Существует 24 возможных перестановки для четырех указателей, то есть 24 разных последовательности, из которых лишь одна отсортирована в алфавитном порядке[2].
Подходя к решению этой проблемы, нелишне вспомнить, что объявление
set ssp;
представляет собой сокращенную запись для объявления
set> ssp;
Строго говоря, это сокращенная запись для объявления
set.allocator> ssp;
но в контексте данного совета распределители памяти несущественны.
Если вы хотите сохранить указатели string* в контейнере set так, чтобы их порядок определялся значениями строк, стандартный функтор сравнения less вам не подойдет. Вместо этого необходимо написать собственный функтор сравнения, который получает указатели string* и упорядочивает их по содержимому строк, на которые они ссылаются. Пример:
struct StringPtrLess:
public binary_function
const string*, // описан в совете 40
bool> {
bool operator() (const string *ps1, const string *ps2) const
{
return *ps1<*ps2:
}
};
.После этого StringPtrLess используется в качестве типа критерия сравнения ssp:
typedef set 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
const T&operator() (const T* ptr) const
{
return *ptr;
}
};
transform(ssp.begin(),ssp.end(),// "Преобразовать" каждый
ostream.iterator(cout,"\n"). // элемент ssp посредством
Dereference());// разыменования и записать
// результаты в cout
Впрочем, замена циклов алгоритмами будет подробно рассматриваться позднее, в совете 43. А сейчас речь идет о том, что при создании стандартного ассоциативного контейнера указателей следует помнить: содержимое контейнера будет сортироваться по значениям указателей. Вряд ли такой порядок сортировки вас устроит, поэтому почти всегда определяются классы-функторы, используемые в качестве типов сравнения.
Обратите внимание на термин «тип сравнения». Возможно, вас интересует, зачем возиться с созданием функтора вместо того, чтобы просто написать функцию сравнения для контейнера set? Например, так:
bool stringPtrLess(const string* psl, // Предполагаемая функция сравнения
const string* ps2) // для указателей string*.
{ // сортируемых по содержимому строки
return *psl<*ps2:
}
set ssp; // Попытка использования stringPtrLess
// в качестве функции сравнения ssp.
// Не компилируется!!!
Проблема заключается в том, что каждый из трех параметров шаблона set должен быть типом. К сожалению, stringPtrLess — не тип, а функция, поэтому попытка задать stringPtrLess в качестве функции сравнения set не компилируется. Контейнеру set не нужна функция; ему нужен тип, на основании которого можно создать функцию.
Каждый раз, когда вы создаете ассоциативный контейнер указателей, помните о том, что вам, возможно, придется задать тип сравнения контейнера. В большинстве случаев тип сравнения сводится к разыменованию указателя и сравнению объектов, как это сделано в приведенном выше примере StringPtrLess. Шаблон для таких функторов сравнения стоит держать под рукой. Пример:
struct DereferenceLess {
template