484 Часть III. Современное программирование на C++

Алгоритмы сортировки и связанные с ними. Алгоритмы библиотеки STL из этой категории выполняют операции поиска, сортировки, слияния, установки операций в сортируемых контейнерах, и некоторые другие. Объединяет алгоритмы этой группы то, что все они имеют две версии. Первая версия всегда использует операцию <, определяемую типом данных контейнера, вторая версия использует для сравнения определяемую пользователем функцию, которая принимает два аргумента и возвращает значение булевого типа. Кроме способа, которым производится сравнение элементов, нет никакой разницы между двумя версиями. Ни один из алгоритмов этой категории не использует операцию == для сравнения элементов. Элементы а и ь считаются равными, если (! (a<b) && ! (b<a)) == true.

В отличие от предыдущих категорий, алгоритмы этой категории могут работать с ассоциативными контейнерами.

! Предупреждение

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

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

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

template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first,

RandomAccessIterator last. Compare comp) ;

stable_sort. Алгоритм устойчивой сортировки stable_sort выполняет то же, что и sort, но при этом сохраняет исходный порядок равных элементов.

template <class RandomAccessIterator> void stable_sort (RandomAccessIterator first, RandomAccessIterator last) ;

template <class RandomAccessIterator, class Compare> void stable_sort (RandomAccessIterator first,

RandomAccessIterator last. Compare comp) ;

partial_sort. Выполняет частичную сортировку входной последовательности [first, last). Первые middle - first элементов результирующей последовательности являются упорядоченными элементами из всего входного диапа-