Совет 34. Помните о том. какие алгоритмы получают сортированные интервалы

Совет 34. Помните о том. какие алгоритмы получают сортированные интервалы

Не все алгоритмы работают с произвольными интервалами. Например, для алгоритма remove (см. советы 32 и 33) необходимы прямые итераторы и возможность присваивания через эти итераторы. Таким образом, алгоритм не применим к интервалам, определяемым итераторами ввода, а также к контейнерам map/multimap и некоторым реализациям set/multiset (см. совет 22). Аналогично, многие алгоритмы сортировки (см. совет 31) требуют итераторов произвольного доступа и потому не могут применяться к элементам списка.

При нарушении этих правил компилятор выдает длинные, невразумительные сообщения об ошибках (см. совет 49). Впрочем, существуют и другие, более сложные условия. Самым распространенным среди них является то, что некоторые алгоритмы работают только с интервалами отсортированных значений. Данное требование должно неукоснительно соблюдаться, поскольку нарушение приводит не только к выдаче диагностических сообщений компилятора, но и к непредсказуемому поведению программы на стадии выполнения.

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

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

binary_search lower_bound

upper_bound equal_range

set_union set_intersection

set_difference set_symmetric_difference

merge inplace_merge

includes

Кроме того, следующие алгоритмы обычно используются с сортированными интервалами, хотя сортировка и не является обязательным требованием:

unique unique_copy

Вскоре будет показано, что в определении «сортированный интервал» кроется одно важное ограничение, но сначала позвольте мне немного прояснить ситуацию с этими алгоритмами. Вам будет проще запомнить, какие алгоритмы работают с сортированными интервалами, если вы поймете, для чего нужна сортировка.

Алгоритмы поиска binary_search, lower_bound, upper_bound и equal_range (см. совет 45) требуют сортированные интервалы, потому что их работа построена на бинарном поиске. Эти алгоритмы, как и функция bsearch из библиотеки С, обеспечивают логарифмическое время поиска, но взамен вы должны предоставить им заранее отсортированные значения.

Вообще говоря, логарифмическое время поиска обеспечивается не всегда. Оно гарантировано лишь в том случае, если алгоритмам передаются итераторы произвольного доступа. Если алгоритм получает менее мощные итераторы (например, двусторонние), он выполняет логарифмическое число сравнений, но работает с линейной сложностью. Это объясняется тем, что без поддержки «итераторной математики» алгоритму необходимо линейное время для перемещения между позициями интервала, в котором производится поиск.

Четверка алгоритмов set_unon, set_inesection, set_diffeence и set_symmetric_ difference предназначена для выполнения со множествами операций с линейным временем. Почему этим алгоритмам нужны сортированные интервалы? Потому что в противном случае они не справятся со своей задачей за линейное время. Начинает прослеживаться некая закономерность — алгоритмы требуют передачи сортированных интервалов для того, чтобы обеспечить лучшее быстродействие, невозможное при работе с несортированными интервалами. В дальнейшем мы лишь найдем подтверждение этой закономерности.

Алгоритмы merge и inplace_merge выполняют однопроходное слияние с сортировкой: они читают два сортированных интервала и строят новый сортированный интервал, содержащий все элементы обоих исходных интервалов. Эти алгоритмы работают с линейным временем, что было бы невозможно без предварительной сортировки исходных интервалов.

Перечень алгоритмов, работающих с сортированными интервалами, завершает алгоритм 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>0): // по убыванию.

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

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

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<int>());

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

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Алгоритмы

Из книги автора

Алгоритмы Алгоритм — это последовательность действий, возможно, с одним входом или более и, в конечном счете, с одним результатом или выходом. Например, подсчет количества людей в комнате представляет собой алгоритм, для которого люди, находящиеся в комнате, являются


Помните: в Интернете пользователь может делать все, что захочет

Из книги автора

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


STL: алгоритмы

Из книги автора

