Skip to content

Intermediate · The Standard Template Library (STL) · topic 25 of 42 · 35 min

STL algorithms: sort, find, count, accumulate and binary search

Explanation

<algorithm> and <numeric> give tested, fast functions that work on iterator ranges: sort, find, count, min_element, max_element, reverse, unique, accumulate, lower_bound and many more. Use them instead of hand-written loops: the code is shorter, clearer and less buggy. Custom ordering is passed as a comparison function, often a lambda.

Why use algorithms?

You could write your own loop to find the maximum mark or sort a list. But hand-written loops are where off-by-one bugs live, and a reader must study each loop to see what it does. std::max_element(v.begin(), v.end()) says what it does in its name and has been tested by millions of programs. The C++ Core Guidelines advise: prefer standard algorithms to raw loops.

Sorting

cpp
#include <algorithm>
#include <functional>
#include <vector>

std::vector<int> marks = {72, 95, 60, 88};
std::sort(marks.begin(), marks.end());                       // 60 72 88 95
std::sort(marks.begin(), marks.end(), std::greater<int>());  // 95 88 72 60

struct Student { std::string name; int marks; };
std::vector<Student> cls = {{"Asha", 88}, {"Ravi", 95}, {"Meena", 88}};
std::sort(cls.begin(), cls.end(), [](const Student& a, const Student& b) {
    if (a.marks != b.marks) return a.marks > b.marks;   // higher marks first
    return a.name < b.name;                              // then by name
});
// Ravi 95, Asha 88, Meena 88
std::sort is O(n log n). The comparator must return true when a should come BEFORE b.
Careful: A comparator must be a "strict weak ordering": use < or >, never <= or >=. A comparator like [](int a, int b) { return a <= b; } breaks the rules and can make std::sort crash or loop forever on inputs with equal elements.

std::sort is not stable: equal elements may change their relative order. If you need equal elements to keep their original order (for example sorting by marks while keeping roll-number order for ties), use std::stable_sort.

Searching and counting

cpp
#include <algorithm>
#include <numeric>

std::vector<int> v = {4, 8, 15, 16, 23, 42};
auto it = std::find(v.begin(), v.end(), 16);          // iterator to 16, or v.end()
int evens = std::count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });   // 4
auto [mn, mx] = std::minmax_element(v.begin(), v.end());                            // *mn 4, *mx 42
long long total = std::accumulate(v.begin(), v.end(), 0LL);                          // 108
bool anyBig = std::any_of(v.begin(), v.end(), [](int x) { return x > 40; });        // true
accumulate is in <numeric>. Pass 0LL (not 0) as the start value to sum in long long and avoid overflow.
Careful: std::accumulate(v.begin(), v.end(), 0) on a vector<double> sums in int and truncates every step, because the type comes from the start value. Use 0.0 for doubles and 0LL for big integer totals.

Binary search on sorted data

cpp
std::vector<int> sorted = {10, 20, 20, 20, 30, 40};
bool has = std::binary_search(sorted.begin(), sorted.end(), 30);        // true
auto lo = std::lower_bound(sorted.begin(), sorted.end(), 20);   // first element >= 20 (index 1)
auto hi = std::upper_bound(sorted.begin(), sorted.end(), 20);   // first element > 20 (index 4)
std::cout << hi - lo << '\n';                                    // 3 copies of 20
Binary search halves the range each step: O(log n). The range MUST already be sorted with the same ordering.
Think of it like this: Binary search is how you find a word in a dictionary: open the middle, decide if your word is before or after, and throw away half the book each time. Twenty halvings are enough for a million words.

Rearranging

  • std::reverse(v.begin(), v.end()) reverses in place.
  • std::unique removes consecutive duplicates (sort first to remove all duplicates), returning the new end; follow it with erase.
  • std::rotate, std::partition and std::nth_element (find the k-th smallest in O(n) on average) are worth knowing for interviews.
  • std::next_permutation steps through all orderings of a sorted range, handy for brute-force contest problems.
  • std::fill and std::iota (from <numeric>) fill a range with one value or with 0, 1, 2, ...
cpp
std::vector<int> ids = {5, 3, 5, 1, 3};
std::sort(ids.begin(), ids.end());                          // 1 3 3 5 5
ids.erase(std::unique(ids.begin(), ids.end()), ids.end());  // 1 3 5
The standard way to remove all duplicates from a vector.

Complexity summary

AlgorithmTime
sort, stable_sortO(n log n)
find, count, accumulate, min/max_element, reverse, uniqueO(n)
binary_search, lower_bound, upper_bound (sorted, random access)O(log n)
nth_elementO(n) on average
Tip: Sorting once (O(n log n)) and then answering many queries with lower_bound (O(log n) each) is a pattern that turns many "too slow" solutions into fast ones.

