Chapter 40 of 48

STL Algorithms

We have now met all the main STL containers: vector, list, deque, array, the adaptors, set/map and their unordered cousins. Containers only store data. Most real work, like sorting, searching, counting, removing duplicates and finding the maximum, is done by the third pillar of the STL: the algorithms.

The headers <algorithm> and <numeric> give us more than a hundred ready-made, well-tested and fast functions. Learning the most important 25–30 of them saves you from writing (and debugging) the same loops again and again. It is also a must for interviews and competitive programming: "sort, then binary search" solves a surprising number of problems.


The Big Idea: Algorithms Work on Ranges, Not Containers

As we saw in Introduction to the STL, an algorithm never receives a container. It receives a pair of iterators [first, last): first points to the first element, and last points one past the last element.

    v.begin()                      v.end()
    │                              │
    ▼                              ▼
    ┌────┬────┬────┬────┬────┬────┐
    │ 72 │ 45 │ 91 │ 60 │ 88 │ 45 │  (one past the last element)
    └────┴────┴────┴────┴────┴────┘
    └── the range [first, last) ──┘

This design has three big benefits:

  • One algorithm, many containers. The same std::find works on a vector, a list, a deque, a plain array, even a string. N algorithms × M containers needs only N implementations, not N × M.

  • Part of a container. You can sort only the first 3 elements by passing v.begin(), v.begin() + 3.

  • The empty range is natural. If first == last there is nothing to do, so no special case is needed.

An STL algorithm is a function template that performs an operation on a range of elements given by iterators. Most return an iterator (for example, where something was found) and signal "not found" by returning last.

An important consequence: algorithms cannot change the size of a container, because they only see iterators, not the container itself. Keep this in mind; it explains the strange behaviour of remove later in this chapter.

Many algorithms accept an extra argument: a predicate (a function returning bool, like "is this mark a failure?") or a comparator (a function answering "should a come before b?"). We can pass a normal function, a ready-made function object such as std::greater<>(), or a lambda, a small unnamed function written right where it is needed, like [](int m) { return m < 40; }. Read it as "a function that takes int m and returns m < 40". We study lambdas fully in the Lambda Expressions chapter; here we only use this simple form.


Sorting

std::sort

std::sort(first, last) sorts a range in ascending order using operator<. Pass a comparator as the third argument to change the order.

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

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

int main() {
    std::vector<int> marks{72, 45, 91, 60, 88, 45};

    std::sort(marks.begin(), marks.end());                   // ascending
    print(marks);

    std::sort(marks.begin(), marks.end(), std::greater<>()); // descending
    print(marks);

    std::vector<std::string> names{"Ravi", "anu", "Meena", "Arjun"};
    std::sort(names.begin(), names.end());   // uses operator< of string
    for (const auto& s : names) std::cout << s << ' ';
    std::cout << '\n';

    // Sort only part of the range: the first 3 elements
    std::vector<int> v{9, 7, 5, 3, 1};
    std::sort(v.begin(), v.begin() + 3);
    print(v);
}

Output:

45 45 60 72 88 91 
91 88 72 60 45 45 
Arjun Meena Ravi anu 
5 7 9 3 1 

Points to notice:

  • std::greater<>() (from <functional>) is a function object that returns a > b, so bigger elements come first.

  • Strings are compared character by character using their character codes. All uppercase letters (A–Z are 65–90) come before lowercase letters (a–z are 97–122), which is why "anu" ends up last.

  • In the last example only 9 7 5 were sorted; 3 1 were outside the range and untouched.

How fast is it? Since C++11 the standard guarantees O(n log n) comparisons in the worst case. Library implementations use introsort: quicksort that switches to heapsort if the recursion gets too deep (so the O(n²) worst case of plain quicksort can never happen), and insertion sort for tiny pieces.

std::sort needs random-access iterators (it jumps around the range). So it works with vector, deque, array, string and plain arrays, but not with std::list, which has its own member function list.sort() (see list, deque & array). And a set or map is always sorted already.

