Iterators: Why Every Algorithm Takes Two Arguments
Every standard algorithm is written as algorithm(begin, end, ...) rather than algorithm(container, ...), and the reason is worth understanding because it explains a lot of the library's shape.
An iterator is an object that behaves like a pointer into a container: *it gives you the element, ++it moves to the next one, and two iterators can be compared. Because every container provides iterators, an algorithm written against iterators works with all of them — the same std::find serves a vector, a list, a set and a plain array. Without this, the library would need one find per container, and none of them would work with a container you wrote yourself.
It also means an algorithm can operate on part of a container. std::sort(v.begin(), v.begin() + 10, ...) sorts the first ten elements. Passing the container would have made that impossible.
The convention to internalise is the half-open range: begin() points at the first element and end() points one past the last. end() is not an element and must never be dereferenced. This looks odd at first and turns out to be exactly right — the number of elements is simply end - begin, an empty range is begin == end, and no loop needs a special case for emptiness.
The same convention explains how searches report failure. std::find returns an iterator to what it found, and returns end() when there is nothing to return — a value that is guaranteed to exist and guaranteed not to be an element. So the check after every search is if (it != v.end()), and dereferencing without checking is undefined behaviour.
#include <algorithm>
#include <iostream>
#include <list>
#include <set>
#include <vector>
int main() {
std::vector<int> v = {5, 3, 1, 4, 2};
std::list<int> l = {5, 3, 1, 4, 2};
std::set<int> s = {5, 3, 1, 4, 2};
// One algorithm, three completely different containers
std::cout << (std::find(v.begin(), v.end(), 4) != v.end()) << '\n'; // 1
std::cout << (std::find(l.begin(), l.end(), 4) != l.end()) << '\n'; // 1
std::cout << (std::find(s.begin(), s.end(), 9) != s.end()) << '\n'; // 0
// ALWAYS check before dereferencing
auto it = std::find(v.begin(), v.end(), 3);
if (it != v.end()) std::cout << "found " << *it << '\n';
// Half-open range: operate on part of a container
std::sort(v.begin(), v.begin() + 3);
for (int x : v) std::cout << x << ' '; // 1 3 5 4 2
std::cout << '\n';
// The size of a range is simply end - begin
std::cout << (v.end() - v.begin()) << '\n'; // 5
}- C++20 adds the ranges library, which lets you write
std::ranges::sort(v)andstd::ranges::find(v, 4)with the container itself. It is a genuine improvement in readability. The iterator forms are what you will meet in existing code and in interviews, so learn those first.
Sorting, and the Comparator Rule
std::sort sorts a range in O(n log n) and is one of the most heavily optimised functions you will ever call. By default it sorts ascending using operator<. Passing a third argument — a comparator — lets you define any ordering you like: descending, by a struct's field, by two fields with a tie-break.
The comparator answers exactly one question: "must a come before b?" It returns true if so. std::greater<>() from <functional> gives you descending order in one token, and a lambda gives you anything else.
Here is a rule that is easy to get wrong and that fails spectacularly. Your comparator must be a strict weak ordering, and the part that matters in practice is that compare(a, a) must be false. Writing return a <= b; instead of return a < b; looks harmless and is undefined behaviour: std::sort uses the comparison to decide when to stop scanning, and a comparator that says an element precedes itself lets it run off the end of the range. The symptom is a crash or memory corruption inside std::sort on some inputs and not others. Never use <= or >= in a sort comparator.
std::sort is not stable — equal elements may be reordered. When that matters, for instance sorting by marks after having sorted by name and wanting the name order preserved within each mark, use std::stable_sort. It is slightly slower and guarantees equal elements keep their relative order.
Two specialised sorts are worth knowing for interviews. std::partial_sort arranges only the first k elements correctly, which is the efficient answer to "give me the top 10 of a lakh records". std::nth_element places one element where it would be if sorted and partitions everything around it, which finds a median in linear time on average without sorting anything.
#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
struct Student { std::string name; int marks; };
int main() {
std::vector<int> nums = {5, 3, 1, 4, 2};
std::sort(nums.begin(), nums.end()); // 1 2 3 4 5
std::sort(nums.begin(), nums.end(), std::greater<>()); // 5 4 3 2 1
// WRONG: <= is not a strict weak ordering. Undefined behaviour.
// std::sort(nums.begin(), nums.end(), [](int a, int b){ return a <= b; });
std::vector<Student> cls = {
{"Ananya", 91}, {"Rahul", 65}, {"Meera", 91}, {"Kabir", 78}
};
// By marks descending, then by name for ties
std::sort(cls.begin(), cls.end(), [](const Student& a, const Student& b) {
if (a.marks != b.marks) return a.marks > b.marks;
return a.name < b.name;
});
for (const auto& s : cls) std::cout << s.name << ' ';
std::cout << '\n'; // Ananya Meera Kabir Rahul
// Only the top 2 need to be in order
std::vector<int> big = {45, 12, 99, 3, 78, 61};
std::partial_sort(big.begin(), big.begin() + 2, big.end(), std::greater<>());
std::cout << big[0] << ' ' << big[1] << '\n'; // 99 78
}std::sortneeds random-access iterators, so it does not work onstd::list. That container provides its own member function,l.sort(), which relinks the nodes instead of moving elements.std::mapandstd::setare already sorted and cannot be re-sorted at all.
Searching, Counting and Accumulating
std::find walks the range looking for a value and is O(n). std::find_if does the same with a predicate, so you can search for the first element satisfying any condition. Both return end() on failure.
When the range is already sorted, you can do far better. std::binary_search answers yes or no in O(log n). std::lower_bound returns an iterator to the first element not less than your value, and std::upper_bound to the first element strictly greater — between them they give you the range of all equal elements, and lower_bound is also the correct insertion point that keeps the range sorted. All three require a sorted range; run them on unsorted data and they return confidently wrong answers with no error.
std::count and std::count_if tally matches. std::all_of, std::any_of and std::none_of answer the corresponding yes/no questions and stop as soon as they know, so they are both clearer and faster than counting and comparing to zero.
std::accumulate, from <numeric>, sums a range starting from an initial value — and that initial value hides the single nastiest gotcha in the algorithms library. The type of the initial value determines the type of the accumulation. Write std::accumulate(v.begin(), v.end(), 0) on a vector of double and every partial sum is truncated to an int; you get a whole number and no warning. Pass 0.0 instead. The same trap applies to large integers: summing a lakh of values that each fit in an int can overflow, so pass 0LL to accumulate in 64 bits.
std::minmax_element returns a pair of iterators to the smallest and largest elements, which pairs nicely with structured bindings. On an empty range both iterators equal end(), so dereferencing them without checking is undefined behaviour — check empty() first.
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<int> marks = {72, 65, 91, 48, 88};
// Linear search with a condition
auto it = std::find_if(marks.begin(), marks.end(),
[](int m) { return m > 85; });
if (it != marks.end()) std::cout << "first above 85: " << *it << '\n'; // 91
// Binary search needs a SORTED range
std::vector<int> sorted = marks;
std::sort(sorted.begin(), sorted.end()); // 48 65 72 88 91
std::cout << std::binary_search(sorted.begin(), sorted.end(), 72) << '\n'; // 1
auto lo = std::lower_bound(sorted.begin(), sorted.end(), 70);
std::cout << *lo << '\n'; // 72 — first >= 70
// Counting and quantifiers
std::cout << std::count_if(marks.begin(), marks.end(),
[](int m) { return m >= 60; }) << '\n'; // 4
std::cout << std::all_of(marks.begin(), marks.end(),
[](int m) { return m >= 33; }) << '\n'; // 1
// accumulate: the initial value decides the type
std::vector<double> prices = {10.5, 20.25, 5.75};
std::cout << std::accumulate(prices.begin(), prices.end(), 0) << '\n'; // 35 WRONG
std::cout << std::accumulate(prices.begin(), prices.end(), 0.0) << '\n'; // 36.5
std::vector<int> huge(100000, 50000);
std::cout << std::accumulate(huge.begin(), huge.end(), 0LL) << '\n'; // 5000000000
if (!marks.empty()) {
auto [lowest, highest] = std::minmax_element(marks.begin(), marks.end());
std::cout << *lowest << ' ' << *highest << '\n'; // 48 91
}
}std::lower_boundon astd::maporstd::setshould be called as the container's own member function —s.lower_bound(x)— not the free algorithm. The member version uses the tree structure and is O(log n); the free version on a node-based container degrades to a linear walk.
Transforming, and Why remove Does Not Remove
std::transform applies a function to every element and writes the results somewhere. That destination is an iterator, and it must already point at somewhere with room. Writing into an empty vector is undefined behaviour — the classic mistake. Either size the destination first with resize or a sized constructor, or use std::back_inserter from <iterator>, which turns each write into a push_back. Writing back into the source range is also fine, which is how you modify a container in place.
std::for_each runs a function on every element and returns nothing useful. It has largely been replaced by the range-based for loop, which is shorter and clearer for the same job.
Now the behaviour that surprises everyone at least once. std::remove and std::remove_if do not remove anything. After calling them, the container's size() is exactly what it was before.
The explanation is the iterator design. An algorithm only receives two iterators; it has no access to the container and therefore no way to shrink it. What remove_if actually does is shuffle the elements you want to keep to the front of the range, in order, and return an iterator marking where the kept elements end. Everything from that iterator to the original end() is leftover values you should ignore. To genuinely shorten the container, you pass that returned iterator to the container's own erase: v.erase(std::remove_if(...), v.end()). That pairing is the erase-remove idiom, and it is worth memorising as one unit because the remove half is nearly useless alone.
std::unique works the same way and adds a second requirement: it removes only consecutive duplicates. On unsorted data it will happily leave duplicates behind, so the standard recipe is sort first, then unique, then erase. In C++20 all of this is wrapped up: std::erase_if(v, pred) does the whole job in one call.
#include <algorithm>
#include <cctype>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
int main() {
std::vector<int> marks = {72, 28, 91, 15, 65};
// Destination must have room — size it, or use back_inserter
std::vector<int> scaled(marks.size());
std::transform(marks.begin(), marks.end(), scaled.begin(),
[](int m) { return m + 5; });
std::vector<int> alsoScaled;
std::transform(marks.begin(), marks.end(), std::back_inserter(alsoScaled),
[](int m) { return m + 5; });
// In place: source and destination are the same range
std::string code = "pass2026";
std::transform(code.begin(), code.end(), code.begin(),
[](unsigned char c) { return std::toupper(c); });
std::cout << code << '\n'; // PASS2026
// remove_if alone changes NOTHING about size
std::vector<int> a = marks;
std::remove_if(a.begin(), a.end(), [](int m) { return m < 33; });
std::cout << a.size() << '\n'; // 5 — still five!
// The erase-remove idiom actually shortens the container
std::vector<int> b = marks;
b.erase(std::remove_if(b.begin(), b.end(), [](int m) { return m < 33; }),
b.end());
std::cout << b.size() << '\n'; // 3
// unique only collapses ADJACENT duplicates: sort first
std::vector<int> dup = {3, 1, 3, 2, 1};
std::sort(dup.begin(), dup.end());
dup.erase(std::unique(dup.begin(), dup.end()), dup.end());
for (int x : dup) std::cout << x << ' '; // 1 2 3
std::cout << '\n';
}- If a call to
remove_if,uniqueortransformcompiles but appears to do nothing, the missingeraseis almost always the reason. A useful habit: never writestd::remove_ifwithout immediately typing the surroundingerase(...)on the same line.