Algorithm (C++)

Algorithm — заголовочный файл из стандартной библиотеки с++, включающий набор функций для выполнения алгоритмических операций над контейнерами и над другими последовательностями. Все функции библиотеки расположены в пространстве имен std.

Категории алгоритмов

Алгоритмы стандартной библиотеки STL разделяются на следующие категории.

• Не изменяющие последовательные операции
• Изменяющие последовательные операции
• Операции сортировки
• Бинарные операции поиска
• Операции слияния
• Кучи
• Операции отношений

Описание алгоритмов

В данных ниже таблицах в колонке аргументов функции вы встретите следующие обозначения:

1. first, last — итераторы конца и начала (first1, last1, first2, last2 — итераторы конца и начала 1 и 2 диапазона соответственно)
2. middle — итератор, указывающий на определенную позицию в контейнере
3. function, predicate, op и comp — функциональные объекты
4. value, new, old и init — значения объектов, хранящихся в контейнерах
5. a, b — некоторые объекты одного типа
6. iter — итератор

Не изменяющие последовательные операции

Название функции	Аргументы функции	Описание функции
adjacent_find	first, last	Возвращает итератор, указывающий на первую пару одинаковых объектов
count	first, last, value	Возвращает количество элементов, значение которых равно value
equal	first1, last1, first2	Возвращает значение true, если все соответствующие пары объектов из двух диапазонов равны
find	first, last, value	Возвращает итератор, указывающий на первый элемент, равный значению value
for_each	first, last, function	Применяет function ко всем объектам
mismatch	first1, last1, first2	Возвращает первую несовпадающую пару соответствующих объектов, расположенных в разных диапазонах позиций контейнера
search	first1, last1, first2, last2	Проверяет, содержится ли второй диапазон внутри первого, возвращает начало совпадения или last1, если нет совпадения

Изменяющие последовательные операции

Название функции	Аргументы функции	Описание функции
fill	first, last, value	Присваивает значение value всем объектам из диапазона
generate	first, last, gen	Заполняет диапазон значениями, получаемыми с помощью последовательных вызовов функции gen
iter_swap	iter1, iter2	Обменивает объекты, на которые указывают два итератора
remove	first, last, value	Удаляет из диапазона все значения, равные value
reverve	first, last	Обращает последовательность объектов из диапазона
replace	first, last, old, new	Заменяет все объекты, равные old , объектами, равными new
rotate	first, last, middle	Отражает зеркально последовательность элементов
swap	a, b	Заменяет один объект другим
swap_ranges	first1, last1, first2	Обменивает соответствующие объекты в двух диапазонах
transform	first1, last1, first2, operator	Превращает объекты из диапазона 1 в новые объекты диапазона 2, применяя operator
unique	first, last	Удаляет все эквивалентные объекты в последовательности, кроме первого

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

Название функции	Аргументы функции	Описание функции
nth_element	first, nth,last	Помещает n-й объект в позиции, которую он занимал бы после сортировки всего диапазона
sort	first, last	Сортирует объекты в диапазоне

Бинарные операции поиска

Название функции	Аргументы функции	Описание функции
binary_search	first, last, value	Возвращает true, если значение value входит в интервал
equal_range	first, last, value	Возвращает пару объектов, представляющих собой нижнюю и верхнюю гранцицы, между которыми можно вставить значение value без изменения порядка сортировки
lower_bound	first, last, value	Возвращает итератор, указывающий на первую позицию, в которую можно вставить значение value без изменения порядка следования объектов
upper_bound	first, last, value	Возвращает итератор, указывающий на последнюю позицию, в которую можно вставить значение value без изменения порядка следования объектов

Операции слияния

Название функции	Аргументы функции	Описание функции
includes	first1, last1, first2, last2	Возвращает true, если все объекты из диапазона first2 last2 имеются также в диапазоне first1 (только для работы с set и multiset)
merge	first1, last1, first2, last2, first3	соединяет отсортированные диапазоны 1 и 2 в диапазон 3
set_difference	first1, last1, first2, last2, first 3	Создает упорядоченную разность множеств, заданных диапазонами 1 и 2(только для работы с set и multiset)
set_intersectiom	first1, last1, first2, last2, first3	Создает упорядоченное пересечение элементов диапазонов 1 и 2(только для работы с set и multiset)
set_union	first1, last1, first2, last2, first3	Создает упорядоченное объединение элементов диапазонов 1 и 2 (только для работы с set и multiset)

Кучи

Название функции	Аргументы функции	Описание функции
make_heap	first, last	Создает кучу из значений диапазона first last
pop_heap	first, last	Меняет значения в first и last-1. Помещает диапазон first last-1 в кучу
push_heap	first, last	Помещает значение из last-1 в результирующую кучу (heap, область динамической памяти) диапазон от first до last
sort_heap	first, last	Упорядочивает элементы в куче first last

Операции отношений

Название функции	Аргументы функции	Описание функции
lexicographical_compare	first1, last1, first2, last2	Возвращает true, если последовательность в диапазоне 2 следует в алфавитном порядке за последовательностью диапазона 1
max	a, b	Возвращает наибольшее из a, b
max_element	first, last	Возвращает итератор, указывающий на наибольший объект в диапазоне
min	a, b	Возвращает наименьшее из a, b
min_element	first,last	Возвращает итератор, указывающий на наименьший объект в диапазоне
next_permulation	first, last	Выполняет одну перестановку в последовательности данного диапазона
prev_permutation	first, last	Выполняет одну обратную перестановку в последовательности данного диапазона

Ссылки

• Лафоре P. Приложение E // Лафоре P. Объектно-ориентировочное программирование на с++. — Санкт-Петербург: Питер, 2004. — С. 836—843.
• www.cplusplus.com — список функций с их описанием в библиотеке algorithm
• en.cppreference.com — список функций с их описанием в библиотеке algorithm
• Описание библиотеки algorithm в английской википедии