Custom Comparators and Stability

A comparator comp(a, b) must return true if a should come before b. Suppose we sort students by marks, high to low. What happens to students with equal marks?

A sort is stable if elements that compare equal keep their original relative order. std::sort is not stable; std::stable_sort is.

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

struct Student {
    std::string name;
    int marks;
};

// Comparator: returns true if a must come BEFORE b
bool byMarksDesc(const Student& a, const Student& b) {
    return a.marks > b.marks;
}

void print(const std::vector<Student>& v) {
    for (const auto& s : v) std::cout << s.name << '(' << s.marks << ") ";
    std::cout << '\n';
}

int main() {
    // Input is in alphabetical order of names
    std::vector<Student> cls{{"Aman", 80}, {"Bina", 92}, {"Chirag", 80},
                             {"Divya", 75}, {"Esha", 92}, {"Farhan", 80}};

    std::vector<Student> a = cls;
    std::stable_sort(a.begin(), a.end(), byMarksDesc);
    print(a);   // ties keep their alphabetical order - guaranteed

    // With plain sort, make the tie-break explicit instead
    std::vector<Student> b = cls;
    std::sort(b.begin(), b.end(), [](const Student& x, const Student& y) {
        if (x.marks != y.marks) return x.marks > y.marks;  // marks high to low
        return x.name < y.name;                            // then name A to Z
    });
    print(b);
}

Output:

Bina(92) Esha(92) Aman(80) Chirag(80) Farhan(80) Divya(75) 
Bina(92) Esha(92) Aman(80) Chirag(80) Farhan(80) Divya(75) 

Both lines are the same here, but for different reasons:

  • stable_sort guarantees that Aman, Chirag and Farhan (all 80) stay in their input order, which happened to be alphabetical.

  • Plain sort with a comparator that only looked at marks might have put the three 80s in any order. Because our lambda breaks ties by name, the order is fully defined anyway.

Use stable_sort when the existing order carries meaning (for example, data already sorted by name, now sorted by marks: the classic "multi-key sort"). Its cost: O(n log n) when it can allocate a temporary buffer, and O(n log² n) if no extra memory is available.

The Golden Rule for Comparators: Strict Weak Ordering

The comparator must behave like <, never like <=. In particular, comp(a, a) must be false, and if comp(a, b) is true then comp(b, a) must be false.

// WRONG: undefined behaviour
std::sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });

// RIGHT
std::sort(v.begin(), v.end(), [](int a, int b) { return a < b; });

With <=, the call is undefined behaviour. In practice, with many equal elements, the sorting loop can run past the end of the array and crash or corrupt memory. This is a famous source of "random" crashes in competitive programming.


Searching

Linear Search: find, find_if, count, count_if

These work on any range, sorted or not, by checking elements one by one: O(n).

#include <algorithm>
#include <iostream>
#include <vector>

bool isFail(int m) { return m < 40; }

int main() {
    std::vector<int> marks{55, 32, 78, 32, 90, 15, 64};

    // Linear search: works on any range, sorted or not - O(n)
    auto it = std::find(marks.begin(), marks.end(), 78);
    if (it != marks.end())
        std::cout << "78 found at index " << (it - marks.begin()) << '\n';

    auto f = std::find_if(marks.begin(), marks.end(), isFail);
    if (f != marks.end())
        std::cout << "first failing mark: " << *f << '\n';

    std::cout << "count of 32: " << std::count(marks.begin(), marks.end(), 32) << '\n';
    std::cout << "failures: " << std::count_if(marks.begin(), marks.end(), isFail) << '\n';

    if (std::find(marks.begin(), marks.end(), 100) == marks.end())
        std::cout << "100 not found\n";
}

Output:

78 found at index 2
first failing mark: 32
count of 32: 2
failures: 3
100 not found
  • find returns an iterator to the first match, or last (here marks.end()) if there is none. Always compare with end() before dereferencing; dereferencing end() is undefined behaviour.

  • For a vector, subtracting begin() from an iterator gives the index.

  • The _if versions take a predicate instead of a value.

