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

Совет 21. Следите за тем, чтобы функции сравнения возвращали false в случае равенства

Совет 21. Следите за тем, чтобы функции сравнения возвращали false в случае равенства

Сейчас я покажу вам нечто любопытное. Создайте контейнер set с типом сравнения less_equal и вставьте в него число 10:

set<int, less_equal<int> > s; // Контейнер s сортируется по критерию "<="
s.insert(10); // Вставка числа 10

Теперь попробуйте вставить число 10 повторно:

s.insert(10);

При этом вызове insert контейнер должен выяснить, присутствует ли в нем число 10. Мы знаем, что такое число уже есть, но контейнер глуп как пробка и все проверяет лично. Чтобы вам было проще понять, что при этом происходит, назовем первоначально вставленный экземпляр 10_A, а новый экземпляр — 10B.

Контейнер перебирает свои внутренние структуры данных и ищет место для вставки 10B. В итоге ему придется проверить 10_A и сравнить его с 10B. Для ассоциативного контейнера «сравнение» сводится к проверке эквивалентности (см. совет 19), поэтому контейнер проверяет эквивалентность объектов 10_A и 10B. Естественно, при этой проверке используется функция сравнения контейнера set; в нашем примере это функция operator<=, поскольку мы задали функцию сравнения less_equal, a less_equal означает operator<=. Затем контейнер проверяет истинность следующего выражения:

!(10a<=10b)&&!(10b<=10a) // Проверка эквивалентности 10A и 10B

Оба значения, 10_A и 10B, равны 10, поэтому условие 10_A<=10B заведомо истинно. Аналогично истинно и условие 10B<=10_A. Приведенное выше выражение упрощается до !(true)&&!(true), то есть false&&false — результат равен false. Другими словами, контейнер приходит к выводу, что 10_A и 10Bне эквивалентны, и вставляет 10B в контейнер наряду с 10_A. С технической точки зрения эта попытка приводит к непредсказуемым последствиям, но на практике в контейнере set появляются два экземпляра значения 10, а это означает утрату одного из важнейших свойств set. Передача типа сравнения less_equal привела к порче контейнера! Более того, любаяфункция сравнения, которая возвращает true для равных значений, приведет к тем же последствиям. Равные значения по определению неэквивалентны! Здорово, не правда ли?

Мораль: всегда следите за тем, чтобы функции сравнения для ассоциативных контейнеров возвращали false для равных значений. Будьте внимательны, поскольку это ограничение очень легко упустить из виду.

Например, в совете 20 рассказано о том, как написать функцию сравнения для контейнеров указателей string* обеспечивающую автоматическую сортировку содержимого контейнера по значениям строк, а не указателей. Приведенная функция сравнения сортирует строки по возрастанию, но давайте предположим, что вам понадобилась функция для сортировки по убыванию. Естественно, вы возьмете существующий код и отредактируете его. Но если не проявить достаточной осторожности, у вас может получиться следующий результат (изменения выделены жирным шрифтом):

struct StringPtrGreater:
 public binary_function<const string*, // Жирным шрифтом выделены
 const string*,                        // изменения, внесенные в код
 bool> {                               // из совета 20.
                                       // Внимание - приведенное решение
                                       // не работает!
 bool operator()(const string *ps1, const string *ps2) const {
  return !(*ps1 < *ps2); // Простое логическое отрицание
 }                       // старого условия не работает!
};

Идея заключается в том, чтобы изменить порядок сортировки логическим отрицанием условия в функции сравнения. К сожалению, отрицанием операции «<» является не «>», а «>=», а мы выяснили, что операция «>=», возвращающая true для равных значений, не подходит для функции сравнения в ассоциативных контейнерах.

Правильный тип сравнения должен выглядеть так:

struct StringPtrGreater:               // Правильный тип сравнения
 public binary_function<const string*, // для ассоциативных контейнеров
 const string*, bool> {
 bool operator() (const string *ps1, const string *ps2) const {
  return *ps2<*ps1;// Поменять местами операнды
 }
};

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

Я знаю, о чем вы думаете. «Конечно, это имеет смысл для set и map, поскольку эти контейнеры не могут содержать дубликатов. А как насчет multiset и multimap? Раз эти контейнеры могут содержать дубликаты, так ли важно, что два объекта с одинаковыми значениями окажутся не эквивалентными? Сохраним оба, для этого и нужны mult-контейнеры. Верно?»

Нет, неверно. Давайте вернемся к исходному примеру, но на этот раз воспользуемся контейнером multiset:

multiset<int, less_equal<int> > s; // s сортируется по критерию "<="
s.insert(10);// Вставка числа 10A
s.insert(10);// Вставка числа 10B

Теперь s содержит два экземпляра числа 10, и было бы логично предположить, что при вызове equal_range мы получим пару итераторов, описывающих интервал с обеими копиями. Однако это невозможно. Функция equal_range, несмотря на свое название, определяет интервал не равных, а эквивалентныхзначений. В нашем примере функция сравнения s говорит, что 10_A и 10B не эквивалентны, поэтому они не могут оказаться в интервале, определяемом функцией equal_range.

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

Строго говоря, функции сравнения, используемые для сортировки ассоциативных контейнеров, должны определять для сравниваемых объектов порядок строгой квазиупорядоченности (strict weak ordering); аналогичное ограничение действует и для функций сравнения, передаваемых алгоритмам, — таким, как sort (см. совет 31). Если вас заинтересуют подробности того, что понимается под строгой квазиупорядоченностью, информацию можно найти во многих серьезных руководствах по STL, в том числе «The C++ Standard Library» [3], «Generic Programming аnd the STL» [4] и на web-сайте SGI, посвященном STL [21]. Особых откровений не ждите, но одно из требований строгой квазиупорядоченности относится непосредственно к данному совету. Требование заключается в следующем: функция, определяющая строгую квазиупорядоченность, должна возвращать false при получении двух копий одного значения.

Оглавление книги