Алгоритм find и функция set::insert являются типичными представителями семейства функций, проверяющих совпадение двух величин, однако делают это они по-разному. Для find совпадением считается равенство двух величин, проверяемое оператором =. Функция set:: insert проверяет отношение эквивалентности, обычно основанное на операторе <. Таким образом, по одному определению два объекта могут иметь одинаковые значения, тогда как по другому определению они будут различаться. Отсюда следует, что для эффективного использования STL необходимо понимать различия между равенством и эквивалентностью.

Формальное определение равенства основано на использовании оператора =. Если результат выражения х=у равен true, значит, х и у имеют одинаковые значения, а если f al se - разные. В целом определение весьма прямолинейное, хотя следует помнить о том, что из равенства значений не следует равенство всех полей данных. Предположим, класс Widget хранит внутренние данные о времени последнего обращения:

class Widget { public:

private: TimeStamp lastAccessed:

Для класса Widget можно определить оператор ==, игнорирующий значение этого поля:

bool operator==(const WidgetS Ihs, const WidgetS rhs) {

Поле lastAccessed игнорируется

В этом слзае два объекта Widget будут считаться равными даже в том случае, если их поля 1 astAccessed содержат разные значения.

Эквивалентность основана на относительном порядке значений объектов в отсортированном интервале. Проще всего рассматривать ее в контексте порядка сортировки, являющегося частью любого стандартного ассоциативного контейнера (то есть set, multiset, map и multimap). Два объекта х и у считаются эквивалентными по отношению к порядку сортировки, используемому ассоциативным контейнером с, если ни один из них не предшествует другому в порядке сортировки с. На первый взгляд такая формулировка кажется запутанной, но на практике все просто. Возьмем контейнер set<Widget> s. Два объекта Widget, wl и w2, имеют эквивалентные значения по отношению к s, если ни один из них не предшествует другому в порядке сортировки s. Стандартная функция сравнения для set<Widget> - 1ess<Widget> - по умолчанию просто вызывает operator< для объектов Widget, поэтому wl и w2 будут иметь значения, эквивалентные по отношению к operator<, если истинно следующее выражение:

!(wl<w2) Условие wl < w2 ложно

&& и

!(w2<wl) Условие w2 < wl ложно

Все вполне логично: два значения эквивалентны (по отношению к некоторому критерию упорядочения), если ни одно из них не предшествует другому в соответствии с данным критерием.

В общем слзае функцией сравнения для ассоциативного контейнера является не оператор < или даже 1 ess, а пользовательский предикат (см. совет 39). Каждый стандартный ассоциативный контейнер предоставляет свой предикат сортировки через функцию кеу сотр, поэтому два объекта х и у имеют эквивалентные значения по отношению к критерию сортировки ассоциативного контейнера с, если выполняется следующее условие:

!c.key conip()(x.y)&&!c.key conip()(y,x) х не предшествует у

в порядке сортировки с. а у не предшествует х

Выражение !c.key coinp()(x,y) выглядит устрашающе, но стоит понять, что с.кеу сотр() возвращает функцию (или объект функции), как все затруднения исчезают. Перед нами простой вызов функции (или объекта функции), возвращаемой кеу сотр, которой передаются аргументы х и у. Затем вычисляется логическое отрицание результата. Функция с. keycomp () (х, у) возвращает true лишь в том слзае, если х предшествует у в порядке сортировки, поэтому выражение ! с. кеу сотр () (х, у) истинно только в том слзае, если х не предшествует у в порядке сортировки с.

Чтобы вы лзше осознали принципиальный характер различий между равенством и эквивалентностью, рассмотрим пример - контейнер set<string> без зета регистра символов, то есть контейнер set<string>, в котором функция сравнения игнорирует регистр символов в строках. С точки зрения такой функции строки STL и stL эквивалентны. Пример реализации функции ciStringCompare, игнорирующей регистр символов, приведен в совете 35, однако set требуется тип функции сравнения, а не сама функция. Чтобы заполнить этот пробел, мы пишем класс функтора с оператором О, вызывающим ciStringCompare:

struct CiStringCompare: Класс сравнения строк

public без учета регистра символов;

binary function<string.string.Ьоо1>{ описание базового класса

приведено в совете 40

bool operatorO (const strings Ihs,

const strings rhs) const

return ciStringCompare(lhs,rhs); Реализация ciStringCompare

приведена в совете 35

При наличии CiStringCompare контейнер set<string>, игнорирующий регистр символов, создается очень просто:

set<string,CIStringCompare> ciss:

Теперь при вставке строк Persephone и persephone в множество будет включена только первая строка, поскольку вторая считается эквивалентной:

ciss.insert( Persephone ): В множество включается новый элемент ciss.insert( persephone ): Эквивалентный элемент не включается

Если теперь провести поиск строки persephone функцией set::find, результат будет успешным:

if(ciss.find( persephone )!=ciss.end())... Элемент найден

Но если воспользоваться внешним алгоритмом find, поиск завершается неудачей:

if(find(ciss.begin(), ciss.endO.

persephone )!=ciss.end())... Элемент отсутствует

Дело в том, что строка persephone эквивалентна Persephone (по отношению к функтору сравнения ClStringCompare), но неравна ей (поскольку string ( persephone ) !=string( Persephone )). Приведенный пример поясняет одну из причин, по которой в соответствии с советом 44 рекомендуется использовать функции контейнеров (set:: find) вместо их внешних аналогов (find).

Возникает вопрос - почему же в работе стандартных ассоциативных контейнеров используется понятие эквивалентности, а не равенства? Ведь большинству программистов равенство кажется интуитивно более понятным, чем эквивалентность (в противном случае данный совет был бы лишним). На первый взгляд ответ кажется простым, но чем дольше размышляешь над этим вопросом, тем менее очевидным он становится.

Стандартные ассоциативные контейнеры сортируются, поэтому каждый контейнер должен иметь функцию сравнения (по умолчанию less), определяющую порядок сортировки. Эквивалентность определяется в контексте функции сравнения, поэтому клиентам стандартных ассоциативных контейнеров остается лишь задать единственную функцию сравнения. Если бы ассоциативные контейнеры при сравнении объектов использовали критерий равенства, то каждому ассоциативному контейнеру, помимо используемой при сортировке функции сравнения, пришлось бы определять вторую функцию для проверки равенства. Вероятно, по умолчанию функция сравнения вызывала бы equal to, но интересно заметить, что функция equal to в STL не используется в качестве стандартной функции сравнения. Когда в STL возникает необходимость проверки равенства, по умолчанию просто вызывается оператор =. В частности, именно так поступает внешний алгоритм find.

Допустим, у нас имеется контейнер set2CF, построенный по образцу set - set с двумя функциями сравнения . Первая функция сравнения определяет порядок сортировки элементов множества, а вторая используется для проверки равенства. А теперь рассмотрим следующее объявление:

set2CF<string.ClStringCompare,equal to<string> > S;

Контейнер s производит внзггреннюю сортировку строк без зета регистра, но с использованием интуитивного критерия равенства: две строки считаются равными при совпадении их содержимого. Предположим, в s вставляются два варианта написания строки Persephone :

S. i nsert( Persephone ); s.insert( persephone );

Как поступить в этом случае? Если контейнер поймет, что Persephone != persephone , и вставит обе строки в s, в каком порядке они должны следовать?