Binary Search on Sorted Ranges

If the range is sorted, we can do much better: O(log n) comparisons. Four algorithms do this:

AlgorithmReturnsMeaning
binary_search(f, l, x)boolIs x present?
lower_bound(f, l, x)iteratorFirst element ≥ x
upper_bound(f, l, x)iteratorFirst element > x
equal_range(f, l, x)pair of iterators{lower_bound, upper_bound}: all copies of x
index:            0    1    2    3    4    5    6
value:           10   20   20   20   30   40   50
                       ▲              ▲
             lower_bound(20)    upper_bound(20)
                       └── 3 copies ──┘     count = 4 − 1 = 3
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{10, 20, 20, 20, 30, 40, 50};   // MUST be sorted

    std::cout << std::boolalpha;
    std::cout << "binary_search 30: " << std::binary_search(v.begin(), v.end(), 30) << '\n';
    std::cout << "binary_search 35: " << std::binary_search(v.begin(), v.end(), 35) << '\n';

    auto lo = std::lower_bound(v.begin(), v.end(), 20);  // first element >= 20
    auto hi = std::upper_bound(v.begin(), v.end(), 20);  // first element >  20
    std::cout << "lower_bound(20) index: " << (lo - v.begin()) << '\n';
    std::cout << "upper_bound(20) index: " << (hi - v.begin()) << '\n';
    std::cout << "occurrences of 20: " << (hi - lo) << '\n';

    auto [first, last] = std::equal_range(v.begin(), v.end(), 20);  // C++17 binding
    std::cout << "equal_range(20): [" << (first - v.begin()) << ", "
              << (last - v.begin()) << ")\n";

    // Where would 35 go to keep v sorted?
    auto pos = std::lower_bound(v.begin(), v.end(), 35);
    std::cout << "35 would be inserted at index " << (pos - v.begin()) << '\n';

    // Value larger than everything: lower_bound returns end()
    if (std::lower_bound(v.begin(), v.end(), 99) == v.end())
        std::cout << "no element >= 99\n";
}

Output:

binary_search 30: true
binary_search 35: false
lower_bound(20) index: 1
upper_bound(20) index: 4
occurrences of 20: 3
equal_range(20): [1, 4)
35 would be inserted at index 5
no element >= 99

Why are lower_bound and upper_bound so useful?

  • binary_search only says yes/no. lower_bound tells you where, which is what you usually need.

  • upper_bound(x) − lower_bound(x) counts the copies of x in O(log n).

  • lower_bound(x) is also the position where x can be inserted while keeping the range sorted.

Two warnings. First, on an unsorted range the result is meaningless (formally, the range must be partitioned with respect to x). Second, the "O(log n)" counts comparisons; on a list, moving the iterator to the middle still costs O(n) steps. For a set or map, always call the member functions s.find(x) and s.lower_bound(x), which are O(log n), instead of std::find (O(n)) or std::lower_bound (O(n) steps on tree iterators), as explained in set & map.


Minimum, Maximum and Totals

#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> v{42, 7, 19, 88, 7, 63};

    auto mx = std::max_element(v.begin(), v.end());
    auto mn = std::min_element(v.begin(), v.end());
    std::cout << "max " << *mx << " at index " << (mx - v.begin()) << '\n';
    std::cout << "min " << *mn << " at index " << (mn - v.begin()) << '\n';

    auto [lo, hi] = std::minmax_element(v.begin(), v.end());
    std::cout << "minmax: " << *lo << ' ' << *hi << '\n';

    std::cout << "max of three: " << std::max({3, 9, 4}) << '\n';
    std::cout << "clamp(150, 0, 100): " << std::clamp(150, 0, 100) << '\n';

    // accumulate lives in <numeric>
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "sum = " << sum << '\n';

    long long product = std::accumulate(v.begin(), v.end(), 1LL,
                                        std::multiplies<>());
    std::cout << "product = " << product << '\n';

    // PITFALL: the type of the initial value decides the result type
    std::vector<double> prices{1.5, 2.5, 3.25};
    std::cout << "wrong: " << std::accumulate(prices.begin(), prices.end(), 0) << '\n';
    std::cout << "right: " << std::accumulate(prices.begin(), prices.end(), 0.0) << '\n';
}

