выполняют однопроходное слияние с сортировкой: они читают два сортированных интервала и строят новый сортированный интервал, содержащий все элементы обоих исходных интервалов. Эти алгоритмы работают с линейным временем, что было бы невозможно без предварительной сортировки исходных интервалов.
Перечень алгоритмов, работающих с сортированными интервалами, завершает алгоритм
includes
. Он проверяет, входят ли все объекты одного интервала в другой интервал. Поскольку
includes
рассчитывает на сортировку обоих интервалов, он обеспечивает линейное время. Без этого он в
общем случае работает медленнее.
В отличие от перечисленных алгоритмов,
unique
и
unique_copy
способны работать и с несортированными интервалами. Но давайте взглянем на описание
unique
в Стандарте (курсив мой): «…Удаляет из каждой смежной группы равных элементов все элементы, кроме первого».
Иначе говоря, если вы хотите, чтобы алгоритм
unique
удалил из интервала все дубликаты (то есть обеспечил «уникальность» значений в интервале), сначала необходимо позаботиться о группировке всех дубликатов. Как нетрудно догадаться, именно эта задача и решается в процессе сортировки. На практике алгоритм
unique
обычно применяется для исключения всех дубликатов из интервала, поэтому интервал, передаваемый при вызове
unique
(или
unique_copy
), должен быть отсортирован. Программисты Unix могут обратить внимание на поразительное сходство между алгоритмом STL
unique
и командой Unix
uniq
— подозреваю, что совпадение отнюдь не случайное.
Следует помнить, что
unique
исключает элементы из интервала по тому же принципу, что и
remove
, то есть ограничивается «логическим» удалением. Если вы не совсем уверены в том, что означает этот термин, немедленно обратитесь к советам 32 и 33. Трудно выразить, сколь важно доскональное понимание принципов работы
remove
и
remove
– подобных алгоритмов. Общих представлений о происходящем недостаточно. Если вы не знаете, как работают эти алгоритмы, у вас будут неприятности.
Давайте посмотрим, что же означает само понятие «сортированный интервал». Поскольку STL позволяет задать функцию сравнения, используемую в процессе сортировки, разные интервалы могут сортироваться по разным критериям. Например, интервал
int
можно отсортировать как стандартным образом (то есть по возрастанию), так и с использованием
greater<int>
, то есть по убыванию. Интервал объектов
Widget
может сортироваться как по цене, так и по дате. При таком изобилии способов сортировки очень важно, чтобы данные сортировки, находящиеся в распоряжении контейнера STL, была логически согласованы. При передаче сортированного интервала алгоритму, который также получает функцию сравнения, проследите за тем, чтобы переданная функция сравнения вела себя так же, как функция, применявшаяся при сортировке интервала.
Рассмотрим пример неправильного подхода:
vector<int> v; // Создать вектор, заполнить
… // данными, отсортировать
sort(v.begin, v.end, greater<int>); // по убыванию.
… // Операции с вектором
// (не изменяющие содержимого).
bool a5Exists = // Поиск числа 5 в векторе.
binary_search(v.begin, v.end, 5); // Предполагается, что вектор
// отсортирован по возрастанию!
По умолчанию
binary_search
предполагает, что интервал, в котором производится поиск, отсортирован оператором
<
(то есть по возрастанию), но в приведенном примере вектор сортируется по убыванию. Как нетрудно догадаться, вызов
binary_search
(или
lower_bound
и т. д.) для интервала, порядок сортировки которого отличен от ожидаемого, приводит к непредсказуемым последствиям.
Чтобы программа работала правильно, алгоритм
binary_search
должен использовать ту же функцию сравнения, которая использовалась при вызове
Все алгоритмы, работающие только с сортированными интервалами (то есть все алгоритмы, упоминавшиеся в данном совете, кроме
unique
и
unique_copy
), проверяют совпадение по критерию эквивалентности, как и стандартные ассоциативные контейнеры (которые также сортируются). С другой стороны,
unique
и
unique_copy
по умолчанию проверяют совпадение по критерию равенства, хотя при вызове этим алгоритмам может передаваться предикат, определяющий альтернативный смысл «совпадения». За подробной информацией о различиях между равенством и эквивалентностью обращайтесь к совету 19.
Одиннадцать алгоритмов требуют передачи сортированных интервалов для того, чтобы обеспечить повышенную эффективность, невозможную без соблюдения этого требования. Передавайте им только сортированные интервалы, помните о соответствии двух функций сравнения (передаваемой алгоритму и используемой при сортировке) и вы избавитесь от хлопот при проведении поиска, слияния и операций с множествами, а алгоритмы
unique
и
unique_copy
будут удалять все дубликаты — чего вы, вероятно, и добивались.
Совет 35. Реализуйте простые сравнения строк без учета регистра символов с использованием mismatch или lexicographical_compare
Один из вопросов, часто задаваемых новичками в STL — «Как в STL сравниваются строки без учета регистра символов?» Простота этого вопроса обманчива. Сравнения строк без учета регистра символов могут быть очень простыми или очень сложными в зависимости от того, насколько общим должно быть ваше решение. Если игнорировать проблемы интернационализации и ограничиться строками, на которые была рассчитана функция
strcmp
, задача проста. Если решение должно работать со строками в языках, не поддерживаемых
strcmp
(то есть практически в любом языке, кроме английского), или программа должна использовать нестандартный локальный контекст, задача чрезвычайно сложна.
В этом совете рассматривается простой вариант, поскольку он достаточно наглядно демонстрирует роль STL в решении задачи (более сложный вариант связан не столько с STL, сколько с проблемами локального контекста, упоминаемыми в приложении A). Чтобы простая задача стала интереснее, мы рассмотрим два возможных решения. Программисты, разрабатывающие интерфейсы сравнения строк без учета регистра, часто определяют два разных интерфейса: первый по аналогии с
strcmp
возвращает отрицательное число, ноль или положительное число, а второй по аналогии с оператором
<
возвращает
true
или
false
. Мы рассмотрим способы реализации обоих интерфейсов вызова с применением алгоритмов STL.