STL: алгоритмы Предпочитайте алгоритмы циклам. — Бьярн Страуструп (Bjarne Stroustrup), [Stroustrup00] §18.12 Алгоритмы представляют собой циклы — только они лучше циклов. Алгоритмы — это "шаблоны" циклов, с добавлением дополнительной семантики по сравнению с простыми for и do. Конечно, начав


Совет 10. Помните о правилах и ограничениях распределителей памяти

Из книги автора

Совет 10. Помните о правилах и ограничениях распределителей памяти Распределители памяти первоначально разрабатывались как абстракция для моделей памяти, позволяющих разработчикам библиотек игнорировать различия между near- и far-указателями в некоторых 16-разрядных


Совет 15. Помните о различиях в реализации string

Из книги автора

Совет 15. Помните о различиях в реализации string Бьерн Страуструп однажды написал статью с интригующим названием «Sixteen Ways to Stack a Cat» [27], в которой были представлены разные варианты реализации стеков. Оказывается, по количеству возможных реализаций контейнеры string не уступают


Совет 19. Помните о различиях между равенством и эквивалентностью

Из книги автора

Совет 19. Помните о различиях между равенством и эквивалентностью Алгоритм find и функция set::insert являются типичными представителями семейства функций, проверяющих совпадение двух величин, однако делают это они по-разному. Для find совпадением считается равенство двух


Алгоритмы

Из книги автора

Алгоритмы В начале главы 1 я упоминал о том, что львиная доля репутации STL связана с контейнерами, и это вполне объяснимо. Контейнеры обладают массой достоинств и упрощают повседневную работу бесчисленных программистов С++. Но и алгоритмы STL тоже по-своему замечательны и в


Совет 31. Помните о существовании разных средств сортировки

Из книги автора

Совет 31. Помните о существовании разных средств сортировки Когда речь заходит об упорядочении объектов, многим программистам приходит в голову всего один алгоритм: sort (некоторые вспоминают о qsort, но после прочтения совета 46 они раскаиваются и возвращаются к мыслям о


Совет 43. Используйте алгоритмы вместо циклов

Из книги автора

Совет 43. Используйте алгоритмы вместо циклов Каждому алгоритму передается по крайней мере одна пара итераторов, определяющих интервал объектов для выполнения некоторой операции. Так, алгоритм min_element находит минимальное значение в интервале, алгоритм accumulate вычисляет


Совет 45. Различайте алгоритмы count, find, binary_search, lower_bound, upper_bound и equal_range

Из книги автора

Совет 45. Различайте алгоритмы count, find, binary_search, lower_bound, upper_bound и equal_range Предположим, вы ищете некоторый объект в контейнере или в интервале, границы которого обозначены итераторами. Как это сделать? В вашем распоряжении целый арсенал алгоритмов: count, find, binary_search, lower_bound, upper_bound и


Совет 50. Помните о web-сайтах, посвященных STL

Из книги автора

Совет 50. Помните о web-сайтах, посвященных STL Интернет богат информацией об STL. Если ввести в любой поисковой системе запрос «STL», вы получите сотни ссылок, часть из которых даже будет содержать полезную информацию. Впрочем, большинство программистов STL в поисках не нуждается


АЛГОРИТМЫ

Из книги автора

АЛГОРИТМЫ Все алгоритмы отделены от деталей реализации структур данных и используют в качестве параметров типы итераторов. Поэтому они могут работать с определяемыми пользователем структурами данных, когда эти структуры данных имеют типы итераторов, удовлетворяющие


12.5.4. Алгоритмы перестановки

Из книги автора

12.5.4. Алгоритмы перестановки Рассмотрим последовательность из трех символов: {a,b,c}. Для нее существует шесть различных перестановок: abc, acb, bac, bca, cab и cba, лексикографически упорядоченных на основе оператора “меньше”. Таким образом, abc – это первая перестановка, потому что


Алгоритмы хэширования

Из книги автора

Алгоритмы хэширования Криптографическими методами можно обеспечить не только конфиденциальность, но и проконтролировать целостность передаваемых или хранимых данных. Контроль целостности в основном осуществляется путем расчета некоторой "контрольной суммы" данных.