Output:

max 88 at index 3
min 7 at index 1
minmax: 7 88
max of three: 9
clamp(150, 0, 100): 100
sum = 226
product = 216781488
wrong: 6
right: 7.25
  • min_element/max_element return an iterator (so you also get the position). With duplicates, both return the first one. Careful: minmax_element returns the first smallest but the last largest.

  • std::max({3, 9, 4}) takes an initializer list and returns a value (C++11). std::clamp(x, lo, hi) (C++17) limits a value to a range.

  • std::accumulate(first, last, init) is in <numeric>, not <algorithm>. It computes init + a0 + a1 + …. With a fourth argument it can use any operation, such as std::multiplies<>().

The accumulate trap. The running total has the type of init. With 0 (an int), every step is converted back to int:

total = 0                    (int)
total = 0 + 1.5  = 1.5  → 1  (fraction dropped)
total = 1 + 2.5  = 3.5  → 3
total = 3 + 3.25 = 6.25 → 6  ✗  (correct answer: 7.25)

The same trap applies to big integer sums: summing a vector<long long> or many large ints with init = 0 accumulates in int and can overflow, which is undefined behaviour for signed types. Use 0LL or 0.0 as needed.

C++17 also added std::reduce (in <numeric>). It is like accumulate, but it may add elements in any order or grouping, which allows parallel execution. So use it only with operations that are associative and commutative, like + on integers.


Modifying Algorithms: fill, iota, reverse, rotate, replace, transform

#include <algorithm>
#include <cctype>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

char toUpper(char c) {
    return static_cast<char>(std::toupper(static_cast<unsigned char>(c)));
}

int square(int x) { return x * x; }

int main() {
    std::vector<int> v(6);
    std::iota(v.begin(), v.end(), 1);          // 1 2 3 4 5 6   (<numeric>)
    print(v);

    std::reverse(v.begin(), v.end());          // 6 5 4 3 2 1
    print(v);

    std::rotate(v.begin(), v.begin() + 2, v.end());  // element at index 2 becomes first
    print(v);

    std::replace(v.begin(), v.end(), 6, 60);   // every 6 becomes 60
    print(v);

    std::vector<int> sq(v.size());             // destination must have room
    std::transform(v.begin(), v.end(), sq.begin(), square);
    print(sq);

    std::fill(v.begin(), v.begin() + 3, 0);    // first three become 0
    print(v);

    std::string s = "gate 2027";
    std::transform(s.begin(), s.end(), s.begin(), toUpper);  // in place
    std::cout << s << '\n';
}

Output:

1 2 3 4 5 6 
6 5 4 3 2 1 
4 3 2 1 6 5 
4 3 2 1 60 5 
16 9 4 1 3600 25 
0 0 0 1 60 5 
GATE 2027

Let us trace the less obvious ones:

  • iota(first, last, 1) (in <numeric>) fills with 1, 2, 3, …, increasing by one each time.

  • rotate(first, middle, last) makes middle the new first element. Here v was 6 5 4 3 2 1 and middle pointed to 4 (index 2), so 4 3 2 1 moved to the front and 6 5 wrapped round to the back. It is a left rotation by 2 in O(n).

  • transform(first, last, out, f) applies f to each element and writes the result to out. The destination may be the same range (in-place, as with the string).

  • We pass toupper an unsigned char, because calling std::toupper with a negative char value (other than EOF) is undefined behaviour.

