C++ STL Algorithms
The C++ Standard Template Library (STL) ships a large collection of algorithms – reusable, generic functions that operate on ranges of elements accessed through iterators. Instead of hand-writing a loop every time you need to sort, search, count, copy, or transform data, you call a well-tested function from <algorithm> (or <numeric> for numeric operations) that works on any container exposing iterators: vectors, arrays, lists, sets, and more. Mastering STL algorithms is one of the biggest productivity jumps in C++, because it swaps error-prone manual loops for expressive, composable, and highly optimized building blocks.
Overview: How STL Algorithms Work
Every STL algorithm is a template function that operates on a range, expressed as a pair of iterators: first and last, where last points one-past-the-end of the range. The algorithm never touches the container directly – it only sees iterators – which is why the very same sort call works on a vector<int>, an array<double, 10>, or a plain C-style array via pointers. This separation is the core design idea of the STL: containers store data, iterators traverse it, and algorithms operate on it, and the three pieces are independent of one another.
Internally, most algorithms are simple loops written once, thoroughly tested, and sometimes specialized for the category of iterator they receive (random-access iterators, like a vector’s, allow different optimizations than forward-only iterators, like a list’s). For example, sort typically implements introsort – a hybrid of quicksort, heapsort, and insertion sort – guaranteeing O(n log n) worst-case performance, something you would rarely bother implementing correctly by hand. Many algorithms accept an optional predicate or comparator: a function pointer, function object, or (most commonly today) a lambda expression that customizes behavior without changing the algorithm’s own code. This is compile-time polymorphism – the compiler generates a specialized version of the algorithm for each type and callable you pass in, so there is zero runtime overhead compared to writing the loop yourself.
Algorithms are usually grouped by intent: non-modifying queries (find, count, all_of, any_of), modifying operations (transform, replace, remove, reverse), sorting and related operations (sort, unique, binary_search), and numeric operations (accumulate, inner_product, found in <numeric> rather than <algorithm>). Knowing these categories helps you reach for the right tool instead of reinventing a raw for-loop every time.
Syntax
The general shape of every algorithm call is the same: a range (two iterators), followed by whatever extra arguments that particular algorithm needs.
ReturnType algorithm_name(InputIterator first, InputIterator last, ...extra_args);
// examples of the pattern
sort(v.begin(), v.end());
sort(v.begin(), v.end(), comparator);
find(v.begin(), v.end(), value);
transform(v.begin(), v.end(), dest.begin(), unary_function);
accumulate(v.begin(), v.end(), initial_value);- first, last – the iterator range to operate on;
lastis exclusive (one past the final element). - extra_args – a value to search for, an initial value to accumulate onto, a destination iterator to write results to, or a callable (comparator/predicate) to customize the logic.
- Return value – varies by algorithm: an iterator (
find,max_element), a count (count), a bool (any_of), or an accumulated value (accumulate).
| Algorithm | Header | Purpose | Typical Complexity |
|---|---|---|---|
| sort | <algorithm> | Sort a range in place | O(n log n) |
| find | <algorithm> | Locate the first element equal to a value | O(n) |
| count | <algorithm> | Count elements equal to a value | O(n) |
| accumulate | <numeric> | Fold a range into a single value (sum by default) | O(n) |
| transform | <algorithm> | Apply a function to each element, writing results elsewhere | O(n) |
| unique | <algorithm> | Remove consecutive duplicate elements | O(n) |
| remove | <algorithm> | Move unwanted elements to the end (does not resize) | O(n) |
Examples
Example 1: Sorting a Vector Ascending and Descending
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> nums = {5, 2, 9, 1, 5, 6};
sort(nums.begin(), nums.end());
cout << "Sorted: ";
for (int n : nums) cout << n << " ";
cout << endl;
sort(nums.begin(), nums.end(), greater<int>());
cout << "Descending: ";
for (int n : nums) cout << n << " ";
cout << endl;
return 0;
}Output:
Sorted: 1 2 5 5 6 9
Descending: 9 6 5 5 2 1 The first sort call uses the default comparator <, giving ascending order. The second call passes greater<int>(), a function object from <functional>-compatible headers that reverses the comparison, giving descending order without writing a new loop. Any callable with the signature bool(const T&, const T&) works here, including a lambda.
Example 2: Searching, Counting, and Summing
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main() {
vector<int> scores = {88, 92, 76, 92, 65, 100};
auto it = find(scores.begin(), scores.end(), 76);
if (it != scores.end())
cout << "Found 76 at index " << (it - scores.begin()) << endl;
int countOf92 = count(scores.begin(), scores.end(), 92);
cout << "Number of 92s: " << countOf92 << endl;
int total = accumulate(scores.begin(), scores.end(), 0);
cout << "Total: " << total << endl;
auto maxIt = max_element(scores.begin(), scores.end());
cout << "Highest score: " << *maxIt << endl;
return 0;
}Output:
Found 76 at index 2
Number of 92s: 2
Total: 513
Highest score: 100find returns an iterator, which you can subtract from begin() to get a numeric index. count loops the whole range tallying matches. accumulate (from <numeric>, easy to forget since it is not in <algorithm>) folds the range into one value, starting from the initial value 0 and adding each element. max_element returns an iterator to the largest element, so it must be dereferenced with * to get the value itself.
Example 3: Sorting Structs with a Lambda and Transforming Data
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;
struct Student {
string name;
double gpa;
};
int main() {
vector<Student> students = {
{"Alice", 3.8},
{"Bob", 3.2},
{"Carol", 3.9},
{"Dave", 3.5}
};
sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
return a.gpa > b.gpa;
});
cout << "Ranked by GPA:" << endl;
for (const auto& s : students) {
cout << s.name << ": " << s.gpa << endl;
}
bool anyHonor = any_of(students.begin(), students.end(), [](const Student& s) {
return s.gpa >= 3.9;
});
cout << "Has honor student: " << (anyHonor ? "yes" : "no") << endl;
vector<string> names;
transform(students.begin(), students.end(), back_inserter(names), [](const Student& s) {
return s.name;
});
cout << "Names in rank order: ";
for (const auto& n : names) cout << n << " ";
cout << endl;
return 0;
}Output:
Ranked by GPA:
Carol: 3.9
Alice: 3.8
Dave: 3.5
Bob: 3.2
Has honor student: yes
Names in rank order: Carol Alice Dave Bob This example combines four algorithms. sort uses a lambda comparator to rank students by GPA, highest first. any_of checks whether any element satisfies a predicate without a manual loop or early-return logic. transform applies a lambda to every Student and writes the resulting string into a separate vector; back_inserter (from <iterator>) is a special output iterator that calls push_back on the destination container instead of requiring it to already have the right size.
Under the Hood: Iterators, Categories, and Complexity
An algorithm’s behavior and performance depend on the iterator category it receives. Random-access iterators (vector, array, deque, raw pointers) support jumping by an arbitrary offset in O(1), which is why sort can even be called on them – efficient comparison sorts need random access to do things like pick a pivot or binary-partition. Bidirectional iterators (list, set, map) can only move one step at a time in either direction, which is why you cannot call sort directly on a std::list – it has its own member function list::sort instead, implemented as a merge sort that only needs sequential access. Forward iterators only move forward one step at a time; input iterators (like those from std::istream_iterator) can only be read once, in order.
Most linear-scan algorithms (find, count, accumulate, transform, any_of) are O(n) because they must look at every element exactly once. sort is O(n log n) because comparison-based sorting cannot do better in the general case. binary_search is O(log n), but only correct if the range is already sorted – the algorithm trusts you, it does not check, so calling it on unsorted data returns garbage instead of an error.
Common Mistakes
Mistake 1: Forgetting the Erase-Remove Idiom
remove does not shrink a container – it cannot, because it only receives iterators, not the container itself, so it has no way to call resize or erase. It shifts the elements you want to keep to the front of the range and returns an iterator marking the new logical end; everything from there to the old end() is leftover, unspecified data.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> nums = {1, 2, 3, 2, 4, 2, 5};
remove(nums.begin(), nums.end(), 2);
cout << "Size after remove: " << nums.size() << endl;
cout << "Contents: ";
for (int n : nums) cout << n << " ";
cout << endl;
return 0;
}Output:
Size after remove: 7
Contents: 1 3 4 5 4 2 5 The size is still 7, and the tail of the vector contains leftover junk values instead of being gone. The fix is the classic erase-remove idiom: pass the iterator that remove returns into the container’s own erase member function, which actually shrinks the container.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> nums = {1, 2, 3, 2, 4, 2, 5};
nums.erase(remove(nums.begin(), nums.end(), 2), nums.end());
cout << "Size after erase-remove: " << nums.size() << endl;
cout << "Contents: ";
for (int n : nums) cout << n << " ";
cout << endl;
return 0;
}Output:
Size after erase-remove: 4
Contents: 1 3 4 5 Mistake 2: Calling unique on Unsorted Data
unique only removes consecutive duplicates, not all duplicates. If equal values are not adjacent, it leaves them untouched, which surprises people who expect it to behave like a set.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> nums = {1, 3, 2, 3, 1, 4, 4};
auto newEnd = unique(nums.begin(), nums.end());
nums.erase(newEnd, nums.end());
cout << "Contents: ";
for (int n : nums) cout << n << " ";
cout << endl;
return 0;
}Output:
Contents: 1 3 2 3 1 4 Only the trailing 4 4 pair was adjacent, so it is the only duplicate removed; the two separate 3s and the two separate 1s remain. The fix is to sort the range first so that every duplicate becomes adjacent, then run unique followed by erase.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> nums = {1, 3, 2, 3, 1, 4, 4};
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
cout << "Contents: ";
for (int n : nums) cout << n << " ";
cout << endl;
return 0;
}Output:
Contents: 1 2 3 4 Best Practices
- Always pair
remove/remove_ifwith a container’serase– remember it as one idiom, not two separate steps. - Sort before calling algorithms that require sorted input, such as
uniqueorbinary_search; they do not verify the precondition for you. - Prefer a lambda over a free function or functor for one-off comparators and predicates – it keeps the logic next to the call site and avoids extra boilerplate.
- Use
const auto&in range-based for loops over algorithm results to avoid unnecessary copies, especially with containers of structs or strings. - Reach for a named algorithm (
count_if,any_of,transform) before writing a manual loop – it documents intent and reduces off-by-one bugs. - Remember
<numeric>foraccumulate,inner_product, and similar numeric folds; they are not in<algorithm>. - When writing to a destination that has no existing size, use an inserter like
back_inserterinstead of assuming the destination already has room.
Practice Exercises
- Given
vector<int> nums = {4, 8, 15, 16, 23, 42};, usecount_ifwith a lambda to count how many elements are even. Expected output:4. - Given
vector<string> words = {"pear", "fig", "apple", "kiwi"};, usesortwith a custom comparator to sort the words by length (shortest first), then print them. - Given
vector<int> nums = {1, 1, 2, 2, 2, 3, 4, 4};, useuniquetogether with the erase-remove idiom to remove duplicates in place, then print the resulting vector. Expected output:1 2 3 4.
Summary
- STL algorithms are generic template functions that operate on iterator ranges, working across any compatible container.
sort,find,count, andtransformlive in<algorithm>;accumulateand similar numeric folds live in<numeric>.- Comparators and predicates are usually passed as lambdas, letting one algorithm implementation serve many use cases with no runtime overhead.
- The iterator category a container provides (random-access, bidirectional, forward) determines which algorithms it can use directly.
removeanduniquedo not resize a container – always pair them witherase, and sort beforeuniqueif you want all duplicates gone.- Preferring named algorithms over hand-written loops makes code shorter, clearer about intent, and less prone to off-by-one errors.
