[iterator.primitives]

# 24 Iterators library [[iterators]](./#iterators)

## 24.4 Iterator primitives [iterator.primitives]

### [24.4.1](#general) General [[iterator.primitives.general]](iterator.primitives.general)

[1](#general-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2738)

To simplify the use of iterators, the library provides
several classes and functions[.](#general-1.sentence-1)

### [24.4.2](#std.iterator.tags) Standard iterator tags [[std.iterator.tags]](std.iterator.tags)

[1](#std.iterator.tags-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2744)

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[.](#std.iterator.tags-1.sentence-1)

To facilitate this, the
library introduces[*category tag*](#def:category_tag "24.4.2 Standard iterator tags [std.iterator.tags]") classes which are used as compile time tags for algorithm selection[.](#std.iterator.tags-1.sentence-2)

They are:output_iterator_tag,input_iterator_tag,forward_iterator_tag,bidirectional_iterator_tag,random_access_iterator_tag,
andcontiguous_iterator_tag[.](#std.iterator.tags-1.sentence-3)

For every iterator of typeI,iterator_traits<I>​::​iterator_category shall be defined to be a category tag that describes the
iterator's behavior[.](#std.iterator.tags-1.sentence-4)

Additionally,iterator_traits<I>​::​iterator_concept may be used to indicate conformance to
the iterator concepts ([[iterator.concepts]](iterator.concepts "24.3.4 Iterator concepts"))[.](#std.iterator.tags-1.sentence-5)

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](#std.iterator.tags-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2788)

[*Example [1](#std.iterator.tags-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](#std.iterator.tags-3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2804)

[*Example [2](#std.iterator.tags-example-2)*:

Ifevolve() 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*]

### [24.4.3](#iterator.operations) Iterator operations [[iterator.operations]](iterator.operations)

[1](#iterator.operations-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2834)

Since only random access iterators provide+ and- operators, the library provides two
function templatesadvance anddistance[.](#iterator.operations-1.sentence-1)

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[.](#iterator.operations-1.sentence-2)

[🔗](#lib:advance)

`template<class InputIterator, class Distance>
  constexpr void advance(InputIterator& i, Distance n);
`

[2](#iterator.operations-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2863)

*Preconditions*: n is negative only for bidirectional iterators[.](#iterator.operations-2.sentence-1)

[3](#iterator.operations-3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2868)

*Effects*: Increments i by n if n is non-negative, and
decrements i by -n otherwise[.](#iterator.operations-3.sentence-1)

[🔗](#lib:distance)

`template<class InputIterator>
  constexpr typename iterator_traits<InputIterator>::difference_type
    distance(InputIterator first, InputIterator last);
`

[4](#iterator.operations-4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2882)

*Preconditions*: last is reachable from first, orInputIterator meets
the *Cpp17RandomAccessIterator* requirements andfirst is reachable from last[.](#iterator.operations-4.sentence-1)

[5](#iterator.operations-5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2889)

*Effects*: If InputIterator meets the *Cpp17RandomAccessIterator* requirements,
returns (last - first); otherwise, incrementsfirst until last is reached and returns
the number of increments[.](#iterator.operations-5.sentence-1)

[🔗](#lib:next)

`template<class InputIterator>
  constexpr InputIterator next(InputIterator x,
    typename iterator_traits<InputIterator>::difference_type n = 1);
`

[6](#iterator.operations-6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2905)

*Effects*: Equivalent to: advance(x, n); return x;

[🔗](#lib:prev)

`template<class BidirectionalIterator>
  constexpr BidirectionalIterator prev(BidirectionalIterator x,
    typename iterator_traits<BidirectionalIterator>::difference_type n = 1);
`

[7](#iterator.operations-7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2918)

*Effects*: Equivalent to: advance(x, -n); return x;

### [24.4.4](#range.iter.ops) Range iterator operations [[range.iter.ops]](range.iter.ops)

#### [24.4.4.1](#range.iter.ops.general) General [[range.iter.ops.general]](range.iter.ops.general)

[1](#range.iter.ops.general-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2927)

The library includes the function templatesranges​::​advance, ranges​::​distance,ranges​::​next, and ranges​::​prev to manipulate iterators[.](#range.iter.ops.general-1.sentence-1)

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[.](#range.iter.ops.general-1.sentence-2)

[*Example [1](#range.iter.ops.general-example-1)*:

ranges​::​advance uses the + operator to move a[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") forward n steps in constant time[.](#range.iter.ops.general-1.sentence-3)

For an iterator type that does not model [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]"),ranges​::​advance instead performs n individual increments with
the ++ operator[.](#range.iter.ops.general-1.sentence-4)

— *end example*]

[2](#range.iter.ops.general-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2942)

The entities defined in [[range.iter.ops]](#range.iter.ops "24.4.4 Range iterator operations") are
algorithm function objects ([[alg.func.obj]](alg.func.obj "16.3.3.4 Algorithm function objects"))[.](#range.iter.ops.general-2.sentence-1)

#### [24.4.4.2](#range.iter.op.advance) ranges​::​advance [[range.iter.op.advance]](range.iter.op.advance)

[🔗](#lib:advance_)

`template<[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") I>
  constexpr void ranges::advance(I& i, iter_difference_t<I> n);
`

[1](#range.iter.op.advance-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2955)

*Preconditions*: If I does not model [bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]"),n is not negative[.](#range.iter.op.advance-1.sentence-1)

[2](#range.iter.op.advance-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2960)

*Effects*: 

- [(2.1)](#range.iter.op.advance-2.1)

  If I models [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]"),
 equivalent to i += n[.](#range.iter.op.advance-2.1.sentence-1)

- [(2.2)](#range.iter.op.advance-2.2)

  Otherwise, if n is non-negative, increments i by n[.](#range.iter.op.advance-2.2.sentence-1)

- [(2.3)](#range.iter.op.advance-2.3)

  Otherwise, decrements i by -n[.](#range.iter.op.advance-2.3.sentence-1)

[🔗](#lib:advance__)

`template<[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S>
  constexpr void ranges::advance(I& i, S bound);
`

[3](#range.iter.op.advance-3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2978)

*Preconditions*: Either [assignable_from](concept.assignable#concept:assignable_from "18.4.8 Concept assignable_­from [concept.assignable]")<I&, S> || [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<S, I> is modeled, or
[i, bound) denotes a range[.](#range.iter.op.advance-3.sentence-1)

[4](#range.iter.op.advance-4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2983)

*Effects*: 

- [(4.1)](#range.iter.op.advance-4.1)

  If I and S model [assignable_from](concept.assignable#concept:assignable_from "18.4.8 Concept assignable_­from [concept.assignable]")<I&, S>,
 equivalent to i = std​::​move(bound)[.](#range.iter.op.advance-4.1.sentence-1)

- [(4.2)](#range.iter.op.advance-4.2)

  Otherwise, if S and I model [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<S, I>,
 equivalent to ranges​::​advance(i, bound - i)[.](#range.iter.op.advance-4.2.sentence-1)

- [(4.3)](#range.iter.op.advance-4.3)

  Otherwise, while bool(i != bound) is true,
 increments i[.](#range.iter.op.advance-4.3.sentence-1)

[🔗](#lib:advance___)

`template<[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S>
  constexpr iter_difference_t<I> ranges::advance(I& i, iter_difference_t<I> n, S bound);
`

[5](#range.iter.op.advance-5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3002)

*Preconditions*: If n > 0, [i, bound) denotes a range[.](#range.iter.op.advance-5.sentence-1)

If n == 0, [i, bound) or [bound, i) denotes a range[.](#range.iter.op.advance-5.sentence-2)

If n < 0, [bound, i) denotes a range,I models [bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]"), andI and S model [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I, S>[.](#range.iter.op.advance-5.sentence-3)

[6](#range.iter.op.advance-6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3010)

*Effects*: 

- [(6.1)](#range.iter.op.advance-6.1)

  If S and I model [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<S, I>:
  * [(6.1.1)](#range.iter.op.advance-6.1.1)

      If ​|n| ≥ |bound - i|,
 equivalent to ranges​::​advance(i, bound)[.](#range.iter.op.advance-6.1.1.sentence-1)

  * [(6.1.2)](#range.iter.op.advance-6.1.2)

      Otherwise, equivalent to ranges​::​advance(i, n)[.](#range.iter.op.advance-6.1.2.sentence-1)

- [(6.2)](#range.iter.op.advance-6.2)

  Otherwise,
  * [(6.2.1)](#range.iter.op.advance-6.2.1)

      if n is non-negative,
 while bool(i != bound) is true,
 increments i but at most n times[.](#range.iter.op.advance-6.2.1.sentence-1)

  * [(6.2.2)](#range.iter.op.advance-6.2.2)

      Otherwise,
 while bool(i != bound) is true,
 decrements i but at most -n times[.](#range.iter.op.advance-6.2.2.sentence-1)

[7](#range.iter.op.advance-7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3030)

*Returns*: n - M, where M is the difference between
the ending and starting positions of i[.](#range.iter.op.advance-7.sentence-1)

#### [24.4.4.3](#range.iter.op.distance) ranges​::​distance [[range.iter.op.distance]](range.iter.op.distance)

[🔗](#lib:distance_)

`template<class I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S>
  requires (![sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<S, I>)
  constexpr iter_difference_t<I> ranges::distance(I first, S last);
`

[1](#range.iter.op.distance-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3045)

*Preconditions*: [first, last) denotes a range[.](#range.iter.op.distance-1.sentence-1)

[2](#range.iter.op.distance-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3049)

*Effects*: Increments first until last is reached and
returns the number of increments[.](#range.iter.op.distance-2.sentence-1)

[🔗](#lib:distance__)

`template<class I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<decay_t<I>> S>
  constexpr iter_difference_t<decay_t<I>> ranges::distance(I&& first, S last);
`

[3](#range.iter.op.distance-3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3062)

*Effects*: Equivalent to:if constexpr (!is_array_v<remove_reference_t<I>>)return last - first;elsereturn last - static_cast<decay_t<I>>(first);

[🔗](#lib:distance___)

`template<[range](range.range#concept:range "25.4.2 Ranges [range.range]") R>
  constexpr range_difference_t<R> ranges::distance(R&& r);
`

[4](#range.iter.op.distance-4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3080)

*Effects*: If R models [sized_range](range.sized#concept:sized_range "25.4.4 Sized ranges [range.sized]"), equivalent to:return static_cast<range_difference_t<R>>(ranges::size(r)); // [[range.prim.size]](range.prim.size "25.3.10 ranges​::​size")

Otherwise, equivalent to:return ranges::distance(ranges::begin(r), ranges::end(r)); // [[range.access]](range.access "25.3 Range access")

#### [24.4.4.4](#range.iter.op.next) ranges​::​next [[range.iter.op.next]](range.iter.op.next)

[🔗](#lib:next_)

`template<[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") I>
  constexpr I ranges::next(I x);
`

[1](#range.iter.op.next-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3101)

*Effects*: Equivalent to: ++x; return x;

[🔗](#lib:next__)

`template<[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") I>
  constexpr I ranges::next(I x, iter_difference_t<I> n);
`

[2](#range.iter.op.next-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3113)

*Effects*: Equivalent to: ranges​::​advance(x, n); return x;

[🔗](#lib:next___)

`template<[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S>
  constexpr I ranges::next(I x, S bound);
`

[3](#range.iter.op.next-3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3125)

*Effects*: Equivalent to: ranges​::​advance(x, bound); return x;

[🔗](#lib:next____)

`template<[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S>
  constexpr I ranges::next(I x, iter_difference_t<I> n, S bound);
`

[4](#range.iter.op.next-4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3137)

*Effects*: Equivalent to: ranges​::​advance(x, n, bound); return x;

#### [24.4.4.5](#range.iter.op.prev) ranges​::​prev [[range.iter.op.prev]](range.iter.op.prev)

[🔗](#lib:prev_)

`template<[bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") I>
  constexpr I ranges::prev(I x);
`

[1](#range.iter.op.prev-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3150)

*Effects*: Equivalent to: --x; return x;

[🔗](#lib:prev__)

`template<[bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") I>
  constexpr I ranges::prev(I x, iter_difference_t<I> n);
`

[2](#range.iter.op.prev-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3162)

*Effects*: Equivalent to: ranges​::​advance(x, -n); return x;

[🔗](#lib:prev___)

`template<[bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") I>
  constexpr I ranges::prev(I x, iter_difference_t<I> n, I bound);
`

[3](#range.iter.op.prev-3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3174)

*Effects*: Equivalent to: ranges​::​advance(x, -n, bound); return x;