One way of categorizing the algorithms is by the types of iterators that they take as arguments, or return as results.
Let’s start with a reminder of the hierarchy of iterators (I am deliberately ignoring some of the new iterator functionality being proposed for C++17):
| Random access iterator | |
| Bidirectional iterator | |
| Forward iterator | |
| Input iterator | Output iterator |
The key quality of an input iterator is that the input sequence can only be traversed once. We can make a copy of an input iterator, but the moment we increment one of the copies, the other becomes invalid. The input value is available once – a common example is reading in keys from a keyboard.
An output iterator will only let us write a value once. An example is writing a value to a stream that’s being sent over the network (this example ignores a bunch of details likely to apply in practice but that doesn’t stop it from being a useful reminder for me).
A forward iterator lets us read or write as many times as we want. We can make copies of the iterator and traverse the sequence as many times as we want but we can only traverse it in one direction – forward. The classic example is a singly linked list.
A bidirectional iterator has all of the qualities of a forward iterator but will let us traverse backwards as well as forwards – e.g. a doubly linked list.
Finally, a random access iterator will let us traverse forwards, backwards and additionally, jump to any point in the sequence. std::vector lets us do all of this.
Input iterator
There are lots of algorithms that take input iterators as arguments so I have subdivided them further by their return type. Let’s start off with the algorithms that do not return an iterator:
| T | accumulate | (InputIterator, InputIterator, T) |
| T | accumulate | (InputIterator, InputIterator, T, BinaryOperation) |
| bool | all_of | (InputIterator, InputIterator, Predicate) |
| bool | any_of | (InputIterator, InputIterator, Predicate) |
| difference_type | count | (InputIterator, InputIterator, T) |
| difference_type | count_if | (InputIterator, InputIterator, Predicate) |
| bool | equal | (InputIterator1, InputIterator1, InputIterator2) |
| bool | equal | (InputIterator1, InputIterator1, InputIterator2, BinaryPredicate) |
| Function | for_each | (InputIterator, InputIterator, Function) |
| bool | includes | (InputIterator1, InputIterator1, InputIterator2, InputIterator2) |
| bool | includes | (InputIterator1, InputIterator1, InputIterator2, InputIterator2, Compare) |
| T | inner_product | (InputIterator1, InputIterator1, InputIterator2, T) |
| T | inner_product | (InputIterator1, InputIterator1, InputIterator2, T, BinaryOperation1, BinaryOperation2) |
| bool | is_partitioned | (InputIterator, InputIterator, Predicate) |
| bool | lexicographical_compare | (InputIterator1, InputIterator1, InputIterator2, InputIterator2) |
| bool | lexicographical_compare | (InputIterator1, InputIterator1, InputIterator2, InputIterator2, Compare) |
| bool | none_of | (InputIterator, InputIterator, Predicate) |
We could subdivide this list even further. We have the algorithms that return bool – they are asking questions (all_of, any_of, equal, includes, is_partitioned, lexicographical_compare, none_of). We have the count and count_if algorithms – also asking questions and getting back an answer in the form of an integer. There are the algorithms that return a single value computed from the input range (accumulate and inner_product) and finally, for_each which, because it allows its function object to change state, returns the final version of the function object.
All of the algorithms can be run in a single pass over the input range – remember that input iterators do not allow us to iterate twice over a range. These algorithms can also be run over any pair of iterators above an input iterator in the hierarchy – i.e. all iterators except output iterators.
Next up, algorithms that take input iterators and return an output iterator:
| OutputIterator | adjacent_difference | (InputIterator, InputIterator, OutputIterator) |
| OutputIterator | adjacent_difference | (InputIterator, InputIterator, OutputIterator, BinaryOperation) |
| OutputIterator | copy | (InputIterator, InputIterator, OutputIterator) |
| OutputIterator | copy_if | (InputIterator, InputIterator, OutputIterator, Predicate) |
| OutputIterator | copy_n | (InputIterator, Size, OutputIterator) |
| OutputIterator | merge | (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator) |
| OutputIterator | merge | (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare) |
| OutputIterator | move | (InputIterator, InputIterator, OutputIterator) |
| OutputIterator | partial_sum | (InputIterator, InputIterator, OutputIterator) |
| OutputIterator | partial_sum | (InputIterator, InputIterator, OutputIterator, BinaryOperation) |
| pair<OutputIterator1, OutputIterator2> | partition_copy | (InputIterator, InputIterator, OutputIterator1, OutputIterator2, Predicate) |
| OutputIterator | remove_copy | (InputIterator, InputIterator, OutputIterator, T) |
| OutputIterator | remove_copy_if | (InputIterator, InputIterator, OutputIterator, Predicate) |
| OutputIterator | replace_copy | (InputIterator, InputIterator, OutputIterator, T, T) |
| OutputIterator | replace_copy_if | (InputIterator, InputIterator, OutputIterator, Predicate, T) |
| OutputIterator | set_difference | (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator) |
| OutputIterator | set_difference | (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare) |
| OutputIterator | set_intersection | (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator) |
| OutputIterator | set_intersection | (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare) |
| OutputIterator | set_symmetric_difference | (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator) |
| OutputIterator | set_symmetric_difference | (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare) |
| OutputIterator | set_union | (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator) |
| OutputIterator | set_union | (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare) |
| OutputIterator | transform | (InputIterator, InputIterator, OutputIterator, UnaryOperation) |
| OutputIterator | transform | (InputIterator1, InputIterator1, InputIterator2, OutputIterator, UnaryOperation) |
| OutputIterator | unique_copy | (InputIterator, InputIterator, OutputIterator) |
| OutputIterator | unique_copy | (InputIterator, InputIterator, OutputIterator, BinaryPredicate) |
The algorithms that return an output iterator all take an output iterator as a parameter. The algorithms are taking an input range and converting it to an output range. The result is always the position after the last written element of the output range – i.e. the first element that was not overwritten.
Alex Stepanov had many design principles for the STL. One of them states that an algorithm that calculates a useful value should return that value even when the calculation of that value is not the main point of the algorithm. Take std::copy. The programmer already knows where the beginning and end of the input range are, and where the beginning of the output range is. What the programmer does not necessarily know is where the end of the output range is. Since the algorithm computes the end of the output range, and it is potentially useful information (I’ve used it several times), the algorithm returns the end of the output range.
As well as straightforward copying we also get variants on std::copy : std::copy, std::copy_if, std::copy_n, std::remove_copy, std::remove_copy_if, std::partition_copy (note that std::remove, std::remove_if and std::partition need more powerful iterators – it is the copying which lets them work with input iterators).
We also get std::merge – a building block for merge sort algorithms.
Finally for the input iterators, we have the algorithms that return an input iterator.
| InputIterator | find | (InputIterator, InputIterator, T) |
| InputIterator | find_first_of | (InputIterator, InputIterator, ForwardIterator, ForwardIterator) |
| InputIterator | find_first_of | (InputIterator, InputIterator, ForwardIterator, ForwardIterator, BinaryPredicate) |
| InputIterator | find_if | (InputIterator, InputIterator, Predicate) |
| InputIterator | find_if_not | (InputIterator, InputIterator, Predicate) |
| pair<InputIterator1, InputIterator2> | mismatch | (InputIterator1, InputIterator1, InputIterator2) |
| pair<InputIterator1, InputIterator2> | mismatch | (InputIterator1, InputIterator1, InputIterator2, BinaryPredicate) |
All of the algorithms return the position of something that was found, whether that was a given value or a mismatch.
Remember that an input iterator only gets to iterate over a range once. Once we have read a value and moved on that value is gone, however an algorithm like std::find only needs to read that value, it does not need to move on before returning the iterator.
Output iterator
There are only a couple of algorithms that take no iterators other than output iterators. Unsurprisingly, these are algorithms that generate some output:
| OutputIterator | fill_n | (OutputIterator, Size, T) |
| OutputIterator | generate_n | (OutputIterator, Size, Generator) |
There are other variants of std::fill and std::generate which we’ll look at later. These two algorithms write a sequence of n values. They are useful because we don’t always have the option of getting an “end” output iterator. Imagine appending data to a file, the end is wherever we decide to stop writing – there is no predetermined “end”.
In a previous blog post I mentioned the idea of adding iota_n. This is the category that iota_n would fit into. Incidentally, the boost algorithms library has boost::iota_n available, along with many other useful algorithms.
Forward iterator
| ForwardIterator | adjacent_find | (ForwardIterator, ForwardIterator) |
| ForwardIterator | adjacent_find | (ForwardIterator, ForwardIterator, BinaryPredicate) |
| bool | binary_search | (ForwardIterator, ForwardIterator, T) |
| bool | binary_search | (ForwardIterator, ForwardIterator, T, Compare) |
| pair<ForwardIterator, ForwardIterator> | equal_range | (ForwardIterator, ForwardIterator, T) |
| pair<ForwardIterator, ForwardIterator> | equal_range | (ForwardIterator, ForwardIterator, T, Compare) |
| void | fill | (ForwardIterator, ForwardIterator, T) |
| ForwardIterator1 | find_end | (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2) |
| ForwardIterator1 | find_end | (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, BinaryPredicate) |
| void | generate | (ForwardIterator, ForwardIterator, Generator) |
| void | iota | (ForwardIterator, ForwardIterator, T) |
| bool | is_permutation | (ForwardIterator1, ForwardIterator1, ForwardIterator2) |
| bool | is_permutation | (ForwardIterator1, ForwardIterator1, ForwardIterator2, BinaryPredicate) |
| bool | is_sorted | (ForwardIterator, ForwardIterator) |
| bool | is_sorted | (ForwardIterator, ForwardIterator, Compare) |
| bool | is_sorted_until | (ForwardIterator, ForwardIterator) |
| bool | is_sorted_until | (ForwardIterator, ForwardIterator, Compare) |
| void | iter_swap | (ForwardIterator1, ForwardIterator2) |
| ForwardIterator | lower_bound | (ForwardIterator, ForwardIterator, T) |
| ForwardIterator | lower_bound | (ForwardIterator, ForwardIterator, T, Compare) |
| ForwardIterator | max_element | (ForwardIterator, ForwardIterator) |
| ForwardIterator | max_element | (ForwardIterator, ForwardIterator, Compare) |
| ForwardIterator | min_element | (ForwardIterator, ForwardIterator) |
| ForwardIterator | min_element | (ForwardIterator, ForwardIterator, Compare) |
| pair<ForwardIterator, ForwardIterator> | minmax_element | (ForwardIterator, ForwardIterator) |
| pair<ForwardIterator, ForwardIterator> | minmax_element | (ForwardIterator, ForwardIterator, Compare) |
| ForwardIterator | partition | (ForwardIterator, ForwardIterator, Predicate) |
| ForwardIterator | partition_point | (ForwardIterator, ForwardIterator, Predicate) |
| ForwardIterator | remove | (ForwardIterator, ForwardIterator, T) |
| ForwardIterator | remove_if | (ForwardIterator, ForwardIterator, Predicate) |
| void | replace | (ForwardIterator, ForwardIterator, T, T) |
| void | replace_if | (ForwardIterator, ForwardIterator, Predicate, T) |
| ForwardIterator | rotate | (ForwardIterator, ForwardIterator, ForwardIterator) |
| OutputIterator | rotate_copy | (ForwardIterator, ForwardIterator, ForwardIterator, OutputIterator) |
| ForwardIterator1 | search | (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2) |
| ForwardIterator1 | search | (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, BinaryPredicate) |
| ForwardIterator | search_n | (ForwardIterator, ForwardIterator, Size, T) |
| ForwardIterator | search_n | (ForwardIterator, ForwardIterator, Size, T, BinaryPredicate) |
| ForwardIterator2 | swap_ranges | (ForwardIterator1, ForwardIterator1, ForwardIterator2) |
| ForwardIterator | unique | (ForwardIterator, ForwardIterator) |
| ForwardIterator | unique | (ForwardIterator, ForwardIterator, BinaryPredicate) |
| ForwardIterator | upper_bound | (ForwardIterator, ForwardIterator, T) |
| ForwardIterator | upper_bound | (ForwardIterator, ForwardIterator, T, Compare) |
Forward iterators give us a lot more options. Since forward iterators can iterate over a range more than once we can handle algorithms such as std::adjacent_find which require us to iterate over each value twice.
As I promised earlier, we have the other variants of std::generate and std::fill here, and we also get std::iota. Now we have moved into forward iterators we can start dealing with output ranges.
One suprise is that std::binary_search, std::equal_range, std::lower_bound and std::upper_bound are present in this list. We normally think of these algorithms as being O(log n) algorithms. Surely we cannot have a O(log n) algorithm working with forward iterators since the algorithm might have to iterate over the entire sequence making it O(n). The reason they are available for forward iterators is because the standard defines their complexity requirements as O(log n) on the number of comparisons, not the number of elements iterated over. We might regard this as cheating.
We are not stuck with one implementation of an algorithm though. There is also a great talk by Stephan T. Lavavej here where he explains how an implementation can select different algorithms for different iterator types so (for example) std::binary_search can use one implementation for forward iterators but a more efficient implementation for random access iterators.
Another surprise for me is that std::min_element, std::max_element and std::minmax_element all require forward iterators. Surely it is possible to find the maximum element of a sequence using input iterators? Well, it is possible to find the maximum element of a sequence using input iterators, however there are two problems:
- std::max_element and friends actually return the position of the desired element(s), not just the value of the desired element. The position is a more general piece of information
- If we had a version of std::max_element that ran on input iterators it would have to make a copy of the element – both for the comparison and to return the value of the element. Making a copy could be expensive, undesirable or impossible. Having said that, there is a Stack Overflow post here where making a copy increases the performance of the algorithm, probably due to a cache effect.
Working out how to implement some of these algorithms to achieve the required complexity guarantees is an interesting exercise.
Bidirectional iterator
| BidirectionalIterator2 | copy_backward | (BidirectionalIterator1, BidirectionalIterator1, BidirectionalIterator2) |
| void | inplace_merge | (BidirectionalIterator, BidirectionalIterator, BidirectionalIterator) |
| void | inplace_merge | (BidirectionalIterator, BidirectionalIterator, BidirectionalIterator, Compare) |
| BidirectionalIterator2 | move_backward | (BidirectionalIterator1, BidirectionalIterator1, BidirectionalIterator2) |
| bool | next_permutation | (BidirectionalIterator, BidirectionalIterator) |
| bool | next_permutation | (BidirectionalIterator, BidirectionalIterator, Compare) |
| bool | prev_permutation | (BidirectionalIterator, BidirectionalIterator) |
| bool | prev_permutation | (BidirectionalIterator, BidirectionalIterator, Compare) |
| void | reverse | (BidirectionalIterator, BidirectionalIterator) |
| OutputIterator | reverse_copy | (BidirectionalIterator, BidirectionalIterator, OutputIterator) |
| BidirectionalIterator | stable_partition | (BidirectionalIterator, BidirectionalIterator, Predicate) |
The bidirectional iterator algorithms are an interesting bunch. The algorithms need more functionality than provided by forward iterators, but don’t require the full power of random access iterators.
We get std::copy_backward. As we saw in part 1a, std::copy and std::copy_backward handle overlapping ranges (std::reverse_copy requires non-overlapping ranges). If you’re looking from some additional amusement, look into how using reverse iterators affects the overlapping range guarantees of std::copy and std::copy_backward (we can make similar arguments for the std::move set of algorithms).
We get std::inplace_merge, an algorithm that will make use of extra memory if it can get it. The standard does not specify where the extra memory comes from – usually C++ allows you to handle all memory via custom allocators, that does not appear to be the case here.
Random access iterator
| bool | is_heap | (RandomAccessIterator, RandomAccessIterator) |
| bool | is_heap | (RandomAccessIterator, RandomAccessIterator, Compare) |
| RandomAccessIterator | is_heap_until | (RandomAccessIterator, RandomAccessIterator) |
| RandomAccessIterator | is_heap_until | (RandomAccessIterator, RandomAccessIterator, Compare) |
| void | make_heap | (RandomAccessIterator, RandomAccessIterator) |
| void | make_heap | (RandomAccessIterator, RandomAccessIterator, Compare) |
| void | nth_element | (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator) |
| void | nth_element | (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator, Compare) |
| void | partial_sort | (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator) |
| void | partial_sort | (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator, Compare) |
| void | pop_heap | (RandomAccessIterator, RandomAccessIterator) |
| void | pop_heap | (RandomAccessIterator, RandomAccessIterator, Compare) |
| void | push_heap | (RandomAccessIterator, RandomAccessIterator) |
| void | push_heap | (RandomAccessIterator, RandomAccessIterator, Compare) |
| void | random_shuffle | (RandomAccessIterator, RandomAccessIterator) |
| void | random_shuffle | (RandomAccessIterator, RandomAccessIterator, RandomNumberGenerator) |
| void | shuffle | (RandomAccessIterator, RandomAccessIterator, URandomNumberGenerator) |
| void | sort | (RandomAccessIterator, RandomAccessIterator) |
| void | sort | (RandomAccessIterator, RandomAccessIterator, Compare) |
| void | sort_heap | (RandomAccessIterator, RandomAccessIterator) |
| void | sort_heap | (RandomAccessIterator, RandomAccessIterator, Compare) |
| void | stable_sort | (RandomAccessIterator, RandomAccessIterator) |
| void | stable_sort | (RandomAccessIterator, RandomAccessIterator, Compare) |
The random access algorithms are all about sorting and shuffling. I have rarely used the heap algorithms directly but they are useful building blocks for algorithms such as std::nth_element (previously discussed here), std::partial_sort_copy and std::partial_sort.
Input iterator and random access iterator
| RandomAccessIterator | partial_sort_copy | (InputIterator, InputIterator, RandomAccessIterator, RandomAccessIterator) |
| RandomAccessIterator | partial_sort_copy | (InputIterator, InputIterator, RandomAccessIterator, RandomAccessIterator, Compare) |
std::partial_sort_copy uses an interesting combination of input iterators and random access iterators.
No iterator
| const T& | max | (T, T) |
| const T& | max | (T, T, Compare) |
| T | max | (InitializerList) |
| T | max | (InitializerList, Compare) |
| const T& | min | (T, T) |
| const T& | min | (T, T, Compare) |
| T | min | (InitializerList) |
| T | min | (InitializerList, Compare) |
| pair<const T&, const T&> | minmax | (T, T) |
| pair<const T&, const T&> | minmax | (T, T, Compare) |
| pair<T, T> | minmax | (InitializerList) |
| pair<T, T> | minmax | (InitializerList, Compare) |
Finally, there are the core min and max algorithms that don’t use iterators at all.
Conclusion
I don’t have a conclusion for this post. I found it interesting to see which algorithms required which iterators – there were a couple that surprised me. The general rule is to write algorithms that use the weakest iterators possible to make the algorithms as widely useful as possible.