{"title":"Algorithms Overview","description":null,"content":"The STL ships with around a hundred ready-made algorithms for searching, sorting, transforming, counting, and combining sequences. They live mostly in `` and ``, and they are built on a single idea: an algorithm does not know what container it is working on. It only knows how to walk a range using a pair of iterators. This chapter maps the available algorithms, explains the iterator-range convention every algorithm follows, and points to the chapters that drill into specific families.\n\n---\n\n# The Stepanov Decoupling\n\nAlexander Stepanov, the designer of the STL, made one architectural choice that defines the whole library: algorithms and containers do not know about each other. Instead, they meet at a common interface called an **iterator**. An iterator is anything that behaves like a pointer; you can dereference it to read or write an element, and you can advance it to the next position.\n\nWithout this decoupling, you would need a separate `sort` for `vector`, another for `deque`, another for built-in arrays, and so on. With it, you write one `std::sort` and it works on every container that offers random-access iterators, including a raw C array.\n\n\n```mermaid\nflowchart LR\n A[Algorithm
std::sort]:::primary\n I1[Iterator pair
begin, end]:::iter\n C1[std::vector]:::container\n C2[std::deque]:::container\n C3[int array]:::container\n\n A --> I1\n I1 --> C1\n I1 --> C2\n I1 --> C3\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef iter fill:#ffa94d,stroke:#000,color:#000\n classDef container fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe algorithm talks to the iterator. The iterator talks to the container. Neither side has to know about the other. Add a new container type tomorrow and every existing algorithm works on it, as long as the new container hands out iterators of the correct category. Write a new algorithm and it works on every existing container. The library scales as multiplication rather than addition.\n\nA small demonstration: `std::find` works the same way on a vector, a list, and a raw array.\n\n\n```cpp\n#include \n#include \n#include \n#include \n\nint main() {\n int prices[] = {2999, 1499, 999, 4999, 1999};\n std::vector ratings = {5, 4, 5, 3, 5};\n std::list categories = {\"books\", \"audio\", \"kitchen\"};\n\n auto p = std::find(std::begin(prices), std::end(prices), 999);\n auto r = std::find(ratings.begin(), ratings.end(), 3);\n auto c = std::find(categories.begin(), categories.end(), std::string(\"audio\"));\n\n std::cout << \"price 999 found: \" << (p != std::end(prices)) << \"\\n\";\n std::cout << \"rating 3 found: \" << (r != ratings.end()) << \"\\n\";\n std::cout << \"audio found: \" << (c != categories.end()) << \"\\n\";\n return 0;\n}\n```\n\n\nOne algorithm, three different containers, no template specialisation written by hand. The `std::find` source code never mentions `vector` or `list`.\n\n---\n\n# The Half-Open Range `[first, last)`\n\nEvery STL algorithm takes a pair of iterators that mark a range. The convention is **half-open**: `first` points at the first element you want to process, and `last` points one past the last element. That `last` position is sometimes called the **sentinel** or **end iterator**, and you never dereference it.\n\n\n```mermaid\nflowchart LR\n F[first]:::iter --> E1[42]:::elem\n E1 --> E2[17]:::elem\n E2 --> E3[8]:::elem\n E3 --> E4[31]:::elem\n E4 --> L[last
one past end]:::sentinel\n\n classDef iter fill:#00ceff,stroke:#000,color:#000\n classDef elem fill:#69db7c,stroke:#000,color:#000\n classDef sentinel fill:#ff8787,stroke:#000,color:#000\n```\n\n\nThree things fall out of this convention. An empty range is `first == last`, which is easy to test. You can express the whole container with `c.begin(), c.end()`, and any sub-range without doing arithmetic that risks off-by-one bugs. Algorithms that did not find anything return `last` as their result, which is why so much code looks like `if (it != v.end())`.\n\nThe pattern is consistent enough that once you have learned it, every new algorithm reads the same way.\n\n\n```cpp\n#include \n#include \n#include \n\nint main() {\n std::vector prices = {2999, 1499, 999, 4999, 1999};\n\n // whole range\n auto cheapest = std::min_element(prices.begin(), prices.end());\n\n // sub-range: skip the first element\n auto cheapestExceptFirst = std::min_element(prices.begin() + 1, prices.end());\n\n std::cout << \"cheapest: \" << *cheapest << \"\\n\";\n std::cout << \"cheapest after first: \" << *cheapestExceptFirst << \"\\n\";\n return 0;\n}\n```\n\n\nThe second call hands `min_element` a smaller range. The algorithm does not know or care that the underlying vector has more elements before `first` or that the iterators came from a vector at all.\n\n---\n\n# The Common Shape\n\nMost algorithms follow one of two return shapes.\n\nAlgorithms that **search or query** return an iterator pointing at what they found, or `last` if they did not find anything: `find`, `find_if`, `search`, `min_element`, `lower_bound`, `partition_point`. Algorithms that **count or fold** return a value: `count`, `count_if`, `accumulate`, `all_of`, `equal`.\n\nAlgorithms that **modify or move** elements return an iterator that marks the new logical end of the range or the position just past the last written element: `copy`, `transform`, `remove`, `unique`. This is how the erase-remove idiom works, covered below.\n\nThe signature shape is almost always one of:\n\n\n```cpp\n// query / search\nauto it = algo(first, last, value_or_predicate);\n\n// modify\nauto out_end = algo(first, last, out, value_or_op);\n\n// count / fold\nauto n = algo(first, last, init, op);\n```\n\n\nOnce you can read those three shapes, the names and parameters of any specific algorithm fall into one of them.\n\n\n```cpp\n#include \n#include \n#include \n#include \n\nint main() {\n std::vector cartPrices = {29.99, 14.99, 9.99, 49.99, 19.99};\n\n // query\n auto firstExpensive = std::find_if(cartPrices.begin(), cartPrices.end(),\n [](double p) { return p > 30.0; });\n\n // count\n auto cheapItems = std::count_if(cartPrices.begin(), cartPrices.end(),\n [](double p) { return p < 20.0; });\n\n // fold\n double cartTotal = std::accumulate(cartPrices.begin(), cartPrices.end(), 0.0);\n\n std::cout << \"first item over $30: $\" << *firstExpensive << \"\\n\";\n std::cout << \"items under $20: \" << cheapItems << \"\\n\";\n std::cout << \"cart total: $\" << cartTotal << \"\\n\";\n return 0;\n}\n```\n\n\nThree different algorithms, three different return types, but the same iterator-pair entry point. Once familiar with the `first, last, ...` pattern, the calls read like English: \"find if any cart price is above 30,\" \"count if a price is under 20,\" \"accumulate from the beginning to the end, starting at zero.\"\n\n---\n\n# Predicates and the `_if` Family\n\nA **predicate** is a callable that takes one or two elements and returns a `bool`. Algorithms that test elements come in two flavours: a \"by value\" version that compares against a fixed value, and an `_if` version that takes a predicate.\n\n\n| Plain | `_if` version |\n|-------|----------------|\n| `find(first, last, val)` | `find_if(first, last, pred)` |\n| `count(first, last, val)` | `count_if(first, last, pred)` |\n| `remove(first, last, val)` | `remove_if(first, last, pred)` |\n| `replace(first, last, old, new)` | `replace_if(first, last, pred, new)` |\n| `copy(first, last, out)` | `copy_if(first, last, out, pred)` |\n\n\nThe non-`_if` versions are convenient when you have a fixed value to look for. The `_if` versions are more powerful because the predicate can encode any condition.\n\n\n```cpp\n#include \n#include \n#include \n\nint main() {\n std::vector stockLevels = {12, 0, 5, 0, 9, 17, 0};\n\n auto outOfStockCount = std::count(stockLevels.begin(), stockLevels.end(), 0);\n\n auto lowStockCount = std::count_if(stockLevels.begin(), stockLevels.end(),\n [](int n) { return n > 0 && n < 10; });\n\n std::cout << \"out of stock: \" << outOfStockCount << \"\\n\";\n std::cout << \"low stock: \" << lowStockCount << \"\\n\";\n return 0;\n}\n```\n\n\nLambdas, available since C++11, are how predicates are written in modern code. Before lambdas, this required a separate function or a functor class. The lambda chapter covers the syntax in detail. These calls can be read as \"for each element, run this block and use its `bool` result.\"\n\nA family of quantifier algorithms takes a predicate and returns a `bool` directly.\n\n\n```cpp\n#include \n#include \n#include \n\nint main() {\n std::vector stock = {12, 5, 9, 17};\n\n bool noneZero = std::none_of(stock.begin(), stock.end(),\n [](int n) { return n == 0; });\n bool allPositive = std::all_of(stock.begin(), stock.end(),\n [](int n) { return n > 0; });\n bool anyHigh = std::any_of(stock.begin(), stock.end(),\n [](int n) { return n > 15; });\n\n std::cout << \"none zero: \" << noneZero << \"\\n\";\n std::cout << \"all positive: \" << allPositive << \"\\n\";\n std::cout << \"any over 15: \" << anyHigh << \"\\n\";\n return 0;\n}\n```\n\n\n`all_of`, `any_of`, and `none_of` short-circuit, meaning they stop the moment the answer is decided. `any_of` returns `true` as soon as one element matches; `all_of` returns `false` as soon as one element fails.\n\nQuantifier algorithms are O(n) worst case but often much less because they bail out early. For an `any_of` that matches the first element, the cost is the cost of one predicate call.\n\n---\n\n# Where the Algorithms Live\n\nMost algorithms sit in ``. Numeric folds live in `` because they grew out of a separate proposal. The C++20 ranges versions live in ``.\n\n\n| Header | Contents |\n|--------|----------|\n| `` | The bulk of generic algorithms: searching, sorting, modifying, partitioning, heaps, set operations |\n| `` | Folds and scans: `accumulate`, `reduce`, `transform_reduce`, `inner_product`, `partial_sum`, `iota` |\n| `` (C++20) | `std::ranges::sort`, `std::ranges::find`, and views like `std::views::filter` |\n| `` | Pre-built function objects used as predicates and comparators: `std::less`, `std::greater`, `std::plus` |\n| `` (C++17) | Execution policies for parallel and vectorised algorithms |\n\n\nIncluding the correct header is part of the contract. Code that uses `std::accumulate` will not compile against `` alone, and the error message can be cryptic.\n\n---\n\n# A Map of the Algorithm Families\n\nThere are too many algorithms to learn individually. Knowing the **families** is what matters, so you know where to look. The remaining chapters in this section drill into each family; this is the map.\n\n### Non-Modifying\n\nThese read the range without changing it. They search, count, test, and compare.\n\n\n| Algorithm | Job |\n|-----------|-----|\n| `find`, `find_if`, `find_if_not` | Locate the first element matching a value or predicate |\n| `find_first_of` | First occurrence of any element from a second range |\n| `adjacent_find` | First pair of equal (or predicate-matching) neighbours |\n| `count`, `count_if` | Count matching elements |\n| `search`, `search_n` | Find a subsequence inside a range |\n| `mismatch` | First position where two ranges differ |\n| `equal` | Are two ranges element-wise equal? |\n| `all_of`, `any_of`, `none_of` | Quantifiers |\n| `min_element`, `max_element`, `minmax_element` | Iterators to extreme elements |\n\n\n### Modifying\n\nThese produce a new sequence somewhere, either in place or written to an output iterator. They never resize containers; that is an iterator-level operation, not an algorithm one.\n\n\n| Algorithm | Job |\n|-----------|-----|\n| `copy`, `copy_if`, `copy_n`, `copy_backward` | Copy elements |\n| `move`, `move_backward` | Move elements (uses `std::move` per element) |\n| `transform` | Apply a function to each element, write the result somewhere |\n| `replace`, `replace_if` | Replace elements that equal a value or match a predicate |\n| `fill`, `fill_n` | Write the same value to every position |\n| `generate`, `generate_n` | Call a nullary function and write its result to each position |\n| `swap_ranges` | Swap elements between two ranges |\n| `reverse`, `rotate`, `shuffle` | Rearrange elements |\n\n\n### Removing\n\nThese do not actually remove anything from a container. They **logically remove** by shifting unwanted elements past a new end iterator, and you call the container's `erase` to physically shrink. This is the erase-remove idiom.\n\n\n```cpp\n#include \n#include \n#include \n\nint main() {\n std::vector cart = {10, 0, 25, 0, 7, 0, 42};\n\n // logically remove zeros\n auto newEnd = std::remove(cart.begin(), cart.end(), 0);\n\n std::cout << \"size before erase: \" << cart.size() << \"\\n\";\n\n // physically shrink\n cart.erase(newEnd, cart.end());\n\n std::cout << \"size after erase: \" << cart.size() << \"\\n\";\n for (int n : cart) std::cout << n << \" \";\n std::cout << \"\\n\";\n return 0;\n}\n```\n\n\n`std::remove` does not know what container it is working on. It cannot call `erase`. All it can do is overwrite the wanted elements toward the front and return an iterator pointing past them. The container is still seven elements long after the call. The `erase` call is what physically drops the tail. Other algorithms in this family are `remove_if` and `unique` (which removes consecutive duplicates).\n\n`std::remove` is O(n) and does the work in one pass. The follow-up `erase` is also O(n) but only over the tail being dropped. Skipping the erase leaves the container's size wrong, which is a common mistake.\n\nC++20 adds `std::erase` and `std::erase_if` free functions in ``, ``, and friends that wrap the idiom into one call. With C++20, prefer them.\n\n### Sorting\n\nThe sorting family includes:\n\n\n| Algorithm | Job |\n|-----------|-----|\n| `sort` | Sort the whole range, not stable |\n| `stable_sort` | Sort and preserve relative order of equal elements |\n| `partial_sort` | Sort the first `k` smallest into the front |\n| `nth_element` | Place the element that belongs at position `n` there, partition the rest |\n| `is_sorted`, `is_sorted_until` | Check sortedness |\n\n\n### Binary Search\n\nThese require a sorted range as input. Calling them on an unsorted range is undefined behaviour. They run in O(log n) on random-access iterators.\n\n\n| Algorithm | Job |\n|-----------|-----|\n| `lower_bound` | First position where `value` could be inserted without breaking sort order |\n| `upper_bound` | First position strictly greater than `value` |\n| `equal_range` | Pair of (`lower_bound`, `upper_bound`) |\n| `binary_search` | A `bool`: is the value present? |\n\n\nSearching gets its own chapter. `binary_search` only tells you yes or no, while `lower_bound` and `upper_bound` give you positions to work with.\n\n### Numeric\n\nThe folds and scans live in ``.\n\n\n| Algorithm | Job |\n|-----------|-----|\n| `accumulate` | Left fold with `+` (or a custom op) |\n| `reduce` (C++17) | Unordered fold, parallelisable |\n| `transform_reduce` (C++17) | Fused map-then-reduce, parallelisable |\n| `inner_product` | Sum of products of two ranges |\n| `partial_sum` | Running totals |\n| `iota` | Fill with successive integers starting at a given value |\n| `adjacent_difference` | Element-wise differences |\n\n\n`accumulate` is the default. `reduce` is for parallelised operations, because `reduce` does not promise left-to-right order, which lets the implementation split the work across threads.\n\n\n```cpp\n#include \n#include \n#include \n\nint main() {\n std::vector cartPrices = {29.99, 14.99, 9.99, 49.99, 19.99};\n\n double total = std::accumulate(cartPrices.begin(), cartPrices.end(), 0.0);\n double withTax = std::accumulate(cartPrices.begin(), cartPrices.end(), 0.0,\n [](double sum, double p) { return sum + p * 1.08; });\n\n std::cout << \"subtotal: $\" << total << \"\\n\";\n std::cout << \"with tax: $\" << withTax << \"\\n\";\n return 0;\n}\n```\n\n\nThe third argument is the initial value of the accumulator. Its **type** also drives the result type, which is a common pitfall: `std::accumulate(v.begin(), v.end(), 0)` on a `vector` accumulates into an `int`, truncating decimals without warning. Pass `0.0` to keep the math in `double`.\n\n### Heap\n\nA heap is a binary tree laid out flat in an array such that the largest element is always at the front. The STL does not give you a heap container directly; it gives you a set of algorithms that maintain the heap invariant on any random-access range. `std::priority_queue` is a container adapter built on top of these.\n\n\n| Algorithm | Job |\n|-----------|-----|\n| `make_heap` | Rearrange a range into a heap, O(n) |\n| `push_heap` | Add the last element of the range to the heap, O(log n) |\n| `pop_heap` | Move the front (largest) to the back and re-heapify the rest, O(log n) |\n| `sort_heap` | Sort a heap into ascending order, O(n log n) |\n| `is_heap`, `is_heap_until` | Check heap-ness |\n\n\n---\n\n# Execution Policies (C++17)\n\nSince C++17, most standard algorithms accept an **execution policy** as their first argument that tells the implementation it is allowed to parallelise or vectorise the work. The policies live in ``.\n\n\n| Policy | What it allows |\n|--------|----------------|\n| `std::execution::seq` | Sequential, in order, as if no policy |\n| `std::execution::par` | Parallel: multiple threads may execute the algorithm |\n| `std::execution::par_unseq` | Parallel **and** unsequenced: threads plus SIMD vectorisation, with stricter requirements |\n| `std::execution::unseq` (C++20) | Single-threaded but vectorisable |\n\n\n\n```cpp\n#include \n#include \n#include \n#include \n#include \n\nint main() {\n std::vector stock(1'000'000);\n std::iota(stock.begin(), stock.end(), 1);\n\n // sequential\n auto total = std::reduce(std::execution::seq, stock.begin(), stock.end(), 0LL);\n\n // parallel\n auto totalPar = std::reduce(std::execution::par, stock.begin(), stock.end(), 0LL);\n\n std::cout << \"seq total: \" << total << \"\\n\";\n std::cout << \"par total: \" << totalPar << \"\\n\";\n return 0;\n}\n```\n\n\n`par_unseq` is the most aggressive. It permits the implementation to interleave element processing across threads **and** within a thread via SIMD instructions. The trade is that your predicate or operation must be both thread-safe and free of memory ordering assumptions. Taking a mutex inside a `par_unseq` lambda is undefined behaviour because the same thread might \"re-enter\" the lambda while still holding the lock.\n\nThere is an ABI catch with these policies. On libstdc++ (g++) and libc++ historically, the parallel implementations were backed by Intel's TBB library. Compiling code that uses `std::execution::par` may require linking against TBB explicitly (`-ltbb`) or installing it through the system package manager. Standard libraries are moving toward self-contained implementations, but a linker error mentioning TBB has this cause.\n\nParallel execution only pays off when the per-element work is substantial or the range is large enough to amortise thread setup. For a `par` sum over a 100-element vector, the threading overhead usually exceeds the speedup. Profile before assuming parallel is faster.\n\n---\n\n# Ranges (C++20)\n\nC++20 introduces a redesign of the algorithm interface that lets you pass a container directly instead of two iterators.\n\n\n```cpp\n#include \n#include \n#include \n#include \n\nint main() {\n std::vector prices = {2999, 1499, 999, 4999, 1999};\n\n // old style, two iterators\n std::sort(prices.begin(), prices.end());\n\n // C++20 ranges style, one range\n std::ranges::sort(prices);\n\n for (int p : prices) std::cout << p << \" \";\n std::cout << \"\\n\";\n return 0;\n}\n```\n\n\n`std::ranges::sort(prices)` is equivalent to `std::sort(prices.begin(), prices.end())`. The ranges versions also support **projections**, which let you sort by a member or computed value without writing a comparator. The Ranges Library chapter in the Modern C++ Features section covers all of this. Every classic algorithm has a `std::ranges::` cousin that is shorter to call. The iterator-pair versions are not going away; they are still what the new versions are built on.\n\n---\n\n# Practical Walkthrough: A Cart Summary\n\nA practical example: given a cart of products with prices and quantities, compute the subtotal, find the most expensive item, and report how many items are on offer (price below a threshold).\n\n\n```cpp\n#include \n#include \n#include \n#include \n#include \n\nstruct CartItem {\n std::string name;\n double price;\n int quantity;\n};\n\nint main() {\n std::vector cart = {\n {\"Wireless Headphones\", 79.99, 1},\n {\"USB Cable\", 9.99, 3},\n {\"Phone Stand\", 14.99, 2},\n {\"Laptop Sleeve\", 29.99, 1},\n {\"Mouse Pad\", 7.49, 4},\n };\n\n // subtotal: fold price * quantity\n double subtotal = std::accumulate(\n cart.begin(), cart.end(), 0.0,\n [](double sum, const CartItem& i) { return sum + i.price * i.quantity; });\n\n // most expensive item by unit price\n auto top = std::max_element(\n cart.begin(), cart.end(),\n [](const CartItem& a, const CartItem& b) { return a.price < b.price; });\n\n // items on offer (under $15)\n auto onOffer = std::count_if(\n cart.begin(), cart.end(),\n [](const CartItem& i) { return i.price < 15.0; });\n\n std::cout << \"Subtotal: $\" << subtotal << \"\\n\";\n std::cout << \"Most expensive: \" << top->name << \" ($\" << top->price << \")\\n\";\n std::cout << \"Items on offer: \" << onOffer << \"\\n\";\n return 0;\n}\n```\n\n\nThree different algorithms, three different return shapes, one consistent calling convention. None of the algorithms know that `CartItem` exists. The lambdas teach each one what to do with the elements, and the iterators carry the data through.","pageType":"cpp"}

Algorithms Overview

Get Premium