Skip to content
Tutorials Center
My learning

Topics

Lesson 107 of 171 ยท The Standard Library (STL)

Algorithms: Searching, Sorting and Counting

Learn C++ STL algorithms for sorting and searching - sort, stable_sort, partial_sort, nth_element, find_if, binary_search, lower_bound, count_if, min_element, any_of.

The header <algorithm> holds more than a hundred ready-made, heavily optimized algorithms. This lesson covers the ones you'll use every day to put data in order and ask questions about it: sorting (sort, stable_sort, partial_sort, nth_element), searching unsorted data (find, find_if, search, adjacent_find), searching sorted data in logarithmic time (binary_search, lower_bound, upper_bound, equal_range), counting (count, count_if), checking conditions (all_of, any_of, none_of) and finding extremes (min_element, max_element, minmax_element, std::clamp).

Each algorithm comes in two flavors. The classic form takes an iterator pair, std::sort(v.begin(), v.end()), and works with every C++ version. The C++20 ranges form takes the whole container, std::ranges::sort(v), checks its requirements with concepts, and accepts an optional projection that picks the field to compare. This lesson mostly uses the ranges form because it's shorter and safer; the Ranges and Views lesson goes deeper into the ranges library itself. You'll pass a lot of lambdas and function objects, so make sure those lessons feel familiar.

Sorting with std::sort

std::sort arranges a range in ascending order using <, or in whatever order a comparator you supply defines. It runs in O(n log n) comparisons, guaranteed since C++11 (GCC uses introsort: quicksort that falls back to heapsort when it detects a bad case). It needs random-access iterators, so it works on std::vector, std::array, std::deque, std::string and C arrays, but not on std::list (which has its own sort() member).

std::sort is not stable: elements that compare equal may end up in any order relative to each other.

C++ sort with comparators and projections

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The multi-key comparator uses std::tie to build tuples of references, which compare lexicographically: first by the first element, then by the second if the first ones are equal. Swapping a and b inside the tie flips the direction for that key only, so std::tie(b.rating, a.title) < std::tie(a.rating, b.title) means "higher rating first, then alphabetical title". std::pair and std::tuple explains std::tie in detail.

The comparator must be a strict weak ordering

A comparator must behave like <: comp(a, a) must be false, and if a comes before b and b before c, then a must come before c. The most common violation is writing <= instead of <:

C++
std::ranges::sort(v, [](int a, int b) { return a <= b; });   // WRONG: undefined behavior

With <=, two equal elements each claim to come before the other. std::sort relies on the rule to stop its inner loops, so a bad comparator can read past the end of the vector and crash, not just produce a wrong order. Comparators that use floating-point values containing NaN break the rule the same way, since every comparison with NaN is false.

stable_sort, partial_sort and nth_element

Three relatives cover the cases where full sorting is either not enough or too much:

  • std::stable_sort keeps equal elements in their original relative order. Use it when you sort by one key after another, or when the input order carries meaning (for example, arrival time). It's O(n log n) with extra memory, O(n logยฒ n) without.
  • std::partial_sort(first, middle, last) sorts only the smallest middle - first elements into place; the rest end up in an unspecified order. Top-k in O(n log k).
  • std::nth_element(first, nth, last) puts the element that would be at nth in a sorted range exactly there, with everything before it no greater and everything after it no smaller. It runs in O(n) on average and is the fastest way to find a median or a percentile.
C++ stable_sort, partial_sort and nth_element

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The orders print as bob:1 dee:1 fay:1 ann:2 eve:2 cid:3: all priority-1 orders come first, and within each priority the original arrival order survives. Plain std::sort is allowed to shuffle bob, dee and fay.

Choose by what you actually need. Sorting a million elements just to read the median wastes work that nth_element skips, and partial_sort beats a full sort when k is much smaller than n.

Searching unsorted data

When the data isn't sorted, searching is a linear scan, O(n). The algorithms return an iterator to the match, or the end iterator if there's none. Always compare with end() before dereferencing.

Algorithm Finds
find(r, value) the first element equal to value
find_if(r, pred) / find_if_not(r, pred) the first element where pred is true / false
find_last / find_last_if (C++23, ranges only) the last such element, returned as a subrange
adjacent_find(r) the first pair of equal neighbors
search(r, pattern) the first occurrence of a subsequence
find_first_of(r, set) the first element that matches any element of set
ranges::contains(r, value) (C++23) just true/false
C++ find, find_if, search and contains

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Notice that std::ranges::search and find_last return a subrange (a begin/end pair) rather than one iterator, because the result naturally has a length. Containers with their own lookup, such as std::set, std::map and std::unordered_map, should use their member find or contains: those are O(log n) or O(1), while std::ranges::find on them would still be a linear scan.

Binary search on sorted data

On a sorted random-access range, you can find things in O(log n) comparisons with binary search. A million elements take about 20 comparisons instead of up to a million. The family:

  • binary_search(r, value): only true or false.
  • lower_bound(r, value): the first element not less than value (>= value). This is also where value should be inserted to keep the range sorted.
  • upper_bound(r, value): the first element greater than value.
  • equal_range(r, value): both at once, as a subrange of all elements equal to value.

The range must be sorted by the same comparator you pass to the search. Calling these on unsorted data doesn't fail loudly; it silently returns wrong answers.

C++ lower_bound, upper_bound and equal_range

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The grade table is a classic upper_bound trick: the number of thresholds that are <= score is the index of the grade. It replaces a chain of if/else if with one O(log n) call, and adding a grade boundary means adding one number.

