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::findworks on avector, alist, adeque, a plain array, even astring. 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 == lastthere 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 returnsa > 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 5were sorted;3 1were 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::sortis not stable;std::stable_sortis.
#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_sortguarantees that Aman, Chirag and Farhan (all 80) stay in their input order, which happened to be alphabetical.Plain
sortwith 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
findreturns an iterator to the first match, orlast(heremarks.end()) if there is none. Always compare withend()before dereferencing; dereferencingend()is undefined behaviour.For a
vector, subtractingbegin()from an iterator gives the index.The
_ifversions 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:
| Algorithm | Returns | Meaning |
|---|---|---|
binary_search(f, l, x) | bool | Is x present? |
lower_bound(f, l, x) | iterator | First element ≥ x |
upper_bound(f, l, x) | iterator | First 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_searchonly says yes/no.lower_boundtells you where, which is what you usually need.upper_bound(x) − lower_bound(x)counts the copies ofxin O(log n).lower_bound(x)is also the position wherexcan 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_elementreturn an iterator (so you also get the position). With duplicates, both return the first one. Careful:minmax_elementreturns 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 computesinit + a0 + a1 + …. With a fourth argument it can use any operation, such asstd::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)makesmiddlethe new first element. Herevwas6 5 4 3 2 1andmiddlepointed to4(index 2), so4 3 2 1moved to the front and6 5wrapped round to the back. It is a left rotation by 2 in O(n).transform(first, last, out, f)appliesfto each element and writes the result toout. The destination may be the same range (in-place, as with the string).We pass
toupperanunsigned char, because callingstd::toupperwith a negativecharvalue (other thanEOF) 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)andstd::erase_if(container, pred), which do both steps and return how many elements were removed. Prefer them when your compiler supports C++20.std::uniqueworks 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 functionsremove,remove_ifandunique, 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_ofandnone_ofreturntrueandany_ofreturnsfalse(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 callspassed.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 variablecutoffinto itself so it can use it. A plain function could not seecutoff.
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_permutationrearranges the range into the next lexicographically greater permutation and returnstrue. When it is already at the last one (cba), it wraps to the first (sorted) one and returnsfalse. 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 smallestmiddle − firstelements (here, withgreater, the largest 3) in sorted order at the front. Cost ≈ n log k. Perfect for "top k" queries.nth_element(first, nth, last)places atnththe 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 "sortcls, descending, comparing bymarks". 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 isstd::ranges::less.C++23 added
std::ranges::contains(a clear yes/no linear search) andstd::ranges::fold_left(a range-based replacement foraccumulate; its result type is worked out from the operation, which avoids theaccumulatetype trap in many cases).Ranges algorithms also check their requirements at compile time with concepts.
std::ranges::sorton astd::listgives 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
| Task | Algorithm | Header | Time | Needs sorted input? |
|---|---|---|---|---|
| Sort | sort | <algorithm> | O(n log n) | No |
| Sort, keep order of ties | stable_sort | <algorithm> | O(n log n), or O(n log² n) without extra memory | No |
| Top k in order | partial_sort | <algorithm> | ≈ O(n log k) | No |
| k-th smallest / median | nth_element | <algorithm> | O(n) average | No |
| Linear search / count | find, find_if, count, count_if | <algorithm> | O(n) | No |
| Binary search | binary_search, lower_bound, upper_bound, equal_range | <algorithm> | O(log n) comparisons | Yes |
| Min / max | min_element, max_element, minmax_element | <algorithm> | O(n) | No |
| Sum / fold | accumulate, reduce (C++17) | <numeric> | O(n) | No |
| Fill 1, 2, 3, … | iota | <numeric> | O(n) | No |
| Reverse / rotate | reverse, rotate | <algorithm> | O(n) | No |
| Remove values | remove/remove_if + erase, or std::erase_if (C++20) | <algorithm> / container header | O(n) | No |
| Remove adjacent duplicates | unique + erase | <algorithm> | O(n) | Sort first for all duplicates |
| Next arrangement | next_permutation, prev_permutation | <algorithm> | O(n) per call | Start sorted to get all n! |
| Merge / set operations | merge, set_union, set_intersection, set_difference, includes | <algorithm> | O(n₁ + n₂) | Yes |
Common Mistakes
Calling
removeand forgettingerase. The size does not change; the "removed" values are still there at the end. Use the remove–erase idiom or C++20std::erase_if. (GCC 15's standard library marksstd::remove,remove_ifanduniqueas[[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.)Binary search on unsorted data.
binary_search,lower_bound,mergeand theset_*algorithms silently give wrong answers. Sort first, with the same comparator you search with.Dereferencing the "not found" result. Always check
it != v.end()before using*it.Using
<=in a comparator. It breaks strict weak ordering: undefined behaviour, possibly a crash.Writing into a container with no room.
std::copy(a.begin(), a.end(), b.begin())with an emptybwrites past the end. Resizebfirst or usestd::back_inserter(b).Wrong initial value in
accumulate.0for doubles truncates;0for big sums can overflow. Use0.0or0LL.Using
std::findon aset/map. It is O(n). The memberfindis O(log n) (or average O(1) for unordered containers).Expecting
uniqueto remove all duplicates. It only removes adjacent ones.Using
std::sorton astd::list. Compile error: usemyList.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 returnlastfor "not found" and can never change a container's size.sortis O(n log n) and unstable;stable_sortkeeps ties in order. Comparators must be strict (use<, never<=).find/countare O(n) on any range;binary_search,lower_bound(first ≥ x),upper_bound(first > x) andequal_rangeare O(log n) but need sorted input.accumulate,reduceandiotalive in<numeric>; the initial value ofaccumulatedecides the result type.remove/uniqueonly rearrange; follow them witherase, or use C++20std::erase/std::erase_if.partial_sort(top k),nth_element(k-th element, O(n) average) andnext_permutationsolve common interview problems in one line.C++20
std::rangesalgorithms take whole containers and projections; C++23 addsranges::containsandranges::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.