Скотт Мейерс - Эффективное использование STL

// отсортирован по возрастанию!

По умолчанию binary_searchпредполагает, что интервал, в котором производится поиск, отсортирован оператором <(то есть по возрастанию), но в приведенном примере вектор сортируется по убыванию. Как нетрудно догадаться, вызов binary_search(или lower_boundи т. д.) для интервала, порядок сортировки которого отличен от ожидаемого, приводит к непредсказуемым последствиям.

Чтобы программа работала правильно, алгоритм binary_searchдолжен использовать ту же функцию сравнения, которая использовалась при вызове sort:

bool a5Exists = binаry_search(v.begin(), v.end(), 5, greater());

Все алгоритмы, работающие только с сортированными интервалами (то есть все алгоритмы, упоминавшиеся в данном совете, кроме uniqueи unique_copy), проверяют совпадение по критерию эквивалентности, как и стандартные ассоциативные контейнеры (которые также сортируются). С другой стороны, uniqueи unique_copyпо умолчанию проверяют совпадение по критерию равенства, хотя при вызове этим алгоритмам может передаваться предикат, определяющий альтернативный смысл «совпадения». За подробной информацией о различиях между равенством и эквивалентностью обращайтесь к совету 19.

Одиннадцать алгоритмов требуют передачи сортированных интервалов для того, чтобы обеспечить повышенную эффективность, невозможную без соблюдения этого требования. Передавайте им только сортированные интервалы, помните о соответствии двух функций сравнения (передаваемой алгоритму и используемой при сортировке) и вы избавитесь от хлопот при проведении поиска, слияния и операций с множествами, а алгоритмы uniqueи unique_copyбудут удалять все дубликаты — чего вы, вероятно, и добивались.

Один из вопросов, часто задаваемых новичками в STL — «Как в STL сравниваются строки без учета регистра символов?» Простота этого вопроса обманчива. Сравнения строк без учета регистра символов могут быть очень простыми или очень сложными в зависимости от того, насколько общим должно быть ваше решение. Если игнорировать проблемы интернационализации и ограничиться строками, на которые была рассчитана функция strcmp, задача проста. Если решение должно работать со строками в языках, не поддерживаемых strcmp(то есть практически в любом языке, кроме английского), или программа должна использовать нестандартный локальный контекст, задача чрезвычайно сложна.

В этом совете рассматривается простой вариант, поскольку он достаточно наглядно демонстрирует роль STL в решении задачи (более сложный вариант связан не столько с STL, сколько с проблемами локального контекста, упоминаемыми в приложении A). Чтобы простая задача стала интереснее, мы рассмотрим два возможных решения. Программисты, разрабатывающие интерфейсы сравнения строк без учета регистра, часто определяют два разных интерфейса: первый по аналогии с strcmpвозвращает отрицательное число, ноль или положительное число, а второй по аналогии с оператором <возвращает trueили false. Мы рассмотрим способы реализации обоих интерфейсов вызова с применением алгоритмов STL.

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

int ciCharCompare(char c1, char c2) // Сравнение символов без учета {

{ // регистра. Функция возвращает -1,

// если c1 < c2, 0, если c1 = c2, и 1,

// если c1 > c2.

int lc1 = tolower(static_cast(c1)); // См. Далее

int lс2 = tolower(static_cast(c2));

if (lc1 < lc2) return -1;

if (lc1 > lc2) return 1;

return 0;

};

Функция ciCharCompareпо примеру strcmpвозвращает отрицательное число, ноль или положительное число в зависимости от отношения между c1и c2. В отличие от strcmp, функция ciCharCompareперед сравнением преобразует оба параметра к нижнему регистру. Именно так и достигается игнорирование регистра символов при сравнении.

Параметр и возвращаемое значение функции tolower, как и у многих функций , относятся к типу int, но эти числа (кроме EOF) должны представляться в виде unsigned char. В C и C++ тип charможет быть как знаковым, так и беззнаковым (в зависимости от реализации). Если тип charявляется знаковым, гарантировать его возможное представление в виде unsigned charможно лишь одним способом: преобразованием типа перед вызовом tolower, этим и объясняется присутствие преобразований в приведенном выше фрагменте (в реализациях с беззнаковым типом charпреобразование игнорируется). Кроме того, это объясняет сохранение возвращаемого значения tolowerв переменной типа intвместо char.