C++, lesson 12
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.
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.
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.
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.
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.
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 42std::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 3Input:
4
mia 120
leo 95
ava 120
zoe 30
Output:
1. ava 120
2. mia 120
3. leo 95
4. zoe 30Input:
6
52 48 61 48 75 50
45 50
60 100
80 90
Output:
3
2
0