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

Совет 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 s. Два объекта Widget, w1 и w2, имеют эквивалентные значения по отношению к s, если ни один из них не предшествует другому в порядке сортировки s. Стандартная функция сравнения для sett> — less — по умолчанию просто вызывает operator< для объектов Widget, поэтому wl и w2 будут иметь значения, эквивалентные по отношению к operator< если истинно следующее выражение:

!(w1

&& // и

!(w2

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

В общем случае функцией сравнения для ассоциативного контейнера является не оператор < или даже 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()(х, у) истинно только в том случае, если х не предшествует у в порядке сортировки с.