Include algorithm c что это

Name already in use

cpp-docs / docs / standard-library / algorithm.md

• Go to file T
• Go to line L
• Copy path
• Copy permalink

• Open with Desktop
• View raw
• Copy raw contents Copy raw contents

Copy raw contents

Copy raw contents

Defines C++ Standard Library container template functions that perform algorithms.

[!NOTE] The <algorithm> library also uses the #include <initializer_list> statement.

The C++ Standard Library algorithms can operate on various data structures. The data structures that they can operate on include not only the C++ Standard Library container classes such as vector and list , but also user-defined data structures and arrays of elements, as long as they satisfy the requirements of a particular algorithm. C++ Standard Library algorithms achieve this level of generality by accessing and traversing the elements of a container indirectly through iterators.

C++ Standard Library algorithms process iterator ranges that are typically specified by their beginning or ending positions. The ranges referred to must be valid in the sense that all iterators in the ranges must be dereferenceable and, within the sequences of each range, the last position must be reachable from the first by incrementing the iterator.

Starting in C++20, most of the algorithms defined in <algorithm> are also available in a form that takes a range . For example, rather than call sort(v1.begin(), v1.end(), greater<int>()); , you can call ranges::sort(v1, greater<int>());

The C++ Standard Library algorithms can work with different types of container objects at the same time. Two suffixes have been used to convey information about the purpose of the algorithms:

The _if suffix indicates that the algorithm is used with function objects that operate on the values of the elements rather than on the elements themselves. For example, the find_if algorithm looks for elements whose values satisfy the criterion specified by a function object, whereas the find algorithm searches for a particular value.

The _copy suffix indicates that the algorithm generally modifies copied values rather than copy modified values. In other words, they don’t modify the source range’s elements but put the results into an output range/iterator. For example, the reverse algorithm reverses the order of the elements within a range, whereas the reverse_copy algorithm copies the reversed result into a destination range.

C++ Standard Library algorithms are often classified into groups to indicate their purpose or requirements. These include modifying algorithms that change the value of elements as compared with non-modifying algorithms that don’t. Mutating algorithms change the order of elements, but not the values of their elements. Removing algorithms can eliminate elements from a range or a copy of a range. Sorting algorithms reorder the elements in a range in various ways and sorted range algorithms only act on ranges whose elements have been sorted in a particular way.

The C++ Standard Library numeric algorithms that are provided for numerical processing have their own header file <numeric> , and function objects and adaptors are defined in the header <functional> . Function objects that return Boolean values are known as predicates. The default binary predicate is the comparison operator< . In general, the elements being ordered need to be less than comparable so that, given any two elements, it can be determined either that they’re equivalent (in the sense that neither is less than the other) or that one is less than the other. This results in an ordering among the nonequivalent elements.

<algorithm>

The header <algorithm> defines a collection of functions especially designed to be used on ranges of elements.

A range is any sequence of objects that can be accessed through iterators or pointers, such as an array or an instance of some of the STL containers. Notice though, that algorithms operate through iterators directly on the values, not affecting in any way the structure of any possible container (it never affects the size or storage allocation of the container).

Алгоритмы стандартной библиотеки C++

Стандартная библиотека <algorithms> содержит большое количество алгоритмов для работы с контейнерами стандартной библиотеки. Доступные инструменты покрывают значительную часть встречающихся алгоритмических задач. Использование стандартных алгоритмов вместо их самостоятельной реализации является хорошим стилем программирования по следующим причинам:

• Экономия времени. Мы не тратим время на реализацию и отладку алгоритма.
• Гарантия отсутствия ошибок в логике работы алгоритма. Алгоритмы стандартной библиотеки протестированы многими программистами.
• Лаконичность и выразительность кода. Вместо некоторого количества строчек, которые выполняют неочевидные манипуляции, мы видим название хорошо документированного алгоритма.

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

iota, for_each и transform

Большое количество циклов for в коде, который выполняет манипуляции со структурами данных, обычно говорит о недостаточном использовании стандартных алгоритмов. Так, если необходимо применить некоторую функцию ко всем элементам контейнера, то можно рассмотреть использование алгоритма for_each .

Решим следующую задачу: вывести в стандартный поток квадраты натуральных чисел от 1 до 100. Следующий код показывает, что эта задача может быть решена в четырех строчках кода и без явного использования циклов:

Мы воспользовались алгоритмом iota из библиотеки <numeric> , чтобы проинициализировать массив набором последовательных целых чисел. Затем мы два раза использовали алгоритм for_each : для вычисления квадратов и для вывода значений в стандартный поток.

Третьим аргументом алгоритм for_each принимает функцию одного аргумента. Тип аргумента должен соответствовать типу элементов контейнера. Вместо обычной функции бывает удобно передать лямбда-выражение, что мы и сделали оба раза в этом примере. Лямбда-выражение позволяет определить функцию в месте ее использования. Квадратные скобки [] указывают на начало лямбда-выражения; в круглых скобках указываются аргументы выражения; в фигурных скобках содержится тело лямбда-выражения.

Модифицируем немного нашу задачу. Предположим, что мы не хотим изменять исходный вектор, а значения квадратов хотим сохранить в другом векторе. Алгоритм transform позволяет выполнить такое преобразование:

Третьим аргументом алгоритм transform принимает итератор на место целевого контейнера, с которого нужно начать заполнять значения. Обратите внимание, что мы заранее инициализировали вектор target нужной длины.

all_of, any_of, none_of

Довольно часто возникает задача проверки какого-либо условия для всех объектов контейнера. Здесь на помощь приходят алгоритмы all_of , any_of и none_of с очевидным поведением, которые принимают диапазон значений и унарный предикат — функцию одного аргумента, которая возвращает true или false . Так, например, можно проверить содержит ли множество хотя бы один отрицательный элемент:

Вторая строчка этого примера не поменяется, если вместо контейнера set будет использован другой контейнер, например, list , vector , array или unordered_set .

count, count_if, find, find_if

Алгоритм count позволяет посчитать количество элементов в контейнере, равных заданному. Модификация этого алгоритма count_if подсчитывает количество элементов, удовлетворяющих определенному условию. Рассмотрим следующий пример: мы имеем дело с историей авторизации пользователей на сайте, которая хранится в виде вектора строк. Каждая строка — это логин пользователя. Подсчитаем сколько раз авторизовывался пользователь с логином david:

Если нам захочется удалить запись для логина david, мы можем это сделать с помощью алгоритма find и метода vector::erase :

Алгоритм find возвращает итератор на найденный элемент. Версия алгоритма find_if позволяет найти первый элемент, удовлетворяющий некоторому условию.

Как и другие алгоритмы, find и count могут работать с контейнерами разных типов. Они проходят переданный диапазон значений последовательно, начиная с первого элемента. Использование такого подхода для контейнеров set и map — плохая идея, ведь они созданы для того чтобы выполнять поиск объектов быстрее. Это общее правило: если контейнер имеет метод, аналогичный общему алгоритму, то следуем использовать метод контейнера. В большинстве случаев это даст выигрыш в производительности.

sort, stable_sort, nth_element

Алгоритмы сортировки — это важный и интересный раздел теории алгоритмов. Работать с отсортированными элементами во многих ситуациях удобнее, в частности, сложность поиска элементов становится логарифмической вместо линейной. Стандартная библиотека C++ предлагает алгоритмы sort и stable_sort , которые выполняют сортировку за время, пропорциональное N log(N), где N — количество элементов массива. Стабильная сортировка stable_sort при этом гарантирует, что равные объекты не меняют своего относительного положения в контейнере.

Рассмотрим простой пример сортировки:

По умолчанию сортировка выполняется по возрастанию, а для сравнения используется оператор меньше < . Это поведение можно изменить, передав свой компаратор — объект, который принимает два объекта и возвращает логическое значение. Отсортируем наш вектор строк по длине строки по убыванию:

Мы использовали стабильную версию сортировки. В этом случае Ivan гарантировано окажется левее Adam в отсортированном векторе.

Оказывается, что задача поиска n-го элемента (как если бы элементы стояли по порядку по какому-либо признаку) может быть решена быстрее, чем сортировка всего массива — за линейное время. Стандартная библиотека предлагает алгоритм nth_element для решения этой задачи.

lower_bound, upper_bound, binary_search

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

Алгоритм binary_search проверяет, есть ли в отсортированном массиве данный элемент и возвращает true или false в зависимости от результата поиска.

Все три алгоритма выполняются за логарифмическое время.

Резюме

В этом материале мы рассмотрели примеры использования нескольких основных алгоритмов стандартной библиотеки C++. Обсудили, что применение стандартных алгоритмов является хорошим стилем программирования, позволяет писать код быстрее, и делает его более легким для прочтения.