The destination must already have room. Output algorithms like transform and copy overwrite elements; they never add new ones. Writing into an empty vector with sq.begin() is undefined behaviour. That is why we created sq(v.size()). The other solution, std::back_inserter, appears in the next sections.


The Remove–Erase Idiom

This is the single most asked-about STL behaviour. Remember: algorithms see only iterators, so std::remove and std::remove_if cannot delete anything. Instead they move the elements to keep to the front and return an iterator to the new "logical end". Whatever lies after that is left in a valid but unspecified state (for ints in practice usually the old values).

remove_if(v, isOdd) on   1  2  3  4  5  6  7

                         2  4  6  ?  ?  ?  ?      size is still 7!
                                  ▲
                                newEnd

v.erase(newEnd, v.end()) →  2  4  6               size 3
#include <algorithm>
#include <iostream>
#include <vector>

void print(const char* label, const std::vector<int>& v) {
    std::cout << label;
    for (int x : v) std::cout << x << ' ';
    std::cout << "(size " << v.size() << ")\n";
}

bool isOdd(int x) { return x % 2 != 0; }

int main() {
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7};

    auto newEnd = std::remove_if(v.begin(), v.end(), isOdd);
    std::cout << "kept elements: " << (newEnd - v.begin()) << '\n';
    std::cout << "size after remove_if: " << v.size() << '\n';   // unchanged!

    v.erase(newEnd, v.end());                  // now really shrink
    print("after erase:   ", v);

    // C++20: one call does both steps
    std::vector<int> w{1, 2, 3, 4, 5, 6, 7};
    auto removed = std::erase_if(w, isOdd);
    print("std::erase_if: ", w);
    std::cout << "removed " << removed << " elements\n";

    // unique removes only CONSECUTIVE duplicates, so sort first
    std::vector<int> d{3, 1, 3, 2, 1, 3};
    std::sort(d.begin(), d.end());             // 1 1 2 3 3 3
    d.erase(std::unique(d.begin(), d.end()), d.end());
    print("distinct:      ", d);
}

Output:

kept elements: 3
size after remove_if: 7
after erase:   2 4 6 (size 3)
std::erase_if: 2 4 6 (size 3)
removed 4 elements
distinct:      1 2 3 (size 3)
  • Before C++20, the idiom is v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());. It is O(n): one pass, every kept element moved at most once. (Erasing elements one by one in a loop would be O(n²) for a vector.)

  • C++20 added std::erase(container, value) and std::erase_if(container, pred), which do both steps and return how many elements were removed. Prefer them when your compiler supports C++20.

  • std::unique works the same way, but it only removes consecutive duplicates. So "sort, then unique, then erase" is the standard way to get the distinct values of a vector in O(n log n).

  • For std::list, use the member functions remove, remove_if and unique, which really delete nodes.


Checking and Copying with Predicates

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    std::vector<int> marks{55, 32, 78, 90, 15, 64};

    std::cout << std::boolalpha;
    std::cout << "all >= 10? " << std::all_of(marks.begin(), marks.end(),
                                     [](int m) { return m >= 10; }) << '\n';
    std::cout << "any == 100? " << std::any_of(marks.begin(), marks.end(),
                                      [](int m) { return m == 100; }) << '\n';
    std::cout << "none < 0? " << std::none_of(marks.begin(), marks.end(),
                                    [](int m) { return m < 0; }) << '\n';

    // copy_if into an EMPTY vector: back_inserter calls push_back for us
    std::vector<int> passed;
    std::copy_if(marks.begin(), marks.end(), std::back_inserter(passed),
                 [](int m) { return m >= 40; });
    for (int m : passed) std::cout << m << ' ';
    std::cout << '\n';

    // A lambda can use a local variable if we "capture" it with [cutoff]
    int cutoff = 60;
    auto above = std::count_if(marks.begin(), marks.end(),
                               [cutoff](int m) { return m > cutoff; });
    std::cout << "above " << cutoff << ": " << above << '\n';
}

Output:

