Learn/C++/12. Sorting and searching
Lesson 12 of 15
Sign in

C++, lesson 12

Sorting and searching

The <algorithm> header is full of ready-made, well-tested functions. Sorting and searching are the ones you will reach for most. They work on iterator ranges: a pair of positions, written v.begin() (the first element) and v.end() (one past the last). Passing a range instead of a container lets the same function work on vectors, arrays, strings and more.

std::sort

By default std::sort uses <, so numbers go smallest first and strings go in dictionary order (by character code, so "Zoe" comes before "adam").

2 exercises to try what you just read.

Exercise 1

Leaderboard

Press Ctrl Enter or Check to test your code.

Exercise 2

Speed camera

Press Ctrl Enter or Check to test your code.

Custom order with a lambda

To sort differently, pass a third argument: a function that takes two elements and returns true if the first should come before the second. The easiest way to write one is a lambda, an unnamed function written right where you need it:

The [] starts the lambda, then come the parameters and the body. For records, compare the most important field first, and fall back to the next field on a tie:

The comparison must behave like <: it must return false when both elements are equal. Using >= or <= breaks that rule and can make std::sort misbehave or even crash.

Stable sorting

std::sort doesn't promise anything about the order of elements that compare equal. std::stable_sort does: equal elements keep their original relative order. That lets you sort by one key while preserving an earlier ordering, for example keeping players in the order they signed up when their scores tie.

Binary search

Once data is sorted, you can find things in about log₂(n) steps instead of n. The standard library offers three functions, all of which require the range to be sorted with the same ordering:

  • std::binary_search(first, last, value) returns true if value is present.
  • std::lower_bound(first, last, value) returns an iterator to the first element not less than value, which is where value is or would be inserted.
  • std::upper_bound(first, last, value) returns an iterator to the first element greater than value.

Subtracting iterators gives a distance, so upper_bound - lower_bound counts the copies of a value, and lower_bound(...) - v.begin() counts how many elements are smaller than it. These tricks turn many "how many..." questions into two fast searches.

Further reading

  • cppreference: std::sort
  • cppreference: std::stable_sort
  • cppreference: std::lower_bound
  • cppreference: std::upper_bound
  • cppreference: std::binary_search
  • cppreference: Lambda expressions

Read a count n, then n lines of name score (name is one word). Sort the players by score, highest first; equal scores are ordered by name using normal string <. Print the ranking as rank. name score.

A speed camera logged the speeds of passing cars. Read a count n, then n speeds (whole numbers). Sort them once. Then answer queries until the input ends. Each query is two numbers low high; print how many logged speeds s satisfy low <= s <= high.

Use std::lower_bound and std::upper_bound: the answer is the distance between them.

#include <algorithm>

std::vector<int> times{42, 7, 19, 3};
std::sort(times.begin(), times.end());          // 3 7 19 42
std::sort(times.begin(), times.end(), [](int a, int b) {
    return a > b;                                // largest first
});
struct Player {
    std::string name;
    int score;
};

std::sort(players.begin(), players.end(), [](const Player& a, const Player& b) {
    if (a.score != b.score) {
        return a.score > b.score;                // higher score first
    }
    return a.name < b.name;                      // then A to Z
});
std::vector<int> v{1, 2, 4, 5, 5, 6};
bool has4 = std::binary_search(v.begin(), v.end(), 4);    // true
auto lo = std::lower_bound(v.begin(), v.end(), 5);        // points at the first 5
auto hi = std::upper_bound(v.begin(), v.end(), 5);        // points at the 6
std::cout << hi - lo << '\n';                             // 2 copies of 5
std::cout << lo - v.begin() << '\n';                      // index 3
Input:
4
mia 120
leo 95
ava 120
zoe 30
Output:
1. ava 120
2. mia 120
3. leo 95
4. zoe 30
Input:
6
52 48 61 48 75 50
45 50
60 100
80 90
Output:
3
2
0