Skip to content

STL Algorithms

The STL provides about 100 template functions implementing algorithms, mostly included in <algorithm>, with some also in <numeric> and <functional>. For a complete list of functions, please refer to the reference manual. For sorting-related functions, you can refer to the corresponding page on sorting.

  • 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 container after deduplication; the original container size remains unchanged. Using it with sort enables complete container deduplication.

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

    random_shuffle function has been removed in the latest C++ standard

    random_shuffle was deprecated since C++14 and removed in C++17.

    In C++11 and newer standards, you can use the shuffle function instead of the original random_shuffle. Usage: shuffle(v.begin(), v.end(), rng) (the last parameter is the random number generator used, typically a Mersenne Twister pseudo-random number generator mt19937 seeded with a true random number generator random_device).

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

  • sort: Sorting. sort(v.begin(), v.end(), cmp) or sort(a + begin, a + end, cmp), where end is the position one past the last element of the array to sort, and cmp is a custom comparison function.

  • stable_sort: Stable sort, usage same as sort().

  • nth_element: Partition a range as specified, i.e., find the \(n\)-th largest element in the sequence such that all elements to its left are less than it and all to its right are greater 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: Ordered merge of two (sorted) sequences into an insert iterator of a third sequence. merge(v1.begin(), v1.end(), v2.begin(), v2.end() ,back_inserter(v3)).

  • inplace_merge: In-place merge of two ranges (already sorted with the less-than operator): [first,middle), [middle,last) into a single sorted sequence. inplace_merge(v.begin(), v.begin() + middle, v.end()).

  • lower_bound: Perform binary search on a sorted sequence, returning an iterator to the position of the first element greater than or equal to \(x\). If no such element exists, returns the end iterator. lower_bound(v.begin(),v.end(),x).

  • upper_bound: Perform binary search on a sorted sequence, returning an iterator to the position of the first element greater than \(x\). If no such element exists, returns the end iterator. upper_bound(v.begin(),v.end(),x).

    Time complexity of lower_bound and upper_bound

    In ordinary arrays, the time complexity of these two functions is \(O(\log n)\). However, in associative containers like set, directly calling lower_bound(s.begin(),s.end(),val) has a time complexity of \(O(n)\).

    Associative containers like set have their own encapsulated lower_bound functions (like s.lower_bound(val)), which have a time complexity of \(O(\log n)\).

  • next_permutation: Change the current permutation to the next permutation in the full permutation order. If the current permutation is already the last permutation in the full order (elements in completely descending order), the function returns false and changes the permutation to the first permutation in the full order (elements in completely ascending order); otherwise, it 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 in the full permutation order. Usage 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

  • Using next_permutation to generate all permutations of \(1\) to \(9\). Example problem: Luogu P1706 Full Permutation Problem

    Implementation 
    1
2
3
4
5
    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));
    • Using lower_bound and upper_bound to find the boundaries of elements less than \(x\), equal to \(x\), and greater than \(x\) in a sorted array \(a\).
    Implementation 
    1
2
3
4
5
    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;
    • Using partial_sum to compute the prefix sums of elements in \(src\) and store them in \(dst\).
    Implementation 
    1
2
3
4
5
    vector<int> src = {1, 2, 3, 4, 5}, dst;
// Compute prefix sums of elements in src, dst[i] = src[0] + ... + src[i]
// back_inserter function acts on the dst container, providing an iterator
partial_sum(src.begin(), src.end(), back_inserter(dst));
for (unsigned int i = 0; i < dst.size(); i++) cout << dst[i] << " ";
    • Using lower_bound to find the element closest to \(x\) in a sorted array \(a\). Example problem: UVa10487 Closest Sums
    Implementation 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    int N = 10, a[] = {1, 1, 2, 4, 5, 5, 8, 8, 9, 9}, x = 6;
// lower_bound will return 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 exists an element greater than or equal to x in a, 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];
    • Using sort and unique to find the \(k\)-th smallest value in array \(a\) (note: duplicate values are counted only once, so this is not finding the \(k\)-th smallest element). Example problem: Luogu P1138 The k-th Smallest Integer
    Implementation 
    1
2
3
4
5
    int N = 10, a[] = {1, 3, 3, 7, 2, 5, 1, 2, 4, 6}, k = 3;
sort(a, a + N);
// unique returns the address past the last element of the deduplicated array, cnt is the length after deduplication
int cnt = unique(a, a + N) - a;
cout << a[k - 1];
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用