Sorting and searching in C++: comparators, tie-breaks and lower_bound
Sort with comparators, make output deterministic with tie-breaks, sort by several keys, find the top N, use lower_bound, and solve problems greedily from a table.
Half of "make the output match the spec" is sorting correctly. The other half is finding things in sorted data without scanning all of it.
std::sort with a comparator
std::sort takes a function that answers "should a come before b?":
std::sort(words.begin(), words.end(), [](const WordCount& a, const WordCount& b) {
return a.count > b.count; // most frequent first
});The comparator must be a strict weak ordering: use < or >, never <= or >=. With <=,
std::sort can read past the end of the vector.
Tie-breaks make output deterministic
The comparator above says nothing about two words that both appear 12 times, so their order is
unspecified, and a test that expects "apple" before "banana" passes on one machine and fails on
another. Always finish with a tie-break that separates different elements:
[](const WordCount& a, const WordCount& b) {
if (a.count != b.count) return a.count > b.count; // primary: count, descending
return a.word < b.word; // tie-break: alphabetical
}When a ticket says "in a fixed order", it's asking for this.
Sorting by several keys with std::tie
For several keys, std::tie compares element by element, like a dictionary does:
// Overdue first, then by due date, then by ID.
std::sort(tasks.begin(), tasks.end(), [](const Task& a, const Task& b) {
return std::tie(b.overdue, a.due, a.id) < std::tie(a.overdue, b.due, b.id);
});Swapping a and b for one key flips just that key to descending (here, true before false).
If that trick is hard to read, write the if/return chain instead: clear beats clever.
stable_sort
std::stable_sort keeps equal elements in their original order. Use it when the input order is
the tie-break, for example "sort by score; students with equal scores stay in the order they
enrolled". It's slightly slower and may allocate.
Top N without sorting everything
If you need the 10 most common words out of 50,000, sorting all of them is wasted work:
const auto n = std::min<std::size_t>(10, words.size());
std::partial_sort(words.begin(), words.begin() + n, words.end(), by_count_then_word);
words.resize(n);std::nth_element is even cheaper when you only need the n-th element, such as a median.
Binary search: lower_bound and upper_bound
On sorted data, std::lower_bound finds a position in O(log n):
std::vector<int> sorted = {10, 20, 20, 30};
auto it = std::lower_bound(sorted.begin(), sorted.end(), 20); // first element >= 20
auto end = std::upper_bound(sorted.begin(), sorted.end(), 20); // first element > 20
// [it, end) holds both 20s; it == end means "not found"std::map and std::set have their own lower_bound member; call that one, since the free
function is O(n) on their iterators. "The first key at or after x" and "the last key before x"
(std::prev of lower_bound, if it isn't begin()) are the building blocks for
intervals and hash rings.
Greedy choices from a table
Some problems are solved by walking a table, largest entry first, and taking as much as fits:
constexpr std::pair<int, std::string_view> table[] = {
{100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"}, {10, "X"}, // ... down to {1, "I"}
};
for (const auto& [value, symbol] : table) {
while (n >= value) { out += symbol; n -= value; }
}The trick is putting the special cases (90, 40) into the table so the loop never needs an if.
That's the whole of Roman numerals for Chronicle Clocks, and the same
idea gives letter grades from score thresholds.
Questions and answers
- Why does my sorted output change between runs or compilers?
- Two elements compared equal, and std::sort doesn't keep equal elements in any particular order. Add a tie-break (for example, by name) so no two different elements ever compare equal.
- What's the difference between lower_bound and upper_bound?
- On sorted data, lower_bound finds the first element not less than the value (>= value) and upper_bound the first element greater than it (> value). Together they bracket all elements equal to the value.
Practise it in a project
These projects put this guide to work, with tickets, tests and code review.
Inkwell Publishing
Manuscript statistics for Inkwell
Split manuscripts into words and find the most used ones, so Inkwell's editors can spot overused words at a glance.
- string processing
- character classes
- hash maps
- sorting with tie-breaks
Tasklane
The task list behind Tasklane
Build the core of Tasklane's to-do list: strict due dates, stable task IDs and an agenda in the right order.
- date validation
- enums
- stable IDs
- multi-key sorting
Brightpath Academy
A gradebook for Brightpath Academy
Give Brightpath's teachers letter grades, averages and a class ranking, instead of a spreadsheet full of formulas.
- conditionals
- classes
- std::map
- sorting
Pantry & Co.
Stock counts for Pantry & Co.
Track stock as goods arrive and leave Pantry's warehouse, and tell the buyers what to reorder.
- classes
- invariants
- std::map
- input validation
Read next
- Big-O in practice: amortised cost, worst cases and memory
What Big-O tells you on the job: the costs of common operations, amortised O(1), inputs that trigger the worst case, memory as a cost, and when to measure instead of guessing.
- Working with intervals: half-open ranges, overlaps, merging and gaps
Bookings, shifts, diff hunks and time slots are intervals. Use half-open ranges, test overlap with one comparison, check clashes in O(log n), merge overlapping intervals and find free gaps.