These are the notes for C++ episode 27. In episode 26 you invented iterators and wrote one show function that works on any range [first, last). The standard library already has over a hundred functions built exactly that way, in the <algorithm> and <numeric> headers. They're called the STL algorithms. Every example below was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13.3, the same command as the SyntaxPilot compiler) and run; outputs and error messages are copied from those runs. Timings change from run to run and machine to machine; compare the ratios.
The problem: 80000 results, sorted by hand
A district's board exam results arrive: 80,000 students. The office wants a rank list, the topper, the number of fails, whether anyone scored 100, and the total. The obvious way is to write everything by hand, starting with the sort you may already know, bubble sort: compare each pair of neighbours, swap them if they're in the wrong order, and repeat.
#include <iostream>
#include <vector>
#include <chrono>
using namespace std;
using namespace std::chrono;
int main() {
vector<int> marks; // a whole district's results
for (int i = 0; i < 80000; i++) marks.push_back(i * 7919 % 100);
auto start = steady_clock::now();
for (int i = 0; i < marks.size(); i++) // bubble sort,
for (int j = 0; j + 1 < marks.size() - i; j++) // by hand
if (marks[j] > marks[j + 1]) swap(marks[j], marks[j + 1]);
auto end = steady_clock::now();
cout << "by hand: " << duration_cast<milliseconds>(end - start).count() << " ms" << endl;
return 0;
}
Output:
by hand: 2146 ms
Seconds for one sort (about two here; over three on a busier machine). Two nested loops over 80,000 items means about 80,000 × 80,000 / 2 ≈ 3.2 billion comparisons: that's O(n²) ("order n squared": the work grows with the square of the number of items).
And it's not only slow. Every report would be another hand-written loop, and every loop is another chance for an off-by-one bug, like getting j + 1 < marks.size() - i wrong.
Step 1: the algorithm library (the mixer-grinder)
Real-life example: you could grind masala on a stone every day, by hand. Or you press one button on a mixer-grinder: built by experts, tested millions of times, fast, and it works with any jar that fits.
| In a kitchen | In C++ |
|---|---|
| grinding on a stone, by hand | hand-written loops: slow, easy to get wrong |
| a mixer-grinder | #include <algorithm>: sort, find, count, ... |
| any jar that fits | any range of iterators: (first, last) |
An algorithm here means a ready-made, tested function that works on a range of iterators. Because it only sees iterators, it doesn't care whether the data lives in a vector, a deque, an array or (for many of them) a list or set.
Step 2: sort
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
using namespace std;
using namespace std::chrono;
int main() {
vector<int> marks;
for (int i = 0; i < 80000; i++) marks.push_back(i * 7919 % 100);
auto start = steady_clock::now();
sort(marks.begin(), marks.end()); // one line
auto end = steady_clock::now();
cout << "sort: " << duration_cast<milliseconds>(end - start).count() << " ms" << endl;
cout << "lowest " << marks.front() << ", highest " << marks.back() << endl;
return 0;
}
Output:
sort: 1 ms
lowest 0, highest 99
One line, and a millisecond or two instead of seconds. std::sort does about n log n comparisons (for 80,000 items, about 1.3 million instead of billions). Inside, GCC uses introsort: quicksort that switches to heapsort if it goes badly, and insertion sort for small pieces.
Biggest first, and sorting part of a range
A third argument tells sort how to compare. greater<int>() (from <functional>) means "bigger comes first". And since sort takes a range, you can sort just part of a container:
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
vector<int> marks = {72, 95, 58, 88, 35};
sort(marks.begin(), marks.end());
for (int m : marks) cout << m << " ";
cout << endl;
sort(marks.begin(), marks.end(), greater<int>()); // biggest first
for (int m : marks) cout << m << " ";
cout << endl;
sort(marks.begin(), marks.begin() + 3); // only the first three
for (int m : marks) cout << m << " ";
cout << endl;
return 0;
}
Output:
35 58 72 88 95
95 88 72 58 35
72 88 95 58 35
The last line: only the first three items (95, 88, 72) were sorted into 72, 88, 95; 58 and 35 were left untouched.
Step 3: asking questions about a range
| Algorithm | Returns | Example |
|---|---|---|
find(first, last, x) |
an iterator to the first x, or last if it's missing |
find(v.begin(), v.end(), 100) |
count(first, last, x) |
how many items equal x |
count(v.begin(), v.end(), 100) |
count_if(first, last, rule) |
how many items make rule return true |
count_if(v.begin(), v.end(), isFail) |
max_element(first, last) |
an iterator to the biggest item | *max_element(...) is the value |
min_element(first, last) |
an iterator to the smallest item | it - v.begin() is its position |
A rule function (the C++ name is a predicate) takes one item and returns true or false. You pass it by name, without brackets. (In episode 30 you'll write these rules inline as lambdas.)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool isFail(int m) {
return m < 40;
}
int main() {
vector<int> marks = {72, 100, 35, 88, 100, 21};
auto it = find(marks.begin(), marks.end(), 100);
if (it != marks.end())
cout << "100 found at position " << it - marks.begin() << endl;
if (find(marks.begin(), marks.end(), 99) == marks.end())
cout << "nobody scored 99" << endl;
cout << "centuries: " << count(marks.begin(), marks.end(), 100) << endl;
cout << "fails: " << count_if(marks.begin(), marks.end(), isFail) << endl;
return 0;
}
Output:
100 found at position 1
nobody scored 99
centuries: 2
fails: 2
find returns an iterator, so it - marks.begin() is the position (index) of the first 100. When the value is missing, find returns last (marks.end() here); that's how you know it wasn't found.
max_element gives you the position too
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main() {
vector<string> names = {"Asha", "Ravi", "Meena", "Kiran"};
vector<int> marks = {72, 95, 58, 88};
auto best = max_element(marks.begin(), marks.end());
auto worst = min_element(marks.begin(), marks.end());
cout << "topper: " << names[best - marks.begin()] << " " << *best << endl;
cout << "needs help: " << names[worst - marks.begin()] << " " << *worst << endl;
return 0;
}
Output:
topper: Ravi 95
needs help: Meena 58
Because max_element returns an iterator, you get who scored it, not just how much: the same position in the names vector.
Step 4: accumulate and the 0 vs 0.0 trap
accumulate(first, last, start) from <numeric> adds every item to start and returns the total.
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int main() {
vector<int> marks = {72, 95, 58, 88};
cout << "total marks: " << accumulate(marks.begin(), marks.end(), 0) << endl;
vector<double> fees = {499.5, 250.25, 99.75}; // exam fees
cout << "total fees: " << accumulate(fees.begin(), fees.end(), 0) << endl;
return 0;
}
Output:
total marks: 313
total fees: 848
Total marks: 313, correct. Total fees: 848, but 499.50 + 250.25 + 99.75 is 849.50. No error, no warning, just a wrong answer.
Why: the start value decides the type of the running total. 0 is an int, so the total is an int, and after each addition the fraction (the paise) is chopped off: 0 + 499.5 → 499, + 250.25 → 749, + 99.75 → 848. Start with 0.0, a double:
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int main() {
vector<double> fees = {499.5, 250.25, 99.75};
cout << "total fees: " << accumulate(fees.begin(), fees.end(), 0.0) << endl;
return 0;
}
Output:
total fees: 849.5
Rule: for decimals start at 0.0; for very big integer totals, start at 0LL (a long long) so the sum can't overflow an int.
Step 5: binary_search needs sorted data, and reverse
Real-life example: you find a word in a dictionary by opening it in the middle. Too far? Keep only the left half. Repeat. That's binary search: about 17 steps for 100,000 words (O(log n)). But it only works because the dictionary is sorted. With shuffled pages, halving tells you nothing.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> roll = {42, 7, 19, 3, 88, 56}; // not sorted
cout << "is 7 here? " << binary_search(roll.begin(), roll.end(), 7) << endl;
sort(roll.begin(), roll.end());
cout << "after sort: " << binary_search(roll.begin(), roll.end(), 7) << endl;
reverse(roll.begin(), roll.end());
for (int r : roll) cout << r << " ";
cout << endl;
return 0;
}
Output:
is 7 here? 0
after sort: 1
88 56 42 19 7 3
On unsorted data binary_search said 0 (no) even though 7 is right there. No error, just a wrong answer. After sort, it says 1 (yes). reverse(first, last) then flipped the order in place.
| Search | Needs sorted data? | Speed |
|---|---|---|
find |
no | O(n): checks items one by one |
binary_search, lower_bound, upper_bound |
yes | O(log n) |
lower_bound(first, last, x) returns an iterator to the first item >= x (useful when you need the position, not just yes/no).
Step 6: sorting your own types
Real results are students, not bare numbers. A struct (episode 11) with a name and marks, sorted with the same one line:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
struct Student {
string name;
int marks;
};
int main() {
vector<Student> cls = {{"Asha", 72}, {"Ravi", 95}, {"Meena", 58}};
sort(cls.begin(), cls.end());
return 0;
}
g++ says:
/usr/include/c++/13/bits/predefined_ops.h:45:23: error: no match for ‘operator<’ (operand types are ‘Student’ and ‘Student’)
sort compares items with <, and C++ has no idea what makes one Student "less than" another: by name? by marks? Tell it, with a compare function: it takes two items and returns true when the first should come before the second.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
struct Student {
string name;
int marks;
};
bool byMarks(const Student& a, const Student& b) {
return a.marks > b.marks; // true: a comes first
}
int main() {
vector<Student> cls = {{"Asha", 72}, {"Ravi", 95}, {"Meena", 58}};
sort(cls.begin(), cls.end(), byMarks);
for (const Student& s : cls)
cout << s.name << " " << s.marks << endl;
return 0;
}
Output:
Ravi 95
Asha 72
Meena 58
Change one line (return a.name < b.name;) and the same call sorts by name. A compare function must be a "strict" order: return false for equal items (use > or <, never >= or <=), or sort may misbehave.
If two students have the same marks, sort may put them in any order. stable_sort keeps equal items in their original order.
sort on a list: random access needed
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main() {
list<int> marks = {72, 95, 58, 88};
sort(marks.begin(), marks.end());
return 0;
}
g++ says:
/usr/include/c++/13/bits/stl_algo.h:1948:50: error: no match for ‘operator-’ (operand types are ‘std::_List_iterator<int>’ and ‘std::_List_iterator<int>’)
sort jumps around the range (it subtracts iterators), so it needs random access iterators (episode 26). A list can only walk. So a list has its own member function:
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> marks = {72, 95, 58, 88};
marks.sort(); // the list's own sort
for (int m : marks) cout << m << " ";
cout << endl;
return 0;
}
Output:
58 72 88 95
Step 7: remove_if, and the erase-remove idiom
In episode 26 you removed fails with an it = erase(it) loop. There's an algorithm called remove_if:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool isFail(int m) {
return m < 40;
}
int main() {
vector<int> marks = {72, 35, 21, 88};
remove_if(marks.begin(), marks.end(), isFail);
cout << "size: " << marks.size() << " -> ";
for (int m : marks) cout << m << " ";
cout << endl;
return 0;
}
Output:
size: 4 -> 72 88 21 88
The size is still 4, and the list now reads 72 88 21 88. The fails weren't removed.
Why: an algorithm only sees two iterators. It can move items around inside the range, but it has no way to change the container's size. remove_if moves every item you keep to the front, in order, and returns an iterator to the new end of the kept items. Whatever is after that is leftover junk.
| Position | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| before | 72 | 35 | 21 | 88 |
after remove_if |
72 | 88 | 21 (junk) | 88 (junk) |
↑ newEnd |
So the container cuts the tail with its own erase(newEnd, end()). Algorithm moves, container erases: the erase-remove idiom.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool isFail(int m) {
return m < 40;
}
int main() {
vector<int> marks = {72, 35, 21, 88};
auto newEnd = remove_if(marks.begin(), marks.end(), isFail);
marks.erase(newEnd, marks.end()); // cut off the tail
cout << "size: " << marks.size() << " -> ";
for (int m : marks) cout << m << " ";
cout << endl;
return 0;
}
Output:
size: 2 -> 72 88
Usually written in one line: v.erase(remove_if(v.begin(), v.end(), rule), v.end());. (C++20 adds erase_if(v, rule), which does both.) It's O(n), much faster than erasing one by one from a vector.
More algorithms worth knowing
| Algorithm | What it does |
|---|---|
reverse(first, last) |
reverses the range in place |
fill(first, last, x) |
sets every item to x |
copy(first, last, out) |
copies a range to out |
unique(first, last) |
squeezes out adjacent repeats (sort first), returns the new end (erase after it) |
lower_bound / upper_bound |
binary search for a position in sorted data |
next_permutation |
the next arrangement in dictionary order |
all_of, any_of, none_of |
does every / any / no item pass a rule? |
min(a, b), max(a, b), swap(a, b) |
two values |
Common mistakes (and the real g++ messages)
| Mistake | What happens | Fix |
|---|---|---|
accumulate(fees.begin(), fees.end(), 0) on doubles |
compiles; wrong total (848 instead of 849.5) | start at 0.0 |
binary_search on unsorted data |
compiles; wrong answer (0 for a value that's there) | sort first |
sort a vector of structs with no rule |
error: no match for ‘operator<’ (operand types are ‘Student’ and ‘Student’) |
pass a compare function |
sort(lst.begin(), lst.end()) on a list |
error: no match for ‘operator-’ (operand types are ‘std::_List_iterator<int>’ and ‘std::_List_iterator<int>’) |
lst.sort() |
remove_if(...) without erase |
compiles; size unchanged, junk at the end | v.erase(remove_if(...), v.end()) |
*max_element(v.begin(), v.end()) on an empty vector |
compiles; undefined behaviour (it returns end()) |
check !v.empty() first |
Forgetting #include <numeric> for accumulate |
error: ‘accumulate’ was not declared in this scope |
include <numeric> |
Mini project: the results office report
Average, distinctions, fails, then remove the fails and print a rank list of the rest. accumulate with a fourth argument uses your own "add" function, so it can add up a field of a struct.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;
struct Student {
string name;
int marks;
};
bool byMarks(const Student& a, const Student& b) { return a.marks > b.marks; }
bool isFail(const Student& s) { return s.marks < 40; }
bool isDistinction(const Student& s) { return s.marks >= 75; }
int addMarks(int total, const Student& s) { return total + s.marks; }
int main() {
vector<Student> cls = {{"Asha", 72}, {"Ravi", 95}, {"Meena", 38}, {"Kiran", 88}, {"Dev", 21}, {"Neha", 64}};
int total = accumulate(cls.begin(), cls.end(), 0, addMarks);
cout << "Class average: " << total / (double)cls.size() << endl;
cout << "Distinctions: " << count_if(cls.begin(), cls.end(), isDistinction) << endl;
cout << "Fails: " << count_if(cls.begin(), cls.end(), isFail) << endl;
cls.erase(remove_if(cls.begin(), cls.end(), isFail), cls.end()); // erase-remove
sort(cls.begin(), cls.end(), byMarks);
cout << "Rank list of passed students:" << endl;
for (int i = 0; i < cls.size(); i++)
cout << " " << i + 1 << ". " << cls[i].name << " " << cls[i].marks << endl;
return 0;
}
Output:
Class average: 63
Distinctions: 2
Fails: 2
Rank list of passed students:
1. Ravi 95
2. Kiran 88
3. Asha 72
4. Neha 64
Practice
- Sort words by length with a compare function.
- Count how many marks are 90 or above with
count_if. - Find the average of a
vector<double>of prices withaccumulate. - Remove every negative number from a vector with erase-remove.
Solutions
1. stable_sort keeps "apple" before "mango" (both length 5) as in the input.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
bool shorterFirst(const string& a, const string& b) {
return a.size() < b.size();
}
int main() {
vector<string> words = {"banana", "kiwi", "apple", "fig", "mango"};
stable_sort(words.begin(), words.end(), shorterFirst); // equal lengths keep their order
for (const string& w : words) cout << w << " ";
cout << endl;
return 0;
}
Output:
fig kiwi apple mango banana
2.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool ninetyPlus(int m) { return m >= 90; }
int main() {
vector<int> marks = {72, 95, 90, 58, 99, 88};
cout << count_if(marks.begin(), marks.end(), ninetyPlus) << endl;
return 0;
}
Output:
3
3. Start at 0.0 so the paise aren't chopped off.
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int main() {
vector<double> prices = {49.5, 120.25, 99.75, 30.5};
double total = accumulate(prices.begin(), prices.end(), 0.0); // 0.0, not 0
cout << "average: " << total / prices.size() << endl;
return 0;
}
Output:
average: 75
4.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool isNegative(int x) { return x < 0; }
int main() {
vector<int> readings = {12, -3, 8, -7, -1, 20};
readings.erase(remove_if(readings.begin(), readings.end(), isNegative), readings.end());
for (int r : readings) cout << r << " ";
cout << "(size " << readings.size() << ")" << endl;
return 0;
}
Output:
12 8 20 (size 3)
Quick quiz
What does this print?
vector<int> v = {5, 1, 4, 1, 3};
sort(v.begin(), v.end());
cout << count(v.begin(), v.end(), 1) << " "
<< *max_element(v.begin(), v.end()) << " "
<< find(v.begin(), v.end(), 4) - v.begin();
Answer
2 5 3. After sorting, v is 1 1 3 4 5. There are two 1s; the maximum is 5; and 4 sits at position 3 (counting from 0).
Interview questions
- What is the time complexity of
std::sort? O(n log n) comparisons (guaranteed since C++11). GCC uses introsort. sortvsstable_sort?stable_sortkeeps equal elements in their original relative order (O(n log n), may use extra memory);sortdoesn't promise that.- Why does
remove_ifnot change the size? Algorithms work on iterators and can't add or remove container elements; it returns the new logical end, and you callerase. findvsbinary_search?findis O(n) and works on any data;binary_searchis O(log n) and requires sorted data (else the answer is wrong).- Why can't
std::sortsort astd::list? It needs random access iterators; uselist::sort()(a merge sort, O(n log n)). - What does a comparator have to satisfy? Strict weak ordering:
comp(a, a)must be false; using<=breaks it and can crashsort. - How do you get the index of the maximum element?
max_element(v.begin(), v.end()) - v.begin(). - What is the pitfall of
accumulate(v.begin(), v.end(), 0)on doubles? The result type is the type of the initial value (int), so decimals are truncated; use0.0. - Remove duplicates from a vector.
sort, thenv.erase(unique(v.begin(), v.end()), v.end());.
Glossary
| Term | Meaning, with an example |
|---|---|
| STL algorithm | A ready-made function in <algorithm> / <numeric> that works on a range of iterators: sort(v.begin(), v.end()) |
range [first, last) |
Items from first up to but not including last. |
| bubble sort | Sorting by repeatedly swapping wrong-order neighbours; O(n²), too slow for big data. |
| O(n²), O(n log n), O(log n) | How the work grows with n items: n², n × log n, log n. For n = 80,000: billions, ~1.3 million, ~17. |
sort |
Sorts a random-access range, smallest first by default. |
greater<int>() |
A ready-made comparator meaning "bigger first" (<functional>). |
| compare function (comparator) | Takes two items, returns true if the first should come first: bool byMarks(const Student& a, const Student& b) |
| predicate (rule function) | Takes one item, returns true/false: bool isFail(int m) |
find |
Returns an iterator to the first match, or last if none. |
count, count_if |
Count items equal to a value / passing a rule. |
max_element, min_element |
Return an iterator to the biggest / smallest item. |
accumulate |
Adds up a range starting from a given value (<numeric>); the start value's type is the result type. |
| binary search | Finding a value in sorted data by halving the range each step. |
reverse |
Reverses a range in place. |
remove_if |
Moves the items to keep to the front and returns the new end; doesn't change the size. |
| erase-remove idiom | v.erase(remove_if(v.begin(), v.end(), rule), v.end()); really removes items. |
stable_sort |
A sort that keeps equal items in their original order. |
| introsort | The quicksort/heapsort/insertion-sort mix GCC's sort uses. |
| off-by-one bug | A loop that runs one time too many or too few, e.g. <= instead of <. |
Summary
- Bubble sort by hand took seconds for 80,000 marks (O(n²)).
sort(first, last)took a millisecond or two (O(n log n)). - The algorithms take a range of iterators, so they work on most containers:
sort,find,count,count_if,max_element,min_element,reverse,binary_search, andaccumulatefrom<numeric>. findreturnslastwhen the value is missing;max_elementgives a position, so you know who.- Traps that compile:
accumulate(..., 0)on decimals (use0.0),binary_searchon unsorted data,remove_ifwithouterase. sortneeds<or a compare function for your own types, and random access iterators (alistuses.sort()).- Erase-remove:
v.erase(remove_if(v.begin(), v.end(), rule), v.end());.
Next episode: containers clean up their own memory, but new and delete from episode 10 don't. Forget one delete and memory leaks. You'll invent pointers that delete themselves: smart pointers.