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

Обратите внимание на термин «тип сравнения». Возможно, вас интересует, зачем возиться с созданием функтора вместо того, чтобы просто написать функцию сравнения для контейнера set? Например, так:

bool stringPtrLess(const string* ps1, // Предполагаемая функция сравнения
 const string* ps2)                   // для указателей string*,
{                                     // сортируемых по содержимому строки
 return *ps1 < *ps2;
}

set ssp; // Попытка использования stringPtrLess
                                // в качестве функции сравнения ssp.
// Не компилируется!!!

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

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

struct DereferenceLess {
 template
 bool operator()(PtrType pT1, // Параметры передаются по значению.
  PtrType рТ2) const          // поскольку они должны быть
 {                            // указателями (или по крайней мере
  return *рТ1 < *рТ2;         // вести себя, как указатели)
 }
};

Данный шаблон снимает необходимость в написании таких классов, как StringPtrLess, поскольку вместо них можно использовать DereferenceLess:

setDereferenceLess> ssp; // Ведет себя так же, как
                                   // set

И последнее замечание. Данный совет посвящен ассоциативным контейнерам указателей, но он в равной степени относится и к контейнерам объектов, которые ведут себя как указатели (например, умные указатели и итераторы). Если у вас имеется ассоциативный контейнер умных указателей или итераторов, подумайте, не стоит ли задать тип сравнения и для него. К счастью, решение, приведенное для указателей, работает и для объектов-аналогов. Если определение DereferenceLess подходит в качестве типа сравнения для ассоциативного контейнера T*, оно с большой вероятностью подойдет и для контейнеров итераторов и умных указателей на объекты T.

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

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

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

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

s.insert(10);

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

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

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

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

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

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