quant_dev quant_dev - 1 month ago 7
C++ Question

Which STL algorithms are safe to use with single-pass input iterators?

Which or what kind of STL algorithms are safe to use in a standard-compliant STL implementation?

In other words: which or what kind STL algorithms are required by the standard to be single-pass?

If the exhaustive list would be too long, a way to identify those which are safe is also OK.

Answer

Algorithms which operate on InputIterators and OutputIterators may by contract rely only on a single pass through the range they operate over.

From cppreference1:

On InputIterators:

An InputIterator is an Iterator that can read from the pointed-to element. InputIterators only guarantee validity for single pass algorithms: once an InputIterator i has been incremented, all copies of its previous value may be invalidated.

and on OutputIterators

Assignment through the same value of an output iterator happens only once: algorithms on output iterators must be single-pass algorithms.


This is a list of those algorithms which have arguments of InputIterator and OutputIterator:

added in C++17:

Interestingly, there are three algorithms not on this list that one might expect: max_element, min_element and minmax_element are the standard's algorithms for finding the maximum, minimum and both the minimum and maximum value of a range. One might expect them to iterate over their given range only a single time, and thus require InputIterator arguments. Instead, they require ForwardIterator arguments, because rather than returning the value of the chosen element, they return an iterator to it. Since this violates the single pass requirement of an InputIterator, these algorithms are naturally left with a ForwardIterator.


1. cppreference is backed on both counts by the standard (n4140 draft).

§24.2.3 [input.iterators] states that after ++r where r is the input iterator, "any copies of the previous value of r are no longer required either to be dereferenceable or to be in the domain of =="

§24.2.4 [output.iterators] states for both the expressions *r = o and *r++ = o "After this operation r is not required to be dereferenceable."

Both sections contain notes that mention that the iterator in question is safe for single pass ranges, stating that "Algorithms on (input|output) iterators should never attempt to pass through the same iterator twice. They should be single pass algorithms." Of course, notes aren't binding.

Comments