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. If you want to link to a specific row in the table, you can click the ^# in the upper-left corner of that row's name column.

The source code and data I used to generate this table (not including the source for this page itself) is located here. The PHP code I used to transclude the generated tables into this page is available here.

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. Occasionally, I may add algorithms specified in C++ standard proposals, which will be indicated in orange. 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.

Where kblib provides an alternate definition of a standard library algorithm, usually only the standard algorithm is shown, unless the two differ in some significant way. For minor differences, which affect only one or two columns, two values may be shown, with the kblib version colored green.

Show entries from kblib

Show entries described by Conor

Show entries from C++ standardization proposals

Home

Catamorphisms (folds) and Searches

Name	Input ranges*	Accumulator	Returns⌖	Operations†	Default operations	Complexity	Order‡	Compare to	Family
^# `inner_product`	2↓I	Arg	Value	A, bT	`plus`, `multiplies`	Unspc.	Fwd.	`transform_reduce`	10
^# `adjacent_reduce`▸	1s↓F	Arg	Value	A, bT		Unspc.	Fwd.	`inner_product`	10
^# `transform_reduce`	1↓I,∥F / 2↓I,∥F	Arg	Value	acR, uT / bT	`plus`, `multiplies`	O(N)	∥		20
^# `find`	1↓I,∥F+Value		Position		`equal_to`	O(N)	S/C, ∥		70
^# `find_if`, `find_if_not`	1↓I,∥F		Position	uP		O(N)	S/C, ∥		70
^# `find_first_of`	1↓I,∥F + 1↓F		Position	bP	`equal_to`	O(S×N)	S/C, ∥	`find_if`	70
^# `min_element`, `max_element`	1↓F	First	Position	bP	`less`	O(N), =(max(N-1, 0))	Fwd., ∥		72
^# `minmax_element`	1↓F	First	2 Positions⌖	bP	`less`	O(N), ≤(max(floor((3/2)*(N−1)), 0))	Fwd., ∥		72
^# `lower_bound`, `upper_bound`	1↓F+Value		Position	bP	`less`	O(log N) + O(1)↓R; O(N)	B/S		75
^# `equal_range`	1↓F+Value		Range⌖	bP	`less`	O(log N) + O(1)↓R; O(N)	B/S		75
^# `search`	2↓F		Position	bP	`equal_to`	≤(S×N)	∥		80
^# `find_end`	2↓F		Position	bP	`equal_to`	≤(S×(N-S+1))	∥	`search`	80
^# `starts_with`	2↓F		`bool`	bP	`equal_to`	N > S ? O(S) : O(1)↓R; O(min(S, N))↓F	Fwd.		80
^# `ends_with`	2↓B		`bool`	bP	`equal_to`	N > S ? O(S) : O(1)↓R; O(min(S, N))↓B			80
^# `ranges::starts_with`	2↓I		`bool`	bP, uT, uTΔ	`equal_to`, `identity`, `identity`	≤(min(S, N))			80
^# `ranges::ends_with`	2↓F		`bool`	bP, uT, uTΔ	`equal_to`, `identity`, `identity`	≤(min(S, N))			80
^# `search (C++17)`	1↓F		Position	Searcher		Depends on Searcher			85
^# `find_match`	2↓I		Position⌖	bP	`equal_to`	O(N), O(min(N, M))	S/C		90
^# `mismatch`	2↓I,∥F		Position⌖	bP	`equal_to`	O(N), O(min(N, M))	S/C, ∥	`find_match`	90
^# `adjacent_find`	1s↓F		Position	bP	`equal_to`	=(min((result-first)+1, (last-first)-1)); O(N)↓∥	S/C, ∥	`find_match`	90
^# `is_sorted_until`	1s↓F		Position	bP	`less`	O(N)	S/C, ∥	`find_match`	90
^# `search_n`	1↓F + Count + Value		Position	bP	`equal_to`	≤(N)	∥	`adjacent_find`	95
^# `accumulate`	1↓I	Arg	Value	A	`plus`	Unspc.; O(N)	Fwd.		110
^# `sum`	1↓I	First	Value	R	`plus`	O(N)	Fwd.	`accumulate`	110
^# `reduce`	1↓I,∥F	Arg	Value	acR	`plus`	O(N)	∥		110
^# `count`	1↓I,∥F+Value	`0`	`size_t`		`equal_to`	=(N)	Fwd., ∥	`accumulate`	110
^# `count_if`	1↓I,∥F	`0`	`size_t`	uP		=(N)	Fwd., ∥	`accumulate`	110
^# `binary_search`	1↓F+Value		`bool`	bP	`less`	O(log N) + O(1)↓R; O(N)	B/S		110
^# `is_partitioned`	1↓I,∥F		`bool`	uP		O(N)	Fwd., ∥		120
^# `is_sorted`	1↓F		`bool`	bP	`less`	O(N)	Fwd., ∥		120
^# `is_heap`	1↓R		`bool`	bP	`less`	O(N)	∥		120
^# `is_permutation`	2↓F		`bool`	bP	`equal_to`	N==M ? O(N²) : O(1)↓R; O(N²)			120
^# `includes`	2↓I,∥F		`bool`	bP	`less`	O(N+M), ≤(2×(N+M-1))	Fwd., ∥		120
^# `first_result`	1↓I+Value / 2↓I+Value	Arg	Value	uT / bT		O(N)	S/C		125
^# `first_result_if`	1↓I / 2↓I		Value	uT / bT, uP / bP		O(N)	S/C		125
^# `all_of`, `none_of`	1↓I,∥F	`true`	`bool`	uP		O(N)	S/C, ∥	`first_result`	125
^# `any_of`	1↓I,∥F	`false`	`bool`	uP		O(N)	S/C, ∥	`first_result`	125
^# `contains`	1↓I+Value	`false`	`bool`		`equal_to`	O(N)	S/C	`first_result`	125
^# `contains_any`	2↓I	`false`	`bool`		`contains`	O(S×N)	S/C	`first_result`	125
^# `equal`	2↓I,∥F		`bool`	bP	`equal_to`	N==M ? ≤(N) : O(1)↓R; ≤(N); O(N)↓∥	Fwd., ∥	`first_result`	125
^# `lexicographical_compare`	2↓I,∥F		`bool`	bP	`less`	≤(2×min(N, M))	Fwd., ∥	`first_result`	125
^# `lexicographical_compare_three_way`	2↓I		ordering	CompareΔ	`compare_three_way`	<(min(N, M))	Fwd.	`first_result`	125
^# `partition_point`	1↓F		Position	uP		O(log N)↓R; O(N)	B/S		130
^# `is_heap_until`	1↓R		Position	bP	`less`	O(N)	∥		130
Name	Input ranges*	Accumulator	Returns⌖	Operations†	Default operations	Complexity	Order‡	Compare to	Family