all >= 10? true
any == 100? false
none < 0? true
55 78 90 64 
above 60: 3
  • all_of, any_of, none_of (C++11) stop as soon as the answer is known. On an empty range, all_of and none_of return true and any_of returns false (just like "for all" and "there exists" in discrete mathematics).

  • std::back_inserter(passed) (from <iterator>) is a special output iterator: each "write" through it calls passed.push_back(value). This is how an algorithm can fill an empty container without knowing the final size in advance. The Iterators chapter explains inserter iterators in detail.

  • The lambda [cutoff](int m) { return m > cutoff; } copies the local variable cutoff into itself so it can use it. A plain function could not see cutoff.


Permutations, Partial Sorting and Selection

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

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

int main() {
    std::string s = "abc";
    int count = 0;
    do {
        std::cout << s << ' ';
        ++count;
    } while (std::next_permutation(s.begin(), s.end()));
    std::cout << "\ntotal: " << count << ", s is back to: " << s << '\n';

    // Top 3 scores in order; the rest are left in unspecified order
    std::vector<int> v{40, 95, 12, 77, 63, 88, 51};
    std::partial_sort(v.begin(), v.begin() + 3, v.end(), std::greater<>());
    std::cout << "top 3: " << v[0] << ' ' << v[1] << ' ' << v[2] << '\n';

    // Median: put the middle element in its sorted position
    std::vector<int> w{40, 95, 12, 77, 63, 88, 51};
    auto mid = w.begin() + w.size() / 2;
    std::nth_element(w.begin(), mid, w.end());
    std::cout << "median: " << *mid << '\n';

    std::sort(w.begin(), w.end());
    print(w);   // check: 63 is indeed in the middle
}

Output:

abc acb bac bca cab cba 
total: 6, s is back to: abc
top 3: 95 88 77
median: 63
12 40 51 63 77 88 95 
  • next_permutation rearranges the range into the next lexicographically greater permutation and returns true. When it is already at the last one (cba), it wraps to the first (sorted) one and returns false. Start from the sorted order to visit all n! permutations; with duplicates, each distinct arrangement appears only once.

  • partial_sort(first, middle, last) puts the smallest middle − first elements (here, with greater, the largest 3) in sorted order at the front. Cost ≈ n log k. Perfect for "top k" queries.

  • nth_element(first, nth, last) places at nth the element that would be there if the range were sorted, with smaller-or-equal elements before it and greater-or-equal after it (in no particular order). It runs in O(n) on average, faster than sorting just to find the median or the k-th smallest.


Algorithms on Sorted Ranges: merge and Set Operations

These take two sorted ranges and produce a sorted output in a single linear pass, like the merge step of merge sort.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

void print(const char* label, const std::vector<int>& v) {
    std::cout << label;
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

int main() {
    // Both inputs MUST be sorted
    std::vector<int> a{1, 3, 5, 7, 9};
    std::vector<int> b{3, 4, 5, 6};

    std::vector<int> m, u, i, d;
    std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(m));
    std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(u));
    std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(i));
    std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(d));

    print("merge:        ", m);
    print("union:        ", u);
    print("intersection: ", i);
    print("a - b:        ", d);

    std::vector<int> sub{3, 7};
    std::cout << std::boolalpha << "a includes {3,7}: "
              << std::includes(a.begin(), a.end(), sub.begin(), sub.end()) << '\n';
}

Output:

merge:        1 3 3 4 5 5 6 7 9 
union:        1 3 4 5 6 7 9 
intersection: 3 5 
a - b:        1 7 9 
a includes {3,7}: true

merge keeps all elements (both 3s and both 5s), while set_union keeps a common element only once. All of these are O(n₁ + n₂). If the inputs are not sorted, the result is wrong (and formally the behaviour is undefined).


C++20 Ranges: Algorithms Without begin() and end()

Writing v.begin(), v.end() every time is noisy and error-prone (it is easy to mix up a.begin() with b.end()). C++20 added constrained algorithms in the namespace std::ranges. You pass the whole container, and many of them accept a projection: a member or function that is applied to each element before comparing.

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

