Algorithms and variations 2

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:

  1. 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
  2. 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.

One thought on “Algorithms and variations 2

  1. John Payson says:

    I like your point about functions returning useful values. It’s an interesting contrast with many routines from the C Standard Library which have major semantic weaknesses as a result of poor return-value choices. A well-designed library to facilitate string concatenation would make it possible to efficiently say:

    char *p = target_buffer;
    char *buff_end = target_buffer + TARGET_LENGTH;
    /* Hypothetical method:
    strrcpy(char *dest, char const *dest_limit, char const *src); */
    *p = strrcpy(p, buff_end, string1);
    *p = strrcpy(p, buff_end, string2);
    *p = strrcpy(p, buff_end, string3);

    to copy as much of string1 as will fit, as much of string2 as will fit in the space that’s left, etc. without risking an overrun of the target buffer, and without having to redundantly scan anything. Unfortunately, strcpy(), nor strcat(), and other similar library functions return a useless pointer to the start of the destination, even though in many cases returning a useless copy of the passed-in pointer will entail more work than would have been necessary to return something useful. Worse, strncat() requires that code which presumably doesn’t know how much data is already in the destination buffer [code which did know would have no reason to pass a pointer to the start of the destination string rather than the end] to somehow know how much space remains.

    It’s nice to see examples of places where return values were given some useful consideration.

Leave a Reply

Your email address will not be published.