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

Контейнер перебирает свои внутренние структуры данных и ищет место для вставки 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* обеспечивающую автоматическую сортировку содержимого контейнера по значениям строк, а не указателей. Приведенная функция сравнения сортирует строки по возрастанию, но давайте предположим, что вам понадобилась функция для сортировки по убыванию. Естественно, вы возьмете существующий код и отредактируете его. Но если не проявить достаточной осторожности, у вас может получиться следующий результат (изменения выделены жирным шрифтом):

struct StringPtrGreater:

 public binary_function

 const string*,                        // изменения, внесенные в код

 bool> {                               // из совета 20.

                                       // Внимание - приведенное решение

                                       // не работает!

 bool operator(const string *ps1, const string *ps2) const {

  return !(*ps1 < *ps2); // Простое логическое отрицание

 }                       // старого условия не работает!

};

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

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

struct StringPtrGreater:               // Правильный тип сравнения

 public binary_function

 const string*, bool> {

 bool operator (const string *ps1, const string *ps2) const {

  return *ps2<*ps1;// Поменять местами операнды

 }

};

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

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

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

multiset > s; // s сортируется по критерию "<="

s.insert(10);// Вставка числа 10A

s.insert(10);// Вставка числа 10B