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.. — «The standard library algorithms are found in
<algorithm>.».
Литература
- Лафоре P. Приложение E // Лафоре P. Объектно-ориентировочное программирование на с++. — Санкт-Петербург: Питер, 2004. — С. 836—843.
Ссылки
- <algorithm> — C++ Reference (англ.)
- Algorithms library — cppreference.com (англ.)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.