algorithm (C++)

algorithm — заголовочный файл в стандартной библиотеке языка программирования C++, включающий набор функций для выполнения алгоритмических операций над контейнерами и над другими последовательностями^[1].

Все функции библиотеки расположены в пространстве имён std^[2].

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

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

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

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

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

first, last — итераторы конца и начала (first1, last1, first2, last2 — итераторы конца и начала 1 и 2 диапазона соответственно)
middle — итератор, указывающий на определённую позицию в контейнере
function, predicate, op и comp — функциональные объекты
value, new, old и init — значения объектов, хранящихся в контейнерах
a, b — некоторые объекты одного типа
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`
`reverse`	`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`	Сортирует объекты в диапазоне
`stable_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 last1 (только для работы с set и multiset)
`merge`	`first1, last1, first2, last2, first3`	соединяет отсортированные диапазоны 1 и 2 в диапазон 3
`set_difference`	`first1, last1, first2, last2, first3`	Создает упорядоченную разность множеств, заданных диапазонами 1 и 2(только для работы с set и multiset)
`set_intersection`	`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_permutation`	`first, last`	Выполняет одну перестановку в последовательности данного диапазона
`prev_permutation`	`first, last`	Выполняет одну обратную перестановку в последовательности данного диапазона

Примечания править

↑ ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages — C++ § 25 Algorithms library [lib.algorithms] para. 1
↑ Stroustrup, Bjarne. Programming : principles and practice using C++ (англ.). — Upper Saddle River, NJ: Addison-Wesley, 2009. — P. 729. — ISBN 9780321543721. Архивировано 19 марта 2016 года.. — «The standard library algorithms are found in <algorithm>.».

Литература править

Лафоре P. Приложение E // Лафоре P. Объектно-ориентировочное программирование на с++. — Санкт-Петербург: Питер, 2004. — С. 836—843.

Ссылки править

<algorithm> — C++ Reference (англ.)
Algorithms library — cppreference.com (англ.)

[C++03_25/1-1] ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages — C++ § 25 Algorithms library [lib.algorithms] para. 1

[2] Stroustrup, Bjarne. Programming : principles and practice using C++ (англ.). — Upper Saddle River, NJ: Addison-Wesley, 2009. — P. 729. — ISBN 9780321543721. Архивировано 19 марта 2016 года.. — «The standard library algorithms are found in <algorithm>.».

[1]

[2]