25 Iterators library [iterators]

25.4 Iterator primitives [iterator.primitives]

25.4.1 General [iterator.primitives.general]

1
#
To simplify the use of iterators, the library provides several classes and functions.

25.4.2 Standard iterator tags [std.iterator.tags]

1
#
It is often desirable for a function template specialization to find out what is the most specific category of its iterator argument, so that the function can select the most efficient algorithm at compile time.
To facilitate this, the library introduces category tag classes which are used as compile time tags for algorithm selection.
They are: output_iterator_tag, input_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, random_access_iterator_tag, and contiguous_iterator_tag.
For every iterator of type I, iterator_traits<I>​::​iterator_category shall be defined to be a category tag that describes the iterator's behavior.
Additionally, iterator_traits<I>​::​iterator_concept may be used to indicate conformance to the iterator concepts ([iterator.concepts]).
namespace std { struct output_iterator_tag { }; struct input_iterator_tag { }; struct forward_iterator_tag: public input_iterator_tag { }; struct bidirectional_iterator_tag: public forward_iterator_tag { }; struct random_access_iterator_tag: public bidirectional_iterator_tag { }; struct contiguous_iterator_tag: public random_access_iterator_tag { }; }
2
#
[Example 1: 
A program-defined iterator BinaryTreeIterator can be included into the bidirectional iterator category by specializing the iterator_traits template: template<class T> struct iterator_traits<BinaryTreeIterator<T>> { using iterator_category = bidirectional_iterator_tag; using difference_type = ptrdiff_t; using value_type = T; using pointer = T*; using reference = T&; };
— end example]
3
#
[Example 2: 
If evolve() is well-defined for bidirectional iterators, but can be implemented more efficiently for random access iterators, then the implementation is as follows: template<class BidirectionalIterator> inline void evolve(BidirectionalIterator first, BidirectionalIterator last) { evolve(first, last, typename iterator_traits<BidirectionalIterator>::iterator_category()); } template<class BidirectionalIterator> void evolve(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag) { // more generic, but less efficient algorithm } template<class RandomAccessIterator> void evolve(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) { // more efficient, but less generic algorithm }
— end example]

25.4.3 Iterator operations [iterator.operations]

1
#
Since only random access iterators provide + and - operators, the library provides two function templates advance and distance.
These function templates use + and - for random access iterators (and are, therefore, constant time for them); for input, forward and bidirectional iterators they use ++ to provide linear time implementations.
🔗
template<class InputIterator, class Distance> constexpr void advance(InputIterator& i, Distance n);
2
#
Preconditions: n is negative only for bidirectional iterators.
3
#
Effects: Increments i by n if n is non-negative, and decrements i by -n otherwise.
🔗
template<class InputIterator> constexpr typename iterator_traits<InputIterator>::difference_type distance(InputIterator first, InputIterator last);
4
#
Preconditions: last is reachable from first, or InputIterator meets the Cpp17RandomAccessIterator requirements and first is reachable from last.
5
#
Effects: If InputIterator meets the Cpp17RandomAccessIterator requirements, returns (last - first); otherwise, increments first until last is reached and returns the number of increments.
🔗
template<class InputIterator> constexpr InputIterator next(InputIterator x, typename iterator_traits<InputIterator>::difference_type n = 1);
6
#
Effects: Equivalent to: advance(x, n); return x;
🔗
template<class BidirectionalIterator> constexpr BidirectionalIterator prev(BidirectionalIterator x, typename iterator_traits<BidirectionalIterator>::difference_type n = 1);
7
#
Effects: Equivalent to: advance(x, -n); return x;

25.4.4 Range iterator operations [range.iter.ops]

25.4.4.1 General [range.iter.ops.general]

1
#
The library includes the function templates ranges​::​advance, ranges​::​distance, ranges​::​next, and ranges​::​prev to manipulate iterators.
These operations adapt to the set of operators provided by each iterator category to provide the most efficient implementation possible for a concrete iterator type.
[Example 1: 
ranges​::​advance uses the + operator to move a random_access_iterator forward n steps in constant time.
For an iterator type that does not model random_access_iterator, ranges​::​advance instead performs n individual increments with the ++ operator.
— end example]
2
#
The function templates defined in [range.iter.ops] are not found by argument-dependent name lookup ([basic.lookup.argdep]).
When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a function call ([expr.call]), they inhibit argument-dependent name lookup.
[Example 2: void foo() { using namespace std::ranges; std::vector<int> vec{1,2,3}; distance(begin(vec), end(vec)); // #1 }
The function call expression at #1 invokes std​::​ranges​::​distance, not std​::​distance, despite that (a) the iterator type returned from begin(vec) and end(vec) may be associated with namespace std and (b) std​::​distance is more specialized ([temp.func.order]) than std​::​ranges​::​distance since the former requires its first two parameters to have the same type.
— end example]
3
#
The number and order of deducible template parameters for the function templates defined in [range.iter.ops] is unspecified, except where explicitly stated otherwise.

25.4.4.2 ranges​::​advance [range.iter.op.advance]

🔗
template<input_or_output_iterator I> constexpr void ranges::advance(I& i, iter_difference_t<I> n);
1
#
Preconditions: If I does not model bidirectional_iterator, n is not negative.
2
#
Effects:
🔗
template<input_or_output_iterator I, sentinel_for<I> S> constexpr void ranges::advance(I& i, S bound);
3
#
Preconditions: Either assignable_from<I&, S> || sized_sentinel_for<S, I> is modeled, or [i, bound) denotes a range.
4
#
Effects:
  • (4.1)
    If I and S model assignable_from<I&, S>, equivalent to i = std​::​move(bound).
  • (4.2)
    Otherwise, if S and I model sized_sentinel_for<S, I>, equivalent to ranges​::​advance(i, bound - i).
  • (4.3)
    Otherwise, while bool(i != bound) is true, increments i.
🔗
template<input_or_output_iterator I, sentinel_for<I> S> constexpr iter_difference_t<I> ranges::advance(I& i, iter_difference_t<I> n, S bound);
5
#
Preconditions: If n > 0, [i, bound) denotes a range.
If n == 0, [i, bound) or [bound, i) denotes a range.
If n < 0, [bound, i) denotes a range, I models bidirectional_iterator, and I and S model same_as<I, S>.
6
#
Effects:
  • (6.1)
    If S and I model sized_sentinel_for<S, I>:
    • (6.1.1)
      If ​|n|  ≥ |bound - i|, equivalent to ranges​::​advance(i, bound).
    • (6.1.2)
      Otherwise, equivalent to ranges​::​advance(i, n).
  • (6.2)
    Otherwise,
    • (6.2.1)
      if n is non-negative, while bool(i != bound) is true, increments i but at most n times.
    • (6.2.2)
      Otherwise, while bool(i != bound) is true, decrements i but at most -n times.
7
#
Returns: n - M, where M is the difference between the ending and starting positions of i.

25.4.4.3 ranges​::​distance [range.iter.op.distance]

🔗
template<class I, sentinel_for<I> S> requires (!sized_sentinel_for<S, I>) constexpr iter_difference_t<I> ranges::distance(I first, S last);
1
#
Preconditions: [first, last) denotes a range.
2
#
Effects: Increments first until last is reached and returns the number of increments.
🔗
template<class I, sized_sentinel_for<decay_t<I>> S> constexpr iter_difference_t<decay_t<I>> ranges::distance(I&& first, S last);
3
#
Effects: Equivalent to: return last - static_cast<const decay_t<I>&>(first);
🔗
template<range R> constexpr range_difference_t<R> ranges::distance(R&& r);
4
#
Effects: If R models sized_range, equivalent to: return static_cast<range_difference_t<R>>(ranges::size(r)); // [range.prim.size]
Otherwise, equivalent to: return ranges::distance(ranges::begin(r), ranges::end(r)); // [range.access]

25.4.4.4 ranges​::​next [range.iter.op.next]

🔗
template<input_or_output_iterator I> constexpr I ranges::next(I x);
1
#
Effects: Equivalent to: ++x; return x;
🔗
template<input_or_output_iterator I> constexpr I ranges::next(I x, iter_difference_t<I> n);
2
#
Effects: Equivalent to: ranges​::​advance(x, n); return x;
🔗
template<input_or_output_iterator I, sentinel_for<I> S> constexpr I ranges::next(I x, S bound);
3
#
Effects: Equivalent to: ranges​::​advance(x, bound); return x;
🔗
template<input_or_output_iterator I, sentinel_for<I> S> constexpr I ranges::next(I x, iter_difference_t<I> n, S bound);
4
#
Effects: Equivalent to: ranges​::​advance(x, n, bound); return x;

25.4.4.5 ranges​::​prev [range.iter.op.prev]

🔗
template<bidirectional_iterator I> constexpr I ranges::prev(I x);
1
#
Effects: Equivalent to: --x; return x;
🔗
template<bidirectional_iterator I> constexpr I ranges::prev(I x, iter_difference_t<I> n);
2
#
Effects: Equivalent to: ranges​::​advance(x, -n); return x;
🔗
template<bidirectional_iterator I> constexpr I ranges::prev(I x, iter_difference_t<I> n, I bound);
3
#
Effects: Equivalent to: ranges​::​advance(x, -n, bound); return x;