AIOJ

STL provides approximately 100 template functions that implement algorithms. Most are included in <algorithm>, while some are included in <numeric> and <functional>. For a complete list of functions, see the reference manual; for sorting-related functions, see the corresponding sorting page.

find: sequential search. find(v.begin(), v.end(), value), where value is the value to search for.
reverse: reverse an array or string. reverse(v.begin(), v.end()) or reverse(a + begin, a + end).
unique: remove adjacent duplicate elements in a container. unique(ForwardIterator first, ForwardIterator last) returns an iterator pointing to the end of the deduplicated container; the size of the original container remains unchanged. Combined with sort, it can implement complete container deduplication.

random_shuffle: randomly shuffle an array. random_shuffle(v.begin(), v.end()) or random_shuffle(v + begin, v + end).

???+ warning "The random_shuffle function has been removed from the latest C++ standard" random_shuffle was deprecated starting in C++14 and removed starting in C++17.

In C++11 and later standards, you can use the `shuffle` function instead of the original `random_shuffle`. Use it as `shuffle(v.begin(), v.end(), rng)` (the last parameter is the random-number generator to use; generally, use a true random-number generator [`random_device`](https://zh.cppreference.com/w/cpp/numeric/random/random_device) to seed a Mersenne Twister pseudorandom number generator [`mt19937`](https://zh.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine)).

```cpp
// #include <random>
std::mt19937 rng(std::random_device{}());
std::shuffle(v.begin(), v.end(), rng);
```

sort: sort. sort(v.begin(), v.end(), cmp) or sort(a + begin, a + end, cmp), where end is one position after the last element of the array being sorted, and cmp is a custom comparison function.
stable_sort: stable sort; usage is the same as sort().
nth_element: classify within a specified range; that is, find the $n$ -th largest element in the sequence, such that all elements to its left are smaller than it and all elements to its right are larger than it. nth_element(v.begin(), v.begin() + n, v.end(), cmp) or nth_element(a + begin, a + begin + n, a + end, cmp).
binary_search: binary search. binary_search(v.begin(), v.end(), value), where value is the value to search for.
merge: merge in sorted order two (already sorted) sequences into the insertion iterator of a third sequence. merge(v1.begin(), v1.end(), v2.begin(), v2.end() ,back_inserter(v3)).
inplace_merge: merge in place into one sorted sequence the two ranges sorted by the less-than operator: [first,middle), [middle,last). inplace_merge(v.begin(), v.begin() + middle, v.end()).
lower_bound: perform a binary search in a sorted sequence and return an iterator pointing to the position of the first element greater than or equal to $x$ . If no such element exists, return the end iterator. lower_bound(v.begin(),v.end(),x).
upper_bound: perform a binary search in a sorted sequence and return an iterator pointing to the position of the first element greater than $x$ . If no such element exists, return the end iterator. upper_bound(v.begin(),v.end(),x).

???+ warning "Time complexity of lower_bound and upper_bound" In an ordinary array, the time complexity of both functions is $O(\log n)$ , but in associative containers such as set, directly calling lower_bound(s.begin(),s.end(),val) has time complexity $O(n)$ .
```
Associative containers such as `set` already encapsulate functions such as `lower_bound` (called as `s.lower_bound(val)`); this form has time complexity $O(\log n)$.
```
next_permutation: change the current permutation to the next permutation among all permutations. If the current permutation is already the last permutation among all permutations (the elements are completely arranged in descending order), the function returns false and changes the permutation to the first permutation among all permutations (the elements are completely arranged in ascending order); otherwise, the function returns true. next_permutation(v.begin(), v.end()) or next_permutation(v + begin, v + end).
prev_permutation: change the current permutation to the previous permutation among all permutations. Usage is the same as next_permutation.
partial_sum: compute prefix sums. Let the source container be $x$ and the target container be $y$ ; then $y[i]=x[0]+x[1]+\dots+x[i]$ . partial_sum(src.begin(), src.end(), back_inserter(dst)).

Usage examples

Use next_permutation to generate all permutations of $1$ through $9$ . Example problem: Luogu P1706 Permutation Problem

???+ note "Implementation" cpp int N = 9, a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; do { for (int i = 0; i < N; i++) cout << a[i] << " "; cout << endl; } while (next_permutation(a, a + N));
Use lower_bound and upper_bound to find the boundaries in sorted array $a$ between elements less than $x$ , equal to $x$ , and greater than $x$ .

???+ note "Implementation" cpp int N = 10, a[] = {1, 1, 2, 4, 5, 5, 7, 7, 9, 9}, x = 5; int i = lower_bound(a, a + N, x) - a, j = upper_bound(a, a + N, x) - a; // a[0] ~ a[i - 1] are elements less than x; a[i] ~ a[j - 1] are elements equal to x; // a[j] ~ a[N - 1] are elements greater than x cout << i << " " << j << endl;
Use partial_sum to calculate the prefix sums of the elements in $src$ and store them in $dst$ .

???+ note "Implementation" cpp vector<int> src = {1, 2, 3, 4, 5}, dst; // Calculate the prefix sums of the elements in src; dst[i] = src[0] + ... + src[i] // The back_inserter function acts on the dst container and provides an iterator partial_sum(src.begin(), src.end(), back_inserter(dst)); for (unsigned int i = 0; i < dst.size(); i++) cout << dst[i] << " ";
Use lower_bound to find the element in sorted array $a$ that is closest to $x$ . Example problem: UVa10487 Closest Sums

???+ note "Implementation" cpp int N = 10, a[] = {1, 1, 2, 4, 5, 5, 8, 8, 9, 9}, x = 6; // lower_bound returns the address of the first element in a greater than or equal to x; i is its index int i = lower_bound(a, a + N, x) - a; // In the following two cases, a[i] (the first element in a greater than or equal to x) is the answer: // 1. The smallest element in a is greater than or equal to x; // 2. There is an element in a greater than or equal to x, and the first such element (a[i]) // is closer to x than the first element less than x (a[i - 1]); // Otherwise, a[i - 1] (the first element in a less than x) is the answer if (i == 0 || (i < N && a[i] - x < x - a[i - 1])) cout << a[i]; else cout << a[i - 1];
Use sort and unique to find the $k$ -th smallest value in array $a$ (note: repeated values count only once, so this problem is not finding the $k$ -th smallest element). Example problem: Luogu P1138 The k-th Smallest Integer

???+ note "Implementation" cpp int N = 10, a[] = {1, 3, 3, 7, 2, 5, 1, 2, 4, 6}, k = 3; sort(a, a + N); // unique returns the address after the last element of the deduplicated array; cnt is its deduplicated length int cnt = unique(a, a + N) - a; cout << a[k - 1];

STL Algorithms

Usage examples