Algorithm Intuition

This page exists to catalog and explore the C++ STL algorithms, and to name and justify missed algorithms.

The name "algorithm intuition" comes from Kate Gregory by way of Conor Hoekstra. It refers to an ability to look at a problem and break it down into a series of high-level algorithmic steps, rather than as a low-level series of discrete steps, in the same way as skilled programmers are able to look at a set of characteristics and select the correct abstract data structure, without having to think about the discrete nodes or pointers that make it up. Building up an intuition for algorithms is essential to being a great C++ programmer, and makes a huge difference in the clarity, consiceness, and ultimately correctness of one's code.

This webpage is an attempt to take the long list of over a hundred named algorithms and break them down into families, providing an easy high-level view of what they do, expressed in the form of input, output, and abstract operations.

I do not actually know if a search (and particularly, a search which returns a whole subrange) is strictly speaking a catamorphism, but even if they are not, there are very strong links between several of the searching and folding algorithms, and several of the folds can be implemented in terms of a related search algorithm. I am also uncertain about whether everything I have labelled as an anamorphism truly is one, as explained below.

Blue names indicate algorithms described by Conor. Green names are from kblib. Red names in the "Default operations" column indicate non-overridable parameters and a lack of generality. The notes below the tables explain the rest of the terminology and notation I used.

Home

Catamorphisms (folds) and Searches

NameInput ranges*Accumu­latorReturnsOperationsDefault operationsOrderCompare to
inner_product 2ArgValueA, bTplus, multipliesFwd.
adjacent_reduce 1sArgValueA, bTFwd.inner_product
transform_reduce 1 / 2ArgValueacR, uT / bTplus, multiplies
find 1+ValuePositionequal_toS/C
find_if, find_if_not 1PositionuPS/C
find_first_of 2PositionbPequal_toS/Cfind_if
min_element, max_element 1FirstPositionbPlessFwd.
minmax_element 1First2 PositionsbPlessFwd.
lower_bound, upper_bound 1+ValuePositionbPlessB/S
equal_range 1+ValueRangebPlessB/S
search, search_n, find_end 2PositionbPequal_to
starts_with 2boolbPequal_toFwd.
ends_with 2boolbPequal_to
ranges::starts_with, ranges::ends_with 2boolbP, uT, uTΔequal_to, identity, identity
search (C++17) 1PositionSearcher
find_match 2PositionbPequal_toS/C
mismatch 2PositionbPequal_toS/Cfind_match
adjacent_find 1sPositionbPequal_toS/Cfind_match
is_sorted_until 1sPositionbPlessS/Cfind_match
accumulate 1ArgValueAplusFwd.
sum 1FirstValueAplusFwd.accumulate
reduce 1ArgValueacRplus
count 1+Value0size_tequal_toFwd.accumulate
count_if 10size_tuPFwd.accumulate
binary_search 1+ValueboolbPlessB/S
is_partitioned 1booluPFwd.
is_sorted 1boolbPlessFwd.
is_heap 1boolbPless
is_permutation 2boolbPequal_to
includes 2boolbPlessFwd.
first_result 1+Value / 2+ValueValueuT / bTS/C
all_of, none_of 1truebooluPS/Cfirst_result
any_of 1falsebooluPS/Cfirst_result
contains 1+Valuefalseboolequal_toS/Cfirst_result
equal 2boolbPequal_toFwd.first_result
lexicographical_compare 2boolbPlessFwd.first_result
lexicographical_compare_three_way 2orderingCompareΔcompare_three_wayFwd.first_result
partition_point 1PositionuPB/S
is_heap_until 1PositionbPless
NameInput ranges*Accumu­latorReturnsOperationsDefault operationsOrderCompare to

Anamorphisms (unfolds/transforms)

