Algorithms
Overview
The <algorithm> header is the crown jewel of C++. It contains over 100 heavily-optimized, production-ready mathematical and structural algorithms (like sorting, searching, reversing, counting, and shuffling).
Because these algorithms operate entirely on Iterators, they are completely agnostic. You can pass std::sort() the iterators for a Vector of Integers, a raw C-array of Doubles, or a Deque of Custom Objects, and it will instantly compile highly optimized machine code for that specific scenario, saving you thousands of hours of rewriting code.
Syntax
#include <iostream>
#include <vector>
#include <algorithm> // CRITICAL: Must include this!
int main() {
std::vector<int> data = {42, 10, 99, 10, 5};
// 1. SORTING (Ascending by default)
std::sort(data.begin(), data.end());
// Now: 5, 10, 10, 42, 99
// 2. REVERSING (Flips the data instantly)
std::reverse(data.begin(), data.end());
// Now: 99, 42, 10, 10, 5
// 3. COUNTING
int tens = std::count(data.begin(), data.end(), 10); // Returns 2!
return 0;
}Common Pitfalls
- Using
std::find()on astd::maporstd::set. While you can technically pass map iterators into the globalstd::find()algorithm, it executes a slow $O(N)$ linear scan. Maps have their own built-in.find()method that utilizes the Red-Black Tree for a blazing fast $O(log N)$ search. Always use the built-in method for associative containers.
Interview Questions
std::sort() to sort objects in Descending order, or to sort custom classes (like sorting Players by Score)?The std::sort function takes an optional 3rd parameter called a 'Comparator'. This can be a custom function or a Lambda Expression that returns a boolean dictating how two elements should be compared (e.g., return a > b; for descending order).
Real-World Example
Using a Custom Comparator (Lambda Expression) to sort a vector of complex Objects by a specific private variable.
#include <iostream>
#include <vector>
#include <algorithm>
struct Player {
int score;
};
int main() {
std::vector<Player> lobby = {{50}, {99}, {10}};
// We pass a Lambda function as the 3rd argument!
// It tells the algorithm: "A goes before B if A's score is LARGER."
std::sort(lobby.begin(), lobby.end(), [](Player a, Player b) {
return a.score > b.score;
});
// Lobby is now sorted: 99, 50, 10
std::cout << "Winner: " << lobby[0].score << "\n";
return 0;
}Check Your Knowledge
Test your understanding of Algorithms with these quick questions.