Как поступить в этом случае? Если контейнер поймет, что
"Persephone" != "persephone"
, и вставит обе строки в
s
, в каком порядке они должны следовать?
Напомню, что функция сортировки эти строки не различает. Следует ли вставить строки в произвольном порядке, добровольно отказавшись от детерминированного порядка перебора содержимого контейнера? Недетерминированный порядок перебора уже присущ ассоциативным контейнерам
multiset
и
multimap
, поскольку Стандарт не устанавливает никаких ограничений на относительный
порядок следования эквивалентных значений (
multiset
) или ключей (
multimap
). Или нам следует настоять на детерминированном порядке содержимого
s
и проигнорировать вторую попытку вставки (для строки «persephone»)? А если будет выбран этот вариант, что произойдет при выполнении следующей команды:
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;
Строго говоря, это сокращенная запись для объявления