Совет 19. Помните о различиях между равенством и эквивалентностью

Совет 19. Помните о различиях между равенством и эквивалентностью

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

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

class Widget {

public:

private:

TimeStamp lastAccessed;

};

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

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

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

}

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

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

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

&& // и

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

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

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

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

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

// а у не предшествует х

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

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

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

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

binary_function<string,string,bool>{ // описание базового класса

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

bool operator() (const string& lhs,

const string& 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.end(),

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

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

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

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

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

set2CF<string.CIStringCompare,equal_to<string> > s;

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

s.insert("Persephone");

s.insert("persephone");

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

Напомню, что функция сортировки эти строки не различает. Следует ли вставить строки в произвольном порядке, добровольно отказавшись от детерминированного порядка перебора содержимого контейнера? Недетерминированный порядок перебора уже присущ ассоциативным контейнерам multiset и multimap, поскольку Стандарт не устанавливает никаких ограничений на относительный порядок следования эквивалентных значений (multiset) или ключей (multimap). Или нам следует настоять на детерминированном порядке содержимого s и проигнорировать вторую попытку вставки (для строки «persephone»)? А если будет выбран этот вариант, что произойдет при выполнении следующей команды:

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

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

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

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

15.1.2 Соотношения между NFS, RPC и XDR

Из книги автора

15.1.2 Соотношения между NFS, RPC и XDR NFS работает поверх вызовов удаленных процедур (Remote Procedure Call — RPC). RPC был разработан в начале использования приложений клиент/сервер. В этой главе мы познакомимся со службами NFS и архитектурой открытых сетевых вычислений (Open Network Computing — ONC), на


Помните: в Интернете пользователь может делать все, что захочет

Из книги автора

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


3.4. Отношения между классами

Из книги автора

3.4. Отношения между классами Типы отношений Рассмотрим сходства и различия между следующими классами: цветы, маргаритки, красные розы, желтые розы, лепестки и божьи коровки. Мы можем заметить следующее: • Маргаритка - цветок. • Роза - (другой) цветок. • Красная и желтая


Совет 10. Помните о правилах и ограничениях распределителей памяти

Из книги автора

Совет 10. Помните о правилах и ограничениях распределителей памяти Распределители памяти первоначально разрабатывались как абстракция для моделей памяти, позволяющих разработчикам библиотек игнорировать различия между near- и far-указателями в некоторых 16-разрядных


Совет 15. Помните о различиях в реализации string

Из книги автора

Совет 15. Помните о различиях в реализации string Бьерн Страуструп однажды написал статью с интригующим названием «Sixteen Ways to Stack a Cat» [27], в которой были представлены разные варианты реализации стеков. Оказывается, по количеству возможных реализаций контейнеры string не уступают


Совет 31. Помните о существовании разных средств сортировки

Из книги автора

Совет 31. Помните о существовании разных средств сортировки Когда речь заходит об упорядочении объектов, многим программистам приходит в голову всего один алгоритм: sort (некоторые вспоминают о qsort, но после прочтения совета 46 они раскаиваются и возвращаются к мыслям о


Совет 34. Помните о том. какие алгоритмы получают сортированные интервалы

Из книги автора

Совет 34. Помните о том. какие алгоритмы получают сортированные интервалы Не все алгоритмы работают с произвольными интервалами. Например, для алгоритма remove (см. советы 32 и 33) необходимы прямые итераторы и возможность присваивания через эти итераторы. Таким образом,


Совет 50. Помните о web-сайтах, посвященных STL

Из книги автора

Совет 50. Помните о web-сайтах, посвященных STL Интернет богат информацией об STL. Если ввести в любой поисковой системе запрос «STL», вы получите сотни ссылок, часть из которых даже будет содержать полезную информацию. Впрочем, большинство программистов STL в поисках не нуждается


Переключение между формами

Из книги автора

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


Дмитрий Шабанов: О различиях между полами Дмитрий Шабанов

Из книги автора

Дмитрий Шабанов: О различиях между полами Дмитрий Шабанов Опубликовано 11 мая 2011 года Недавно я сравнивал три основных типа размножения и кратко разбирался, почему воспроизводство с рекомбинацией благодаря половому процессу «лучше» (эволюционно


Как переключаться между окнами?

Из книги автора

Как переключаться между окнами? Компьютер способен одновременно выполнять несколько приложений. Каждое из них выводит на экран свое окно. Значки этих окон отображаются на Панели задач.Чтобы переключаться между запущенными программами, вы можете щелкать мышью на их


2.2.1. Переключение между окнами

Из книги автора

2.2.1. Переключение между окнами Windows является многозадачной операционной системой. То есть вы можете работать одновременно в нескольких программах и переключаться между ними. Объясняю, как это делается. Итак, сейчас у вас открыто окно Мой компьютер, сверните его на панель


Отдых между спринтами

Из книги автора

Отдых между спринтами В реальной жизни невозможно постоянно бежать как спринтер. Между забегами вам в любом случае нужен отдых. Если вы бежите с постоянной максимальной скоростью, то, по сути, вы просто бежите трусцой.То же самое наблюдается в Scrum’е, да и в разработке


Соглашение между УЦ и РЦ

Из книги автора

Соглашение между УЦ и РЦ Это соглашение охватывает все стороны отношений между УЦ и РЦ. Если УЦ и РЦ являются компонентами модели инсорсинга, то соглашение между ними упрощается и приобретает статус внутреннего юридического соглашения между УЦ (обычно работающим под