Top

Anamorphisms (unfolds/transforms)

Name	Input ranges*	Accumulator	Output ranges	Operations†	Default operations	Complexity	Order‡	Compare to	Family
^# `transform_inclusive_scan`	1↓I,∥F	First, Arg	1↓O,∥F	aR, uT		O(N)	∥		20
^# `transform_exclusive_scan`	1↓I,∥F	Arg	1↓O,∥F	aR, uT		O(N)	∥		20
^# `partial_sum`	1↓I	First	1↓O	A	`plus`	O(N), =(N - 1)	Fwd.		30
^# `inclusive_scan`	1↓I,∥F	First, Arg	1↓O,∥F	aR	`plus`	O(N)	∥		30
^# `exclusive_scan`	1↓I,∥F	Arg	1↓O,∥F	aR	`plus`	O(N)	∥		30
^# `adjacent_difference`	1s↓I,∥F	Quasi	1↓O,∥F	fD	`minus`	O(N), =(N - 1)	Fwd., ∥	`adjacent_transform`	40
^# `adjacent_transform`▸	1s↓I	Quasi	1↓O	D		O(N), =(N - 1)	Fwd., ∥	`adjacent_difference`	40
^# `adjacent_inclusive_scan`▸	1s↓I	First	1↓O	A, D		O(N)	Fwd.		50
^# `transform`	1↓I,∥F / 2↓I,∥F		1↓O,∥F	uT / bT		=(N)	∥		60
^# `copy`	1↓I,∥F		1↓O,∥F			=(N)	Fwd., ∥	`transform`	60
^# `copy_backward`	1↓B		1↓B			=(N)	Rev.		60
^# `copy_n`	1↓I,∥F		1↓O,∥F			=(N)	Unspc., ∥	`transform`	60
^# `replace_copy`	1↓I,∥F+Value	Arg	1↓O,∥F		`equal_to`	=(N)	Fwd., ∥	`transform`	60
^# `replace_copy_if`	1↓I,∥F	Arg	1↓O,∥F	uP		=(N)	Fwd., ∥	`transform`	60
^# `reverse_copy`	1↓B		1↓O,∥F			=(N)	∥	`transform`	60
^# `rotate_copy`	1d↓F		1↓O,∥F			O(N)	∥		60
^# `move (algorithm)`	1↓I,∥F		1↓O,∥F			=(N)	Fwd., ∥	`shift_left`	65
^# `move_backward`	1↓B		1↓B			=(N)	Rev.	`shift_right`	65
^# `shift_left`	1d↓F		Self			"≤(N-n)"	Fwd., ∥	`move (algorithm)`	67
^# `shift_right`	1d↓F(swap),B		Self			"≤(N-n)"	Yes, ∥	`move_backward`	67
^# `sample`	1↓F	Arg(URBG)	1↓O+Size			O(N)	Fwd.		70
^# `sample`Ⓢ	1↓I	Arg(URBG)	1↓R+Size			O(N)	Fwd.		70
^# `partial_sort_copy`	1↓I,∥F		1↓R	bP	`less`	O(N log(min(D,N))	∥		70
^# `partition_copy`	1↓I,∥F		2↓O,∥F	uP		=(N)	Fwd., ∥		73
^# `transform_if`	1↓I		1↓O	uP, uT		O(N)	Fwd.		75
^# `copy_if`, `remove_copy_if`	1↓I,∥F		1↓O,∥F	uP		O(N)	Fwd., ∥	`transform_if`	75
^# `remove_copy`	1↓I,∥F+Value		1↓O,∥F		`equal_to`	=(N)	Fwd., ∥	`transform_if`	75
^# `unique_copy`	1↓I,∥F	First	1↓O,∥F	bP	`equal_to`	O(N)	Fwd., ∥		75
^# `set_difference`, `set_intersection`, `set_symmetric_difference`, `set_union`	2↓I,∥F		1↓O,∥F	bP	`less`	O(N+M), ≤(2⋅(N+M)−1)	Fwd., ∥		77
^# `merge`	2↓I,∥F		1↓O,∥F	bP	`less`	O(N+M)	Fwd., ∥		77
^# `regex_replace`⧫	2↓B		1↓O	Regex⧫		Unspc.		See note⧫	78
^# `search_replace_copy`	3↓F		1↓O	bP	`equal_to`	O(N×(S+R))		`regex_replace`⧫	78
^# `generate`, `generate_n`	0		1↓F	G		=(N)	Fwd., ∥		100
^# `iota`	0	Arg	1↓F		`++`	=(N)	Fwd.	`generate`	100
^# `iota`	0	Arg	1↓F	uT	`++`	=(N)	Fwd.	`generate`	100
^# `fill`, `fill_n`	0	Arg	1↓F			=(N)	Fwd., ∥	`generate`, `generate_n`	100
^# `for_each`, `for_each_n`	1↓I,∥F		0∅	muT		=(N)	Fwd., ∥		140
^# `for_each`, `for_each_n`	1↓I / 2↓I		0∅	muT / mbT		=(N)	Fwd.		140
^# `swap_ranges`	2↓F		Self		`swap`	O(N)	Fwd., ∥	`for_each`	140
^# `remove`	1↓F+Value		Self		`equal_to`	O(N)	Fwd., ∥		150
^# `remove_if`	1↓F		Self	uP		O(N)	Fwd., ∥		150
^# `unique`	1↓F		Self	bP	`equal_to`	O(N)	Fwd., ∥		150
^# `replace`	1↓F+Value		Self		`equal_to`	=(N)	Fwd., ∥	`transform`	160
^# `replace_if`	1↓F		Self	uP		=(N)	Fwd., ∥	`transform`	160
^# `reverse`	1↓B		Self			O(N), =(N/2)	Yes, ∥	`swap_ranges`	170
^# `rotate`	1d↓F		Self			O(N)	Yes, ∥		170
^# `shuffle`	1↓R	Acc(URBG)	Self			O(N)			170
^# `next_permutation`, `prev_permutation`	1↓B		Self			O(N), ≤(N/2)			170
^# `partition`	1↓F		Self	uP		O(N); O(N log N)↓∥	∥		170
^# `stable_partition`	1↓B		Self	uP		O(N) w/ memory, else O(N log N); O(N log N)↓∥	∥		170
^# `sort`	1↓R		Self	bP	`less`	O(N log N)	∥		170
^# `partial_sort`	1d↓R		Self	bP	`less`	O(N log M)	∥		170
^# `stable_sort`	1↓R		Self	bP	`less`	O(N log N) w/ memory, else O(N log(N)²)	∥		170
^# `nth_element`	1d↓R		Self	bP	`less`	O(N); O(N log N)↓∥	∥		170
^# `nth_elements, multi_nth_element`	1↓R+positions↓R		Self	bP	`less`	O(N log M)		`nth_element`	170
^# `make_heap`	1↓R		Self	bP	`less`	O(N), ≤(3N)			170
^# `push_heap`, `pop_heap`	1↓R		Self	bP	`less`	O(log N)			170
^# `sort_heap`	1↓R		Self	bP	`less`	O(N log N)			170
^# `inplace_merge`	1d↓B		Self	bP	`less`	=(N-1) w/ memory, O(N log N); O(N log N)↓∥	∥		170
Name	Input ranges*	Accumulator	Output ranges	Operations†	Default operations	Complexity	Order‡	Compare to	Family