struct Student {
    std::string name;
    int marks;
};

int main() {
    std::vector<int> v{5, 2, 8, 1, 9};

    std::ranges::sort(v);                                  // C++20: no begin/end
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';

    std::cout << std::boolalpha;
    std::cout << "contains 8? " << std::ranges::contains(v, 8) << '\n';   // C++23

    int total = std::ranges::fold_left(v, 0, std::plus<>());           // C++23
    std::cout << "total: " << total << '\n';

    // Projection: compare students by their 'marks' member
    std::vector<Student> cls{{"Aman", 80}, {"Bina", 92}, {"Divya", 75}};
    std::ranges::sort(cls, std::ranges::greater{}, &Student::marks);
    for (const auto& s : cls) std::cout << s.name << ' ';
    std::cout << '\n';

    auto it = std::ranges::find(cls, "Divya", &Student::name);
    if (it != cls.end())
        std::cout << it->name << " has " << it->marks << '\n';

    auto best = std::ranges::max_element(cls, {}, &Student::marks);
    std::cout << "topper: " << best->name << '\n';
}

Output:

1 2 5 8 9 
contains 8? true
total: 25
Bina Aman Divya 
Divya has 75
topper: Bina
  • std::ranges::sort(cls, std::ranges::greater{}, &Student::marks) reads as "sort cls, descending, comparing by marks". No hand-written comparator.

  • In ranges::find(cls, "Divya", &Student::name) the projection lets us search a vector of structs by one field.

  • {} as the comparator means "use the default", which is std::ranges::less.

  • C++23 added std::ranges::contains (a clear yes/no linear search) and std::ranges::fold_left (a range-based replacement for accumulate; its result type is worked out from the operation, which avoids the accumulate type trap in many cases).

  • Ranges algorithms also check their requirements at compile time with concepts. std::ranges::sort on a std::list gives a clear "constraints not satisfied" error instead of pages of template errors.

The classic iterator-pair versions are still everywhere in existing code and textbooks, so learn both.


Cheat Sheet: Common Algorithms and Their Cost

TaskAlgorithmHeaderTimeNeeds sorted input?
Sortsort<algorithm>O(n log n)No
Sort, keep order of tiesstable_sort<algorithm>O(n log n), or O(n log² n) without extra memoryNo
Top k in orderpartial_sort<algorithm>≈ O(n log k)No
k-th smallest / mediannth_element<algorithm>O(n) averageNo
Linear search / countfind, find_if, count, count_if<algorithm>O(n)No
Binary searchbinary_search, lower_bound, upper_bound, equal_range<algorithm>O(log n) comparisonsYes
Min / maxmin_element, max_element, minmax_element<algorithm>O(n)No
Sum / foldaccumulate, reduce (C++17)<numeric>O(n)No
Fill 1, 2, 3, …iota<numeric>O(n)No
Reverse / rotatereverse, rotate<algorithm>O(n)No
Remove valuesremove/remove_if + erase, or std::erase_if (C++20)<algorithm> / container headerO(n)No
Remove adjacent duplicatesunique + erase<algorithm>O(n)Sort first for all duplicates
Next arrangementnext_permutation, prev_permutation<algorithm>O(n) per callStart sorted to get all n!
Merge / set operationsmerge, set_union, set_intersection, set_difference, includes<algorithm>O(n₁ + n₂)Yes