Need help?

Stuck on a word or an idea? Search this course, or every course, and jump straight to the explanation or a worked question.

Try:

Watch the lesson

STL algorithms: sort, find, count, accumulate and binary search · 1/6

STL algorithms

The STL algorithms are tested, fast functions for common jobs. Prefer them to hand-written loops.

Prefer a video by a teacher? Find free videos on “c++ stl algorithms sort lower_bound accumulate lambda comparator tutorial” on YouTube ↗

In real life: A college merit list

For admissions, a college sorts applicants by entrance score (highest first), breaks ties by date of birth (older first), and then uses lower_bound on the sorted cut-off list to tell each applicant which category cut-off they cleared. All of it is a few lines of STL.

cpp
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Applicant { std::string name; int score; int birthYear; };

int main() {
    std::vector<Applicant> list = {{"Asha", 182, 2006}, {"Ravi", 190, 2007}, {"Kiran", 182, 2005}};
    std::sort(list.begin(), list.end(), [](const Applicant& a, const Applicant& b) {
        if (a.score != b.score) return a.score > b.score;
        return a.birthYear < b.birthYear;      // older first on a tie
    });
    for (const auto& a : list) std::cout << a.name << ' ' << a.score << '\n';
}
// Ravi 190
// Kiran 182
// Asha 182
One comparator expresses the whole tie-breaking rule.

Practice (0/4 done)

Task 1 · Question

std::vector<int> v = {3, 1, 2}; std::sort(v.begin(), v.end()); What is v?

Task 2 · Question

What does this print? std::vector<int> v = {1, 3, 3, 3, 7}; auto a = std::lower_bound(v.begin(), v.end(), 3); auto b = std::upper_bound(v.begin(), v.end(), 3); std::cout << (a - v.begin()) << " " << (b - a);

Task 3 · Question

std::vector<double> p = {1.5, 2.5}; What is std::accumulate(p.begin(), p.end(), 0)?

Task 4 · Practice

Read n and then n prices. Answer q queries: for each budget b, print how many items cost at most b. Sort once, then use std::upper_bound for each query, so the whole program is O((n + q) log n).

Quick quiz

Question 1

1.What must be true before using std::binary_search or std::lower_bound?

Question 2

2.Which algorithm keeps equal elements in their original order?

Question 3

3.What is the time complexity of std::sort?

Question 4

4.What does std::unique do on {1, 1, 2, 1}?

Question 5

5.Why is [](int a, int b) { return a <= b; } a bad comparator?

Read more (free)

Open a question to see the answer and why. The first ones are this topic's own quiz, so try the quiz above before you peek.

What must be true before using std::binary_search or std::lower_bound?

Answer: The range is sorted (with the same ordering)

Binary search relies on sorted order to throw away halves.

Which algorithm keeps equal elements in their original order?

Answer: std::stable_sort

stable_sort is stable; sort is not guaranteed to be.

What is the time complexity of std::sort?

Answer: O(n log n)

The standard requires O(n log n) comparisons.

What does std::unique do on {1, 1, 2, 1}?

Answer: Removes only consecutive duplicates, giving {1, 2, 1} at the front and returns the new end

unique only collapses runs of equal neighbours; sort first to remove all duplicates.

Why is [](int a, int b) { return a <= b; } a bad comparator?

Answer: It is not a strict weak ordering, so std::sort may misbehave or crash

For equal elements it says each comes before the other, which breaks sort's assumptions.

Why can you not call std::sort on a std::list?Related

Answer: std::sort needs random-access iterators; list iterators are only bidirectional

Use the member function list.sort() instead.

From Iterators: the glue between containers and algorithms

What must be true for binary search to work?Related

Answer: The array is sorted

Binary search relies on sorted order.

From Two-dimensional arrays and array algorithms

Which must be true for binary search?Related

Answer: The array is sorted

It relies on sorted order.

From 2D arrays and classic array algorithms

At most how many steps does binary search need on 1,000,000 sorted items?Related

Answer: About 20

Each step halves the range; 2²⁰ is just over a million.

From Binary search

Pass the quiz (60% or more) or mark this topic as done when you are ready.

Your progress is saved on this device only.

Next: Templates: code for any type →

Next steps

  1. This is the last topic of “The Standard Template Library (STL)”. The module exam comes next.
  2. Module 6 exam: The STL · 13 questions · 25 min, without help. 5 topics of this module still to finish first.
  3. Then the next module, Templates, smart pointers and move semantics. 42 topics left in the course before the final exam.

← Previous: Iterators: the glue between containers and algorithms