Sorting and searching

Sorting is the algorithm that makes the others faster: once a range is ordered, a search costs a few comparisons instead of a scan. std::sort does it in place with a comparator you supply, and lower_bound turns the order into a binary search.

The comparator is the important part. It decides the order, it must be a strict weak ordering, and the whole program depends on it being consistent. This lesson writes comparators as functions, lambdas and function objects, and then breaks the call that sorts.

The comparator is the part to get right: a mistaken order produces a sorted range that looks correct until a search depends on it, which is why the binary searches below are written for the same order as the sort.

sort

std::sort takes two iterators and orders the range with operator<. The program shuffles a vector of ints into ascending order and prints the result.

The algorithm is not stable: equal elements may end up in any order. That is fine for ints and matters for records that should keep their insertion order, which is what stable_sort is for.

sort needs random access iterators, so it works on a vector, a deque, a std::array and a C array, not on a list. A list has its own sort member that relinks nodes instead of moving values.

#include <algorithm> #include <iostream> #include <vector> int main() { std::vector<int> values{5, 1, 4, 2, 3}; std::sort(values.begin(), values.end()); for (int value : values) { std::cout << value << ' '; } std::cout << '\n'; }

g++ -std=c++23 -Wall -Wextra sort.cpp -o sort
./sort

1 2 3 4 5

A comparator

The third argument of sort is a callable that answers "is a before b?". The program sorts words by length, and words of the same length keep the order std::sort happened to leave them in because the comparator cannot tell them apart.

std::greater<> sorts in descending order and std::less<> is the default; both are function objects from <functional>, and both read better than a lambda that does the same comparison.

A comparator must be a strict weak ordering: it must be irreflexive, transitive and consistent. A comparator that returns true for equal elements passes the compiler and produces undefined behaviour at run time.

#include <algorithm> #include <iostream> #include <string> #include <vector> int main() { std::vector<std::string> words{"pear", "fig", "apple", "kiwi"}; std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) { return a.size() < b.size(); }); for (const auto& word : words) { std::cout << word << ' '; } std::cout << '\n'; }

g++ -std=c++23 -Wall -Wextra comparator.cpp -o comparator
./comparator

fig pear kiwi apple

stable_sort keeps the order

stable_sort orders the range and keeps the relative order of elements that the comparator considers equal. The program sorts records by score and the two records with the same score stay in the order they were written.

The cost is memory or time: stable_sort may allocate a temporary buffer where sort does not. For small ranges the difference is invisible, and for records with a natural order it is worth the price.

The program's records are a small struct with a name and a score, printed after the sort. The names show which order was preserved.

#include <algorithm> #include <iostream> #include <string> #include <vector> struct record { std::string name; int score; }; int main() { std::vector<record> records{{"ada", 10}, {"bob", 20}, {"cyd", 10}}; std::stable_sort(records.begin(), records.end(), [](const record& a, const record& b) { return a.score < b.score; }); for (const auto& r : records) { std::cout << r.name << ' '; } std::cout << '\n'; }

g++ -std=c++23 -Wall -Wextra stable.cpp -o stable
./stable

ada cyd bob

lower_bound and binary_search

lower_bound returns the first element that is not less than the value, and binary_search answers whether the value is present. Both need a sorted range and both cost a logarithmic number of comparisons.

The program sorts a vector, finds the position of 7 with lower_bound and checks 9 with binary_search. The position is an iterator, and the distance from begin is the index.

lower_bound is the more useful of the two: it gives the insertion point, which is how a sorted vector stays sorted, and it tells you whether the element is there by comparing the result with end and the value.

#include <algorithm> #include <iostream> #include <vector> int main() { std::vector<int> values{9, 3, 7, 1, 5}; std::sort(values.begin(), values.end()); auto it = std::lower_bound(values.begin(), values.end(), 7); std::cout << std::distance(values.begin(), it) << '\n'; std::cout << std::binary_search(values.begin(), values.end(), 9) << ' ' << std::binary_search(values.begin(), values.end(), 4) << '\n'; }

g++ -std=c++23 -Wall -Wextra binary.cpp -o binary_search_demo
./binary_search_demo

3
1 0

The container is not a range

sort takes two iterators, not a container. Passing the vector itself is the most common first mistake, and the message says there is no matching function and lists the four candidates.

The program sorts values instead of values.begin(), values.end(). The first candidate in the note has two parameters, which is the hint: an algorithm needs the start and the end of the range.

The same shape of error appears for find, count and transform. The fix is always the pair begin() and end(), or std::ranges::sort in lesson 058, which does take the container.

#include <algorithm> #include <vector> int main() { std::vector<int> values{3, 1, 2}; std::sort(values); return values[0]; }

g++ -std=c++23 -Wall -Wextra container_arg.cpp -o container_arg