Полезные алгоритмы стандартной библиотеки не ограничиваются рассмотренными выше. Мы рекомендуем посмотреть на полный список доступных алгоритмов, среди которых можно обратить внимание на алгоритмы copy , remove , generate и partition , которые вполне могут пригодиться.

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

Standard Algorithms Introduction Algorithms Introduction Std.Algorithms

Standard algorithms use iterators to traverse / access input elements.

• allows algorithms to be implemented independent from container types
• eliminates the need for having one algorithm implementation per container type
• new (third party) containers can be used with existing standard algorithm implementations

Iter ator . Ranges

= pair p,q of iterators

end-of-range iterator q points one behind the last element in the range

Range Objects As Inputs C++20

Algorithms in C++20’s namespace std::ranges

• also accept single range objects like containers or views as inputs (before C++20: only iterator pairs)
• must be called with the full namespace ( namespace-qualified in C++ parlance) because they can’t be found by argument dependent lookup (= look up a function in the namespaces of its arguments).
• A range is any object r for which std::ranges::begin(r) and std::ranges::end(r) return either valid iterators or end-of-range indicating sentinels.

Customization with Callable Parameter s

Many standard algorithms can be customized by passing a callable entity like a function, lambda or custom function object as parameter:

The second version of min_element takes a callable entity as 3 rd argument for comparing pairs of elements unlike the first version which uses operator < .

Example: min_element with Custom Type

Compare using a function

Compare using a lambda

Lambdas

• can be thought of as anonymous functions
• can be defined within functions (regular C++ functions can not be nested)
• are function objects whose type is auto-generated by the compiler

We will learn more about function objects – and lambdas in particular – in later chapters. They are not only extremely useful, but also a lot more powerful than the above example suggests.

Parallel Execution C++17

Most standard algorithms can be executed in parallel.

This is configured by providing an execution policy object as first argument.

Execution Policy

Effect

may parallelize, vectorize, or migrate computation across threads;

allows to invoke input element access functions in an unordered fashion, and unsequenced with respect to each other within each thread

Compiler Support (min. required versions)

GNU g++ 9

Requires TBB Library (Intel Thread Building Blocks)

Install on Debian/Ubuntu/WSL: sudo apt install libtbb-dev

The executable needs to be linked against TBB: g++ -std=c++17 . -o exename -ltbb

Microsoft MSVC 19.14 (VS 2017 15.7)

NVIDIA NVC++

can use NVIDIA GPUs to accelerate C++ standard algorithms:

Iterator  / Range Categories

Category = set of supported iterator / range object operations & guarantees

• based on common algorithm requirements (input, output, efficiency, correctness, …)
• determined by the input range object or the host container providing the iterator

iterator-like position specifier; usually only used for denoting the end of a range

read access to objects; advanceable to next position

example: iterator that reads values from a file

write access to objects; advanceable to next position

example: iterator that writes values to a file

read/write access; forward traversal, no random access

multi-pass guarantee: iterators to the same range can be used to access the same objects multiple times

example: std::forward_list ‘s iterators

multi-pass guarantee, traversal in both directions (but no random access)

example: std::list ‘s iterators

random access, but not necessarily to a contiguous memory block

example: std::deque ‘s iterators

random access to contiguous memory

example: std::vector ‘s iterators

If you need detailed information about algorithm requirements, runtime complexity, etc. refer to cppreference.com

The descriptions there are not very beginner-friendly but very detailed, usually up-to date and checked by a lot of C++ experts.

Error Message s

of generic algorithms can be quite confusing:

This does not compile as sort requires random access iterators, but list provides only bi-directional iterators. The resulting error messages of GCC 10 look like this:

By default, requirements of generic functions regarding their input types are only checked in an ad-hoc manner inside the function implementation and not at the call site.

This means that compilation fails when an unsupported operation, here iterator1 — iterator2 , is used in the implementation.

Always look for the first message that contains the word ‘error’.

C++20  Algorithms in Namespace std::ranges

• requirements are checked at the call site using Concepts (more on that later)
• requirements are overall more consistently specified
• allow compiler error messages to be more helpful, but there is still some room for improvement

Algorithm Parameter Iconography

The following graphical conventions are used for visualizations of standard algorithms, functions, container member functions, etc. throughout this website.