23 Iterators library [iterators]

23.4 Iterator primitives [iterator.primitives]

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

23.4.1 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
:
For a program-defined iterator BinaryTreeIterator, it could 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
:
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
]

23.4.2 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, returns the number of increments needed to get from first to last.
🔗
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;

23.4.3 Range iterator operations [range.iter.ops]

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
:
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 this subclause 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
: 
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 this subclause is unspecified, except where explicitly stated otherwise.

23.4.3.1 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:
  • (2.1)
    If I models random_­access_­iterator, equivalent to i += n.
  • (2.2)
    Otherwise, if n is non-negative, increments i by n.
  • (2.3)
    Otherwise, decrements i by -n.
🔗
template<input_­or_­output_­iterator I, sentinel_­for<I> S> constexpr void ranges::advance(I& i, S bound);
3
#
Preconditions: [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 ​, 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.

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

🔗
template<input_­or_­output_­iterator I, sentinel_­for<I> S> constexpr iter_difference_t<I> ranges::distance(I first, S last);
1
#
Preconditions: [first, last) denotes a range, or [last, first) denotes a range and S and I model same_­as<S, I> && sized_­sentinel_­for<S, I>.
2
#
Effects: If S and I model sized_­sentinel_­for<S, I>, returns (last - first); otherwise, returns the number of increments needed to get from first to last.
🔗
template<range R> constexpr range_difference_t<R> ranges::distance(R&& r);
3
#
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]

23.4.3.3 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;

23.4.3.4 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;