lower_bound on a std::vector that you keep sorted with insert is a common way to build a sorted vector: lookups are fast and cache-friendly, though each insertion is O(n). For many insertions and lookups interleaved, a std::set or std::map (with their member lower_bound) is the better fit; see std::map.

Counting and checking conditions

  • count(r, value) and count_if(r, pred) return how many elements match.
  • all_of, any_of and none_of return a bool and stop as soon as the answer is known.

On an empty range, all_of and none_of return true and any_of returns false. That follows logic ("every element of nothing is red" is vacuously true), but it surprises people who use all_of as a "valid input" check: an empty list of passwords passes "all passwords are long enough".

C++ count_if, all_of, any_of and none_of

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

count and count_if return a signed difference type (std::ptrdiff_t for vectors), not size_t. That's convenient for arithmetic, but compare it with v.size() carefully to avoid signed/unsigned warnings; std::ssize(v) gives a signed size.

Minimum and maximum

For two or a handful of values, use std::min, std::max and std::minmax. For a whole range, use std::ranges::min_element, max_element and minmax_element, which return iterators, so you learn where the extreme value is. C++20 also lets you write std::ranges::min(v) and std::ranges::max(v) to get the value directly (the range must not be empty). Finally, std::clamp(x, low, high) (C++17) limits a value to an interval.

C++ min_element, max_element, minmax and clamp

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

With duplicates, min_element returns the first smallest element and max_element the first largest one, while minmax_element returns the first smallest and the last largest. Also beware of std::min and std::max returning references: const auto& m = std::max(a, b + 1); can dangle, because b + 1 is a temporary that dies at the end of the statement. Store the result by value.

More catalogue entries: find_end, mismatch, is_sorted_until, is_permutation, partition_point

A few more read-only algorithms round out the family. None changes the data; each answers one precise question.

Algorithm Answers Returns
find_end(r, pattern) where does the last occurrence of the pattern start? a subrange for ranges::find_end (empty at the end if absent); an iterator for std::find_end
mismatch(a, b) where do two sequences first differ? a pair of iterators, one into each sequence
is_sorted_until(r) how far is the range sorted? an iterator to the first element that breaks the order
is_permutation(a, b) does b contain the same elements as a, in any order? bool
partition_point(r, pred) where does a partitioned range change from "true" to "false"? an iterator, found in O(log n)

find_end is the mirror image of search, which finds the first occurrence. partition_point is binary search for any yes/no rule, as long as every element for which the predicate holds comes before every element for which it does not. lower_bound is the special case where the rule is "less than the value".

C++ Catalogue extras

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

is_permutation is quadratic in the worst case when the elements can only be compared with ==, so for large inputs sort or count the elements instead. The four-iterator form of mismatch stops at the shorter range, which is the safe one to use.

Complexity cheat sheet

Task Algorithm Cost
Full sort sort O(n log n)
Sort keeping equal order stable_sort O(n log n)
Smallest k in order partial_sort O(n log k)
k-th element, median nth_element O(n) average
Search unsorted find, find_if, contains O(n)
Search sorted binary_search, lower_bound, equal_range O(log n)
Count matches count, count_if O(n)
Check a condition all_of, any_of, none_of O(n), stops early
Extremes min_element, max_element, minmax_element O(n)

If you search the same data many times, sorting it once (O(n log n)) and then using binary search (O(log n) each) quickly beats repeated linear scans. If you only search once, a single find is cheaper than sorting.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. std::vector<int> v{10, 20, 20, 30}; What do lower_bound(v, 20) and upper_bound(v, 20) point to?

    lower_bound finds the first element not less than 20 (index 1); upper_bound finds the first element greater than 20 (index 3, the 30).
  2. 2. What is wrong with sorting using the comparator [](int a, int b) { return a <= b; }?

    A comparator must return false for equal elements. With <= each equal element claims to come first, which can make std::sort read out of bounds.
  3. 3. You need the median of ten million numbers and do not care about the order of the others. Which algorithm is the best fit?

    nth_element places the median exactly in O(n) average time without fully sorting the rest.
  4. 4. What does std::ranges::all_of(std::vector<int>{}, [](int x) { return x > 0; }) return?

    all_of on an empty range is vacuously true; none_of is also true and any_of is false.
  5. 5. After std::ranges::stable_sort(people, {}, &Person::age), two people with the same age appear in what order?

    stable_sort guarantees that equal elements keep their original relative order. Plain sort does not.

Summary

  • std::sort is O(n log n), not stable, and needs random-access iterators; the comparator must behave like <, never <=.
  • std::stable_sort keeps equal elements in order, partial_sort finds the top k, and nth_element finds a median or percentile in O(n).
  • find, find_if, search, adjacent_find and ranges::contains scan unsorted data in O(n) and return end() when nothing matches.
  • On sorted data, binary_search, lower_bound, upper_bound and equal_range work in O(log n), but only with the comparator the data was sorted by.
  • count/count_if count matches; all_of/any_of/none_of stop early, and all_of is true for an empty range.
  • min_element/max_element/minmax_element return iterators, ranges::min/max return values, and std::clamp limits a value to a range. Projections such as &Book::year pick the field to compare.

Next: Algorithms: Transforming and Modifying, where you'll copy, transform, fill, remove, deduplicate, reverse, rotate and shuffle ranges.