container_arg.cpp: In function 'int main()':
container_arg.cpp:7:14: error: no matching function for call to 'sort(std::vector<int>&)'
7 | std::sort(values);
| ~~~~~~~~~^~~~~~~~
container_arg.cpp:7:14: note: there are 4 candidates
In file included from /usr/include/c++/15.2.0/algorithm:63,
from container_arg.cpp:1:
/usr/include/c++/15.2.0/bits/stl_algo.h:4831:5: note: candidate 1: 'template<class _RAIter> constexpr void std::sort(_RAIter, _RAIter)'
4831 | sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
| ^~~~
/usr/include/c++/15.2.0/bits/stl_algo.h:4831:5: note: candidate expects 2 arguments, 1 provided
/usr/include/c++/15.2.0/bits/stl_algo.h:4862:5: note: candidate 2: 'template<class _RAIter, class _Compare> constexpr void std::sort(_RAIter, _RAIter, _Compare)'
4862 | sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
| ^~~~
/usr/include/c++/15.2.0/bits/stl_algo.h:4862:5: note: candidate expects 3 arguments, 1 provided
In file included from /usr/include/c++/15.2.0/algorithm:89:
/usr/include/c++/15.2.0/pstl/glue_algorithm_defs.h:293:1: note: candidate 3: 'template<class _ExecutionPolicy, class _RandomAccessIterator, class _Compare> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> std::sort(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Compare)'
293 | sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp);
| ^~~~
/usr/include/c++/15.2.0/pstl/glue_algorithm_defs.h:293:1: note: candidate expects 4 arguments, 1 provided
/usr/include/c++/15.2.0/pstl/glue_algorithm_defs.h:297:1: note: candidate 4: 'template<class _ExecutionPolicy, class _RandomAccessIterator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> std::sort(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator)'
297 | sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last);
| ^~~~
/usr/include/c++/15.2.0/pstl/glue_algorithm_defs.h:297:1: note: candidate expects 3 arguments, 1 provided

Exercises

  1. Sort a vector of ints in descending order with std::greater<> and print it.
  2. Sort records by score descending and then by name ascending with one comparator.
  3. Use lower_bound to insert 4 into a sorted vector at the right position without sorting again.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does std::sort require of the range's iterators?

    Answer

    Random access

    The algorithm jumps around the range, which needs random-access iterators.

  2. What must a comparator return?

    Answer

    A bool that is true when the first argument comes before the second

    The algorithms only ask 'does a come before b?', which is a strict weak ordering.

  3. What does std::lower_bound return?

    Answer

    The first element that is not less than the key

    The function finds the insertion point of the key in the sorted range.

  4. What does stable_sort keep that sort does not promise?

    Answer

    The relative order of elements that compare equal

    A stable sort keeps equal elements in their original order, which matters for multi-key records.

  5. What does this program print? #include <algorithm> #include <iostream> #include <vector> int main() { std::vector<int> values{3, 1, 5, 2, 4}; std::sort(values.begin(), values.end()); for (int v : values) std::cout << v << ' '; }

    Answer

    1 2 3 4 5

    The sort orders the five values, and the loop prints them in that order.

  6. What does this program print? #include <algorithm> #include <iostream> #include <string> #include <vector> int main() { std::vector<std::string> words{"fig", "pear", "kiwi", "apple"}; std::stable_sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) { return a.size() < b.size(); }); for (const auto& w : words) std::cout << w << ' '; }

    Answer

    fig pear kiwi apple

    The comparator orders by length, and the two four-letter words keep their relative order because the sort is stable.

  7. What does this program print? #include <algorithm> #include <iostream> #include <vector> int main() { std::vector<int> values{1, 3, 5, 7}; auto it = std::lower_bound(values.begin(), values.end(), 5); std::cout << (it - values.begin()) << '\n'; std::cout << std::binary_search(values.begin(), values.end(), 3) << ' ' << std::binary_search(values.begin(), values.end(), 4); }

    Answer

    2 then 1 0

    The key 5 is at index 2, 3 is present and 4 is not.

  8. What does the compiler report for this call? #include <algorithm> #include <vector> int main() { std::vector<int> values{1, 2, 3}; std::sort(values); }

    Answer

    no matching function for call to 'sort(std::vector<int>&)'

    The algorithm takes a pair of iterators, and a container is not a range in this form.

  9. Why is a sorted range faster to search?

    Answer

    A binary search halves the candidates at every step

    The order lets lower_bound skip half of the remaining range each time.

  10. What does std::sort return?

    Answer

    void

    The algorithm sorts in place and returns nothing.

The code on this page was built with g++ 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container. The programs whose section shows a compiler error were compiled until that error and were not run.

Article author: Arthur Isaev