NameInput ranges*Accumu­latorOutput rangesOperationsDefault operationsOrderCompare to
transform_inclusive_scan 1First, Arg1aR, uT
transform_exclusive_scan 1Arg1aR, uT
partial_sum 1First1AplusFwd.
inclusive_scan 1First, Arg1aRplus
exclusive_scan 1Arg1aRplus
adjacent_difference 1sQuasi1fDminusFwd.adjacent_transform
adjacent_transform 1sQuasi1DFwd.adjacent_difference
adjacent_inclusive_scan 1sFirst1A, DFwd.
transform 1 / 21uT / bT
copy, copy_n 11Fwd.transform
copy_backward 11Rev.
move 11Fwd.shift_left
move_backward 11Rev.shift_right
replace_copy 1+ValueArg1equal_toFwd.transform
replace_copy_if 1Arg1uPFwd.transform
reverse_copy 11transform
rotate_copy 1d1
sample 1Arg1Fwd.
partial_sort_copy 11bPless
merge 21bPlessFwd.
partition_copy 12uPFwd.
transform_if 11uP, uTFwd.
copy_if, remove_copy_if 11uPFwd.transform_if
remove_copy 1+Value1equal_toFwd.transform_if
unique_copy 1First1bPequal_toFwd.
set_difference, set_intersection, set_symmetric_difference, set_union 21bPlessFwd.
regex_replace 21RegexSee note
search_replace_copy 31bPequal_toregex_replace
generate, generate_n 01GFwd.
iota 0Arg1++Fwd.generate
iota 0Arg1uT++Fwd.generate
fill, fill_n 0Arg1Fwd.generate, generate_n
for_each, for_each_n 10muTFwd.
for_each, for_each_n 1 / 20muT / mbTFwd.
swap_ranges 2SelfswapFwd.for_each
remove 1+ValueSelfequal_toFwd.
remove_if 1SelfuPFwd.
unique 1SelfbPequal_toFwd.
replace 1+ValueSelfequal_toFwd.transform
replace_if 1SelfuPFwd.transform
reverse 1SelfYesswap_ranges
rotate 1dSelfYes
shift_left 1dSelfFwd.move
shift_right 1dSelfYesmove_backward
shuffle 1+URBGSelf
next_permutation, prev_permutation 1Self
partition, stable_partition 1SelfuP
sort, partial_sort, stable_sort, nth_element 1SelfbPless
make_heap, push_heap, pop_heap, sort_heap 1SelfbPless
inplace_merge 1dSelfbPless
NameInput ranges*Accumu­latorOutput rangesOperationsDefault operationsOrderCompare to

* 's' indicates staggered access to a range. 'd' indicates that a second position in the range is also required.
 The abbreviations used for operations are described below.

Operation types

A
Accumulation
(A, T)A
R
Reduction
(T, T)T
D
Adjacent Op
(T, T)U
T
Transform
(Ts...)U
P
Predicate
(Ts...)bool
G
Generator
()U

Operation semantics

a
Associative
op(a, op(b, c))op(op(a, b), c)
c
Commutative
op(a, b)op(b, a)
f
Flipped
op(b, a)
u
Unary
op(a)
b
Binary
op(a, b)
m
Mutable
op(a) may modify a

If an operation is specified to be associative (but not commutative), and the actual operation provided is not, the result is potentially non-deterministic, however, it is not UB for any such algorithm, as far as I can tell.
 A blank space means unspecified evaluation/traversal order. "S/C" means forward order with short-circuiting (early return). "B/S" means binary search. "Yes" means that an order is specified, but it is not one of the above. The mark indicates that an algorithm may execute out-of-order and/or in parallel, and may accept an execution policy.
Δ This analysis makes no distinction between unary transformations and projections as used in the ranges library, nor does it make any distinction between Compare predicates and general predicates. lexicographical_compare_three_way is unique in that the Compare predicate it requires must return one of the standard three-way ordering types (strong_ordering, weak_ordering, or partial_ordering), rather than bool.
 For the purposes of this analysis, returning an iterator, an index, or a pair of corresponding iterators in different ranges (i.e. mismatch) are all considered to be a single "position". "Range" as a return value of a catamorphism indicates that two iterators identifying a subrange of the input are returned, not that a new range is produced. "2 Positions" means two unassociated iterators are returned, which do not form a range.
 I'm not certain if for_each is, strictly speaking, an anamorphism, because it does not directly produce any output. However, I include it in the anamorphisms table because, as a void function it doesn't neatly fit into this analysis, and because swap_ranges, which clearly is an anamorphism, can be implemented in terms of (the binary version of) it.
 regex_replace is a strange case for this list because it's not really meant to be an algorithm. However, the regular expression can be considered a kind of predicated in exactly the same way as the Searcher of search (C++17) can be, and the actual operation performed is a kind of conditional two-input copy, in a similar way as set_intersection et al. are, but with the conditionality being somewhat more like unique_copy in that it relates to the relationship between nearby elements instead of their individual values. Another unusual thing is that it can return its output as a string by value, in addition to writing to an output iterator. Despite that, I'm considering it an anamorphism because its output is a range of the same kind as its input, even if it is represented in the language as a value type, unlike those catamorphisms which can be used to return ranges, but which, for analytical purposes, return values. I wrote a more generic search_replace_copy, which is a much more normal entry for this list.

Top

Acknowledgements

This page would not exist without Conor Hoekstra's two-part talk "Algorithm Intuition" (CppCon 2019, parts one and two) to inspire me and provide the basic framework for me to expand upon. Jonathan Boccara's talk "105 STL Algorithms in Less Than an Hour" (CppCon 2018) was also very helpful for me in framing this work.

These presentations themselves reference excellent presentations by Sean Parent ("C++ Seasoning", GoingNative 2013), Marshall Clow ("STL Algorithms - why you should use them, and how to write your own", CppCon 2016), and Kate Gregory ("It's Complicated", Meeting C++ 2017 Keynote, "Simplicity: not just for beginners", ACCU 2018, and her appearance on CppCast, episode 30, "Stop Teaching C (When Teaching C++)").

Top