Common Mistakes

  1. Calling remove and forgetting erase. The size does not change; the "removed" values are still there at the end. Use the remove–erase idiom or C++20 std::erase_if. (GCC 15's standard library marks std::remove, remove_if and unique as [[nodiscard]], so g++ warns by default, even without -Wall, if you ignore the returned iterator. Other compilers may stay silent, so do not rely on the warning.)

  2. Binary search on unsorted data. binary_search, lower_bound, merge and the set_* algorithms silently give wrong answers. Sort first, with the same comparator you search with.

  3. Dereferencing the "not found" result. Always check it != v.end() before using *it.

  4. Using <= in a comparator. It breaks strict weak ordering: undefined behaviour, possibly a crash.

  5. Writing into a container with no room. std::copy(a.begin(), a.end(), b.begin()) with an empty b writes past the end. Resize b first or use std::back_inserter(b).

  6. Wrong initial value in accumulate. 0 for doubles truncates; 0 for big sums can overflow. Use 0.0 or 0LL.

  7. Using std::find on a set/map. It is O(n). The member find is O(log n) (or average O(1) for unordered containers).

  8. Expecting unique to remove all duplicates. It only removes adjacent ones.

  9. Using std::sort on a std::list. Compile error: use myList.sort().


Interview / GATE-Style Questions

Q1. What is the time complexity of std::sort, and is it stable?

O(n log n) comparisons in the worst case (guaranteed since C++11; typically introsort). It is not stable: equal elements may change their relative order. Use std::stable_sort when stability matters.

Q2. After v = {1, 2, 3, 2, 5} and std::remove(v.begin(), v.end(), 2); what is v.size()?

Still 5. remove shifts the kept elements 1 3 5 to the front and returns an iterator to position 3. The last two positions hold unspecified values. Only v.erase(returned_iterator, v.end()) shrinks the vector to 3.

Q3. How do you count the occurrences of x in a sorted vector in O(log n)?

std::upper_bound(v.begin(), v.end(), x) - std::lower_bound(v.begin(), v.end(), x), or take the distance between the two iterators returned by std::equal_range.

Q4. In v = {10, 20, 30, 40}, what do lower_bound(25) and upper_bound(40) return?

lower_bound(25) returns an iterator to 30 (index 2), the first element ≥ 25. upper_bound(40) returns v.end() (index 4), because no element is greater than 40.

Q5. Starting from s = "aab", how many times does the body of do { ... } while (next_permutation(s.begin(), s.end())); run?

3: aab, aba, baa. next_permutation generates distinct arrangements only, and the number of distinct permutations of a multiset is 3! / 2! = 3.

Q6. Why can't std::sort be used on std::list?

std::sort requires random-access iterators (it needs it + k and it2 - it1 in O(1)). A list only has bidirectional iterators. std::list provides the member function sort() (a merge sort that relinks nodes, O(n log n), stable).

Q7. What does std::accumulate(v.begin(), v.end(), 0) return for v = {0.5, 0.5, 0.5, 0.5}?

0. The accumulator is an int: 0 + 0.5 = 0.5 is converted to 0 at each step, so the total never grows. With 0.0 as the initial value the answer is 2.

Q8. Which is faster for finding the median of n numbers: sort or nth_element?

nth_element: O(n) on average versus O(n log n) for sort. It only places the middle element correctly and partitions the rest around it, which is all we need.


Summary

  • STL algorithms operate on iterator ranges [first, last), so one algorithm works with every suitable container. They return last for "not found" and can never change a container's size.

  • sort is O(n log n) and unstable; stable_sort keeps ties in order. Comparators must be strict (use <, never <=).

  • find/count are O(n) on any range; binary_search, lower_bound (first ≥ x), upper_bound (first > x) and equal_range are O(log n) but need sorted input.

  • accumulate, reduce and iota live in <numeric>; the initial value of accumulate decides the result type.

  • remove/unique only rearrange; follow them with erase, or use C++20 std::erase/std::erase_if.

  • partial_sort (top k), nth_element (k-th element, O(n) average) and next_permutation solve common interview problems in one line.

  • C++20 std::ranges algorithms take whole containers and projections; C++23 adds ranges::contains and ranges::fold_left.

Algorithms are only as powerful as the iterators we feed them. In the next chapter, Iterators, we look closely at iterator categories, why some algorithms need random access, inserter iterators like back_inserter, and when iterators become invalid.