Top

Named Operators and Function Objects

Name	Arity	Class (<T>)	Signature (<T>)	Class (<void>)	Definition
`plus`	2	(ac)R	`(T, T) → T`	bT	`x + y`
`minus`	2	R	`(T, T) → T`	bT	`x - y`
`multiplies`	2	(ac)R	`(T, T) → T`	bT	`x * y`
`divides`	2	R	`(T, T) → T`	bT	`x / y`
`modulus`	2	R	`(T, T) → T`	bT	`x % y`
`negate`	1	uT	`(T) → T`	uT	`-x`
`equal_to`	2	(c)bP	`(T, T) → bool`	bT	`x == y`
`not_equal_to`	2	(c)bP	`(T, T) → bool`	bT	`x != y`
`less`	2	bP	`(T, T) → bool`	bT	`x < y`
`greater`	2	bP	`(T, T) → bool`	bT	`x > y`
`less_equal`	2	bP	`(T, T) → bool`	bT	`x <= y`
`greater_equal`	2	bP	`(T, T) → bool`	bT	`x >= y`
`logical_and`	2	(c)bP	`(T, T) → bool`	bT	`x and y`
`logical_or`	2	(c)bP	`(T, T) → bool`	bT	`x or y`
`logical_not`	1	uP	`(T) → bool`	uT	`not x`
`bit_and`	2	(ac)R	`(T, T) → T`	bT	`x & y`
`bit_or`	2	(ac)R	`(T, T) → T`	bT	`x \| y`
`bit_xor`	2	(ac)R	`(T, T) → T`	bT	`x ^ y`
`bit_not`	1	uT	`(T) → T`	uT	`~x`
Name	Arity	Class (<T>)	Signature (<T>)	Class (<void>)	Definition

Top

Footnotes

*'s' indicates staggered access to a range. 'd' indicates that a second position in the range is also required. Ranges are also annotated with iterator/range concepts, see below †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. ∥Several algorithms have parallel versions in C++17. The ∥ mark may be used in any column to indicate that a given value only pertains to the parallel version, however, in the "Order" column, it is a value by itself, see next note. ‡A blank space in the "Order" column 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; in this case, the order value preceding it applies to the sequential version of the algorithm. ↓Several algorithms are defined to have different characteristics for different iterator concepts, such as between random access and others, or between forward and input iterators, or anything else. For such algorithms, the value is marked with an arrow followed by a letter, indicating which iterator category that value applies to. The letter codes are: C for contiguous, R for Random Access, B for Bidirectional, F for Forward, I for Input, and O for Output. Note that Output is an orthogonal category. Additionally, the ∥ mark indicates that the given value applies to the parallel version of the algorithm. Δ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. Ⓢsample is listed twice because the requirements on its input and output ranges are complementary, thus effectively providing two overloads.

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