Алгоритмы, связанные с сортировкой

Имеется девять подкатегорий алгоритмов, связанных с сортировкой:

Алгоритмыsort, stable_sort и partial_sort переставляют элементы последовательности в порядке возрастания.

Алгоритм nth_element находит N-й наименьший элемент последовательности.

Алгоритмы binary_search, lower_bound, upper_bound иequal_range выполняют поиск в отсортированной последовательности методом деления пополам.

Алгоритм merge сливает две отсортированные последовательности в одну.

Алгоритмы includes, set_union,set_intersection, set_differenceиset_symmetric_differenceвыполняют теоретико-множественные операции над отсортированными структурами.

Алгоритм push_heap, pop_heap, make_heap и sort_heap выполняют операции по упорядочению последовательности, организованной в виде пирамиды (помимо прочего, эти алгоритмы используются в очередях с приоритетами).

Алгоритмы min, max, min_element и max_element находят минимальный или максимальный элемент пары или последовательности.

Алгоритм lexicographical_compare лексикографически сравнивает две последовательности.

Алгоритмы next_permutation и prev_permutation генерируют перестановки последовательности, основываясь на лексикографическом упорядочении множества всех перестановок.

Обобщенные численные алгоритмы

Библиотека предоставляет четыре подкатегории численных алгоритмов.

Алгоритм accumulate вычисляет сумму элементов последовательности. Алгоритм inner_product вычисляет сумму произведений соответствующих элементов двух последовательностей.

Алгоритм partial_sum вычисляет частичные суммы элементов последовательности и сохраняет их в другой (или той же) последовательности.

Алгоритм adjacent_difference вычисляет разности смежных элементов и сохраняет их в другой (или той же) последовательности.

Итераторы

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

Итераторы разделяются на пять категорий: входные, выходные, однонаправленные, двунаправленные и произвольного доступа.

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

template <typename InputIterator, typename T> InputIterator find(InputIterator first, InputIterator last,

const T& value)

{

while (first != last && *first != value)

++first; return first;

}

Чтобы данный алгоритм и ему подобные работали корректно, должны быть определены операции != и == для сравнения двух итераторов; префиксный и постфиксный оператор ++, который продвигает итератор на один шаг вперед; операция разыменовывания * для возвращения значения, на которое указывает итератор. Заметим, однако, что в данном случае требуется поддержка чтения значения, на которое указывает итератор, но не требуется поддержка записи (операция *first= не является необходимой). Такие итераторы называются входными итераторами. Кроме того на данную категорию налагается требование поддержки операций присвоения = (например, first=) и операции –> (к методам объекта, на который указывает first можно обратиться first–>). Класс InputIterator должен содержать конструктор копирования.

Рассмотрим теперь другой алгоритм STL, который выполняет копирование из одной последовательности в другую:

template <typename InputIterator, typename OutputIterator> OutputIterator copy(InputIterator first,

InputIterator last, OutputIterator result)

{

while (first != last)

{ *result = *first; ++first; ++result;

}

return result;

}

Итератор result позволяет записывать значения в последовательность, но, в отличие от входного итератора не обязательно должен их считывать. Такие итераторы называются выходными итераторами: для них определен оператор разыменовывания * таким образом, что гарантируется корректность выражения *result=, но не гарантируется возможность применения в выражениях для получения значения *result, на которые указывает выходной итератор. Еще одно отличие выходных итераторов от входных состоит в отсутствии обязательной поддержки операций!= и ==, а также операции –>. Для выходных итераторов обязательна поддержка лишь префиксного и постфиксного оператора ++, который продвигает итератор на один шаг вперед и операции разыменовывания * для записи значения в контейнер в позицию, на которую указывает итератор. Кроме того, класс OutputIterator должен содержать конструктор копирования.

Следующий класс итераторов – однонаправленные итераторы (ForwardIterator). Данные итераторы объединяют в себе возможности как выходных, так и входных итераторов.

В качестве алгоритма, который выполняет чтение и запись последовательности, рассмотрим алгоритм STL replace, который меняет все значения x в диапазоне [first,last) другим значением y:

template <typename ForwardIterator, typename T> void replace(ForwardIterator first, ForwardIterator last, const T& x, const T& y)

{

while (first != last)

{ if (*first == x)

*first = y; ++first;

}

}

Этот алгоритм может использоваться для замены значений в различных структурах данных, которые в состоянии предоставить однонаправленные итераторы для доступа к данным.

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

Все три выше описанных категории итераторов должны были иметь возможность двигаться вперед, что обеспечивалось перегрузкой оператора инкремента ++. Четвертая категория итераторов – двунаправленные итераторы (BidirectionalIterator) могут продвигаться в обоих направлениях, что обеспечивается наличием перегруженного оператора декремента –- как в постфиксной форме, так и в префиксной.

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

template <typename BidirectionalIterator> void reverse(BidirectionalIterator first, BidirectionalIterator last);

Оказывается, этих четырех категорий структур данных недостаточно для всех алгоритмов. Имеются некоторые алгоритмы, которые предъявляют к итераторам еще более высокие требования. Для эффективной работы эти алгоритмы требуют, чтобы любой элемент последовательности был достижим из любого другого за константное время.

Рассмотрим, например, обобщенный алгоритм STL sort. Будучи объявлен как

template <typename RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last);

он требует, чтобы любой элемент последовательности был достижим из любого другого за константное время. Поэтому с четырьмя вышеперечисленными категориями итераторов данный алгоритм работать не будет. Лишь некоторые контейнеры STL предоставляют итераторы, обладающие этим свойством. Итераторы произвольного доступа обладают свойством обращения к любому элементу последовательности за константное время. Для этого они поддерживают все методы двунаправленных итераторов и, кроме того, обладают перегруженными методами +, – (прибавление и вычитание целых чисел); двунаправленные «большие переходы» +=, –= (операции first+=5; first – =4); вычитание итераторов (last–first), дающее целое значение; перегруженная операция индексации массива [ ]; операторы сравнения <, >, <=, >=. Обычный тип данных языка C/C++ указатель является итератором произвольного доступа.

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

Отметим в заключение, что все стандартные контейнеры STL поддерживают либо двунаправленные итераторы, либо итераторы произвольного доступа. В подавляющем большинстве задач программирования вполне достаточно тех итераторов, которые предоставляются самими контейнерами. Однако, если мы создаем собственную библиотеку, содержащую новый контейнер, то мы должны определить для него и итератор. Для того, чтобы разобраться в принципах организации классов, реализующих итераторы и создать свой собственный итератор надо обратиться к классам, объявленным в заголовочном файле <iterator>. Это является отдельной темой для изучения.