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

// данными, отсортировать

sort(v.begin(),v.end(),greater0): // по убыванию.

// Операции с вектором

// (не изменяющие содержимого).

bool a5Exists = // Поиск числа 5 в векторе.

binary_search(v.begin(),v.end(),5); // Предполагается, что вектор

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

По умолчанию 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, сколько с проблемами локального контекста, упоминаемыми в приложении А). Чтобы простая задача стала интереснее, мы рассмотрим два возможных решения. Программисты, разрабатывающие интерфейсы сравнения строк без учета регистра, часто определяют два разных интерфейса: первый по аналогии с strcmp возвращает отрицательное число, ноль или положительное число, а второй по аналогии с оператором < возвращает true или false. Мы рассмотрим способы реализации обоих интерфейсов вызова с применением алгоритмов STL.

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

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

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

// если cl

// если cl>c2.

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

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

if (lc1

if (lc1>lc2) return 1;

return 0;

};

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

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

При наличии chCharCompareпервая из двух функций сравнения строк (с интерфейсом в стиле strcmp) пишется просто. Эта функция, ciStringCompare, возвращает отрицательное число, ноль или положительное число в зависимости от отношения между сравниваемыми строками. Функция основана на алгоритме mismatch, определяющем первую позицию в двух интервалах, в которой элементы не совпадают.

Но для вызова mismatch должны выполняться некоторые условия. В частности, необходимо проследить за тем, чтобы более короткая строка (в случае строк разной длины) передавалась в первом интервале. Вся настоящая работа выполняется функцией ciStringCompareImp, а функция ciStringCompareлишь проверяет правильность порядка аргументов и меняет знак возвращаемого значения, если аргументы пришлось переставлять:

int ciStringCompareImpl(const string& si, // Реализация приведена далее

const string& s2);

int ciStringCompare(const string& s1,const string& s2) {

if (s1.size()<=s2.size() return cStringCompareImpl(s1,s2);

else return -ciStringComparelmpl(s2,s1);

}

Внутри ciStringCompareImplвсю тяжелую работу выполняет алгоритм mismatch. Он возвращает пару итераторов, обозначающих позиции первых отличающихся символов в интервалах:

int ciStringCompareImpl(const string& si,const string& s2) {

typedef pair

PSCI p = mismatch( // Использование ptr_fun

s1.begin(),s1,end(), // рассматривается

s2.begin(), // в совете 41

not2(ptr_fun(сiCharCompa re)));

if (p.first==s1.end()) { // Если условие истинно,

if (p.second==s2.end()) return 0; // либо si и s2 равны.

else return -1; // либо s1 короче s2