[iterator.requirements]

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

## 24.3 Iterator requirements [iterator.requirements]

### [24.3.1](#general) General [[iterator.requirements.general]](iterator.requirements.general)

[1](#general-1)

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

Iterators are a generalization of pointers that allow a C++ program to work with different data structures
(for example, containers and ranges) in a uniform manner[.](#general-1.sentence-1)

To be able to construct template algorithms that work correctly and
efficiently on different types of data structures, the library formalizes not just the interfaces but also the
semantics and complexity assumptions of iterators[.](#general-1.sentence-2)

An input iteratori supports the expression*i,
resulting in a value of some object typeT,
called the[*value type*](#def:value_type "24.3.1 General [iterator.requirements.general]") of the iterator[.](#general-1.sentence-3)

An output iterator i has a non-empty set of types that are[*writable*](#def:writable "24.3.1 General [iterator.requirements.general]") to the iterator;
for each such type T, the expression *i = o is valid where o is a value of type T[.](#general-1.sentence-4)

For every iterator typeX,
there is a corresponding signed integer-like type ([[iterator.concept.winc]](#iterator.concept.winc "24.3.4.4 Concept weakly_­incrementable")) called the[*difference type*](#def:difference_type "24.3.1 General [iterator.requirements.general]") of the iterator[.](#general-1.sentence-5)

[2](#general-2)

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

Since iterators are an abstraction of pointers, their semantics are
a generalization of most of the semantics of pointers in C++[.](#general-2.sentence-1)

This ensures that every
function template
that takes iterators
works as well with regular pointers[.](#general-2.sentence-2)

This document defines
six categories of iterators, according to the operations
defined on them:[*input iterators*](#def:input_iterators),[*output iterators*](#def:output_iterators),[*forward iterators*](#def:forward_iterators),[*bidirectional iterators*](#def:bidirectional_iterators),[*random access iterators*](#def:random_access_iterators),
and[*contiguous iterators*](#def:contiguous_iterators),
as shown in Table [77](#tab:iterators.relations "Table 77: Relations among iterator categories")[.](#general-2.sentence-3)

Table [77](#tab:iterators.relations) — Relations among iterator categories [[tab:iterators.relations]](./tab:iterators.relations)  

| [ð](#tab:iterators.relations-row-1)<br>**Contiguous** | â **Random Access** | â **Bidirectional** | â **Forward** | â **Input** |
| --- | --- | --- | --- | --- |
| [ð](#tab:iterators.relations-row-2) |  |  |  | â **Output** |

[3](#general-3)

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

The six categories of iterators correspond to the iterator concepts

- [(3.1)](#general-3.1)

[input_iterator](#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") ([[iterator.concept.input]](#iterator.concept.input "24.3.4.9 Concept input_­iterator")),

- [(3.2)](#general-3.2)

[output_iterator](#concept:output_iterator "24.3.4.10 Concept output_­iterator [iterator.concept.output]") ([[iterator.concept.output]](#iterator.concept.output "24.3.4.10 Concept output_­iterator")),

- [(3.3)](#general-3.3)

[forward_iterator](#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") ([[iterator.concept.forward]](#iterator.concept.forward "24.3.4.11 Concept forward_­iterator")),

- [(3.4)](#general-3.4)

[bidirectional_iterator](#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") ([[iterator.concept.bidir]](#iterator.concept.bidir "24.3.4.12 Concept bidirectional_­iterator")),

- [(3.5)](#general-3.5)

[random_access_iterator](#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") ([[iterator.concept.random.access]](#iterator.concept.random.access "24.3.4.13 Concept random_­access_­iterator")),
and

- [(3.6)](#general-3.6)

[contiguous_iterator](#concept:contiguous_iterator "24.3.4.14 Concept contiguous_­iterator [iterator.concept.contiguous]") ([[iterator.concept.contiguous]](#iterator.concept.contiguous "24.3.4.14 Concept contiguous_­iterator")),

respectively[.](#general-3.sentence-1)

The generic term [*iterator*](#def:iterator "24.3.1 General [iterator.requirements.general]") refers to any type that models the[input_or_output_iterator](#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") concept ([[iterator.concept.iterator]](#iterator.concept.iterator "24.3.4.6 Concept input_­or_­output_­iterator"))[.](#general-3.sentence-2)

[4](#general-4)

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

Forward iterators meet all the requirements of input
iterators and can be used whenever
an input iterator is specified;
Bidirectional iterators also meet all the requirements of
forward iterators and can be used whenever a forward iterator is specified;
Random access iterators also meet all the requirements of bidirectional
iterators and can be used whenever a bidirectional iterator is specified;
Contiguous iterators also meet all the requirements of random access
iterators and can be used whenever a random access iterator is specified[.](#general-4.sentence-1)

[5](#general-5)

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

Iterators that further meet the requirements of output iterators are
called [*mutable iterators*](#def:mutable_iterator "24.3.1 General [iterator.requirements.general]")[.](#general-5.sentence-1)

Nonmutable iterators are referred to
as [*constant iterators*](#def:constant_iterator "24.3.1 General [iterator.requirements.general]")[.](#general-5.sentence-2)

[6](#general-6)

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

In addition to the requirements in this subclause,
the nested [*typedef-name*](dcl.typedef#nt:typedef-name "9.2.4 The typedef specifier [dcl.typedef]")*s* specified in [[iterator.traits]](#iterator.traits "24.3.2.3 Iterator traits") shall be provided for the iterator type[.](#general-6.sentence-1)

[*Note [1](#general-note-1)*:

Either the iterator type must provide the [*typedef-name*](dcl.typedef#nt:typedef-name "9.2.4 The typedef specifier [dcl.typedef]")*s* directly
(in which case iterator_traits pick them up automatically), or
an iterator_traits specialization must provide them[.](#general-6.sentence-2)

â *end note*]

[7](#general-7)

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

Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element
of the array, so for any iterator type there is an iterator value that points past the last element of a
corresponding sequence[.](#general-7.sentence-1)

Such a value is called a [*past-the-end value*](#def:iterator,past-the-end "24.3.1 General [iterator.requirements.general]")[.](#general-7.sentence-2)

Values of an iterator i for which the expression *i is defined
are called [*dereferenceable*](#def:iterator,dereferenceable "24.3.1 General [iterator.requirements.general]")[.](#general-7.sentence-3)

The library never assumes that past-the-end values are dereferenceable[.](#general-7.sentence-4)

Iterators can also have singular values that are not associated with any
sequence[.](#general-7.sentence-5)

Results of most expressions are undefined for singular values;
the only exceptions are destroying an iterator that holds a singular value,
the assignment of a non-singular value to
an iterator that holds a singular value, and, for iterators that meet the*Cpp17DefaultConstructible* requirements, using a value-initialized iterator
as the source of a copy or move operation[.](#general-7.sentence-6)

[*Note [2](#general-note-2)*:

This guarantee is not
offered for default-initialization, although the distinction only matters for types
with trivial default constructors such as pointers or aggregates holding pointers[.](#general-7.sentence-7)

â *end note*]

In these cases the singular
value is overwritten the same way as any other value[.](#general-7.sentence-8)

Dereferenceable
values are always non-singular[.](#general-7.sentence-9)

[8](#general-8)

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

Most of the library's algorithmic templates that operate on data structures have
interfaces that use ranges[.](#general-8.sentence-1)

A [*range*](#def:range "24.3.1 General [iterator.requirements.general]") is an iterator and a [*sentinel*](#def:sentinel "24.3.1 General [iterator.requirements.general]") that designate the beginning and end of the computation, or an iterator and a
count that designate the beginning and the number of elements to which the
computation is to be applied[.](#general-8.sentence-2)[198](#footnote-198 "The sentinel denoting the end of a range can have the same type as the iterator denoting the beginning of the range, or a different type.")

[9](#general-9)

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

An iterator and a sentinel denoting a range are comparable[.](#general-9.sentence-1)

A range [i, s)
is empty if i == s;
otherwise, [i, s)
refers to the elements in the data structure starting with the element
pointed to byi and up to but not including the element, if any, pointed to by
the first iterator j such that j == s[.](#general-9.sentence-2)

[10](#general-10)

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

A sentinel s is called [*reachable from*](#def:reachable_from "24.3.1 General [iterator.requirements.general]") an iterator i if
and only if there is a finite sequence of applications of the expression++i that makes i == s[.](#general-10.sentence-1)

If s is reachable from i,
[i, s) denotes a [*valid range*](#def:range,valid "24.3.1 General [iterator.requirements.general]")[.](#general-10.sentence-2)

[11](#general-11)

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

A [*counted range*](#def:range,counted "24.3.1 General [iterator.requirements.general]") i+[0, n) is empty if n == 0;
otherwise, i+[0, n) refers to
the n elements in the data structure
starting with the element pointed to by i and up to but not including
the element, if any, pointed to by
the result of n applications of ++i[.](#general-11.sentence-1)

A counted range i+[0, n) is [*valid*](#def:range,counted,valid "24.3.1 General [iterator.requirements.general]") if and only if n == 0;
or n is positive, i is dereferenceable,
and ++i+[0, --n) is valid[.](#general-11.sentence-2)

[12](#general-12)

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

The result of the application of library functions
to invalid ranges is undefined[.](#general-12.sentence-1)

[13](#general-13)

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

For an iterator i of a type that
models [contiguous_iterator](#concept:contiguous_iterator "24.3.4.14 Concept contiguous_­iterator [iterator.concept.contiguous]") ([[iterator.concept.contiguous]](#iterator.concept.contiguous "24.3.4.14 Concept contiguous_­iterator")),
library functions are permitted
to replace [i, s) with
[to_address(i), to_address(i + ranges​::​distance(i, s))), and
to replace i+[0, n) with [to_address(i), to_address(i + n))[.](#general-13.sentence-1)

[*Note [3](#general-note-3)*:

This means a program cannot rely on any side effects of
dereferencing a contiguous iterator i,
because library functions might operate on
pointers obtained by to_address(i) instead of operating on i[.](#general-13.sentence-2)

Similarly, a program cannot rely on any side effects of
individual increments on a contiguous iterator i,
because library functions might advance i only once[.](#general-13.sentence-3)

â *end note*]

[14](#general-14)

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

All the categories of iterators require only those functions that are realizable for a given category in
constant time (amortized)[.](#general-14.sentence-1)

Therefore, requirement tables and concept definitions for the iterators
do not specify complexity[.](#general-14.sentence-2)

[15](#general-15)

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

Destruction of an iterator may invalidate pointers and references previously
obtained from that iterator if its type does not meet the*Cpp17ForwardIterator* requirements and does not model [forward_iterator](#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]")[.](#general-15.sentence-1)

[16](#general-16)

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

An [*invalid iterator*](#def:iterator,invalid "24.3.1 General [iterator.requirements.general]") is an iterator that may be singular[.](#general-16.sentence-1)[199](#footnote-199 "This definition applies to pointers, since pointers are iterators. The effect of dereferencing an iterator that has been invalidated is undefined.")

[17](#general-17)

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

Iterators meet the [*constexpr iterators*](#def:iterator,constexpr "24.3.1 General [iterator.requirements.general]") requirements
if all operations provided to meet iterator category requirements
are constexpr functions[.](#general-17.sentence-1)

[*Note [4](#general-note-4)*:

For example, the types âpointer to intâ andreverse_iterator<int*> meet the constexpr iterator requirements[.](#general-17.sentence-2)

â *end note*]

[198)](#footnote-198)[198)](#footnoteref-198)

The sentinel denoting the end of a range
can have the same type as the iterator denoting the beginning of the range, or a
different type[.](#footnote-198.sentence-1)

[199)](#footnote-199)[199)](#footnoteref-199)

This definition applies to pointers, since pointers are iterators[.](#footnote-199.sentence-1)

The effect of dereferencing an iterator that has been invalidated
is undefined[.](#footnote-199.sentence-2)

### [24.3.2](#iterator.assoc.types) Associated types [[iterator.assoc.types]](iterator.assoc.types)

#### [24.3.2.1](#incrementable.traits) Incrementable traits [[incrementable.traits]](incrementable.traits)

[1](#incrementable.traits-1)

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

To implement algorithms only in terms of incrementable types,
it is often necessary to determine the difference type that
corresponds to a particular incrementable type[.](#incrementable.traits-1.sentence-1)

Accordingly,
it is required that if WI is the name of a type that models the[weakly_incrementable](#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") concept ([[iterator.concept.winc]](#iterator.concept.winc "24.3.4.4 Concept weakly_­incrementable")),
the typeiter_difference_t<WI> be defined as the incrementable type's difference type[.](#incrementable.traits-1.sentence-2)

[ð](#lib:incrementable_traits)

namespace std {template<class> struct incrementable_traits { }; template<class T>requires is_object_v<T>struct incrementable_traits<T*> {using difference_type = ptrdiff_t; }; template<class I>struct incrementable_traits<const I>: incrementable_traits<I> { }; template<class T>requires requires { typename T::difference_type; }struct incrementable_traits<T> {using difference_type = typename T::difference_type; }; template<class T>requires (!requires { typename T::difference_type; } &&requires(const T& a, const T& b) { { a - b } -> [integral](concepts.arithmetic#concept:integral "18.4.7 Arithmetic concepts [concepts.arithmetic]"); })struct incrementable_traits<T> {using difference_type = make_signed_t<decltype(declval<T>() - declval<T>())>; }; template<class T>using iter_difference_t = *see below*;}

[2](#incrementable.traits-2)

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

Let RI be remove_cvref_t<I>[.](#incrementable.traits-2.sentence-1)

The type iter_difference_t<I> denotes

- [(2.1)](#incrementable.traits-2.1)

incrementable_traits<RI>​::​difference_type if iterator_traits<RI> names a specialization
generated from the primary template, and

- [(2.2)](#incrementable.traits-2.2)

iterator_traits<RI>​::​difference_type otherwise[.](#incrementable.traits-2.sentence-2)

[3](#incrementable.traits-3)

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

Users may specialize incrementable_traits on program-defined types[.](#incrementable.traits-3.sentence-1)

#### [24.3.2.2](#readable.traits) Indirectly readable traits [[readable.traits]](readable.traits)

[1](#readable.traits-1)

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

To implement algorithms only in terms of indirectly readable types,
it is often necessary
to determine the value type that corresponds to
a particular indirectly readable type[.](#readable.traits-1.sentence-1)

Accordingly, it is required that if R is the name of a type that
models the [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") concept ([[iterator.concept.readable]](#iterator.concept.readable "24.3.4.2 Concept indirectly_­readable")),
the typeiter_value_t<R> be defined as the indirectly readable type's value type[.](#readable.traits-1.sentence-2)

[ð](#lib:indirectly_readable_traits)

template<class> struct *cond-value-type* { }; // *exposition only*template<class T>requires is_object_v<T>struct *cond-value-type*<T> {using value_type = remove_cv_t<T>;};

template<class T>concept [*has-member-value-type*](#concept:has-member-value-type "24.3.2.2 Indirectly readable traits [readable.traits]") = requires { typename T::value_type; }; // *exposition only*template<class T>concept [*has-member-element-type*](#concept:has-member-element-type "24.3.2.2 Indirectly readable traits [readable.traits]") = requires { typename T::element_type; }; // *exposition only*template<class> struct indirectly_readable_traits { };

template<class T>struct indirectly_readable_traits<T*>: *cond-value-type*<T> { };

template<class I>requires is_array_v<I>struct indirectly_readable_traits<I> {using value_type = remove_cv_t<remove_extent_t<I>>;};

template<class I>struct indirectly_readable_traits<const I>: indirectly_readable_traits<I> { };

template<[*has-member-value-type*](#concept:has-member-value-type "24.3.2.2 Indirectly readable traits [readable.traits]") T>struct indirectly_readable_traits<T>: *cond-value-type*<typename T::value_type> { };

template<[*has-member-element-type*](#concept:has-member-element-type "24.3.2.2 Indirectly readable traits [readable.traits]") T>struct indirectly_readable_traits<T>: *cond-value-type*<typename T::element_type> { };

template<[*has-member-value-type*](#concept:has-member-value-type "24.3.2.2 Indirectly readable traits [readable.traits]") T>requires [*has-member-element-type*](#concept:has-member-element-type "24.3.2.2 Indirectly readable traits [readable.traits]")<T>struct indirectly_readable_traits<T> { };

template<[*has-member-value-type*](#concept:has-member-value-type "24.3.2.2 Indirectly readable traits [readable.traits]") T>requires [*has-member-element-type*](#concept:has-member-element-type "24.3.2.2 Indirectly readable traits [readable.traits]")<T> &&[same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<remove_cv_t<typename T::element_type>, remove_cv_t<typename T::value_type>>struct indirectly_readable_traits<T>: *cond-value-type*<typename T::value_type> { };

template<class T> using iter_value_t = *see below*;

[2](#readable.traits-2)

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

Let RI be remove_cvref_t<I>[.](#readable.traits-2.sentence-1)

The type iter_value_t<I> denotes

- [(2.1)](#readable.traits-2.1)

indirectly_readable_traits<RI>​::​value_type if iterator_traits<RI> names a specialization
generated from the primary template, and

- [(2.2)](#readable.traits-2.2)

iterator_traits<RI>​::​value_type otherwise[.](#readable.traits-2.sentence-2)

[3](#readable.traits-3)

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

Class template indirectly_readable_traits may be specialized
on program-defined types[.](#readable.traits-3.sentence-1)

[4](#readable.traits-4)

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

[*Note [1](#readable.traits-note-1)*:

Some legacy output iterators define a nested type named value_type that is an alias for void[.](#readable.traits-4.sentence-1)

These types are not [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") and have no associated value types[.](#readable.traits-4.sentence-2)

â *end note*]

[5](#readable.traits-5)

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

[*Note [2](#readable.traits-note-2)*:

Smart pointers like shared_ptr<int> are [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") and
have an associated value type, but a smart pointer like shared_ptr<void> is not [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") and has no associated value type[.](#readable.traits-5.sentence-1)

â *end note*]

#### [24.3.2.3](#iterator.traits) Iterator traits [[iterator.traits]](iterator.traits)

[1](#iterator.traits-1)

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

To implement algorithms only in terms of iterators, it is sometimes necessary to
determine the iterator category that corresponds to a particular iterator type[.](#iterator.traits-1.sentence-1)

Accordingly, it is required that ifI is the type of an iterator,
the type

[ð](#lib:iterator_category,iterator_traits)

iterator_traits<I>::iterator_category be defined as the iterator's iterator category[.](#iterator.traits-1.sentence-2)

In addition, the types

[ð](#lib:pointer,iterator_traits)

iterator_traits<I>::pointer
iterator_traits<I>::reference shall be defined as the iterator's pointer and reference types;
that is, for an
iterator object a of class type,
the same type asdecltype(a.operator->()) anddecltype(*a),
respectively[.](#iterator.traits-1.sentence-3)

The typeiterator_traits<I>​::​pointer shall be void for an iterator of class type I that does not support operator->[.](#iterator.traits-1.sentence-4)

Additionally, in the case of an output iterator, the typesiterator_traits<I>::value_type
iterator_traits<I>::difference_type
iterator_traits<I>::reference may be defined as void[.](#iterator.traits-1.sentence-5)

[2](#iterator.traits-2)

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

The definitions in this subclause make use of the following
exposition-only concepts:template<class I>concept [*cpp17-iterator*](#concept:cpp17-iterator "24.3.2.3 Iterator traits [iterator.traits]") =requires(I i) {{ *i } -> [*can-reference*](iterator.synopsis#concept:can-reference "24.2 Header <iterator>&nbsp;synopsis [iterator.synopsis]"); { ++i } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I&>; { *i++ } -> [*can-reference*](iterator.synopsis#concept:can-reference "24.2 Header <iterator>&nbsp;synopsis [iterator.synopsis]"); } && [copyable](concepts.object#concept:copyable "18.6 Object concepts [concepts.object]")<I>;

template<class I>concept [*cpp17-input-iterator*](#concept:cpp17-input-iterator "24.3.2.3 Iterator traits [iterator.traits]") =[*cpp17-iterator*](#concept:cpp17-iterator "24.3.2.3 Iterator traits [iterator.traits]")<I> && [equality_comparable](concept.equalitycomparable#concept:equality_comparable "18.5.4 Concept equality_­comparable [concept.equalitycomparable]")<I> && requires(I i) {typename incrementable_traits<I>::difference_type; typename indirectly_readable_traits<I>::value_type; typename common_reference_t<iter_reference_t<I>&&, typename indirectly_readable_traits<I>::value_type&>; typename common_reference_t<decltype(*i++)&&, typename indirectly_readable_traits<I>::value_type&>; requires [signed_integral](concepts.arithmetic#concept:signed_integral "18.4.7 Arithmetic concepts [concepts.arithmetic]")<typename incrementable_traits<I>::difference_type>; };

template<class I>concept [*cpp17-forward-iterator*](#concept:cpp17-forward-iterator "24.3.2.3 Iterator traits [iterator.traits]") =[*cpp17-input-iterator*](#concept:cpp17-input-iterator "24.3.2.3 Iterator traits [iterator.traits]")<I> && [constructible_from](concept.constructible#concept:constructible_from "18.4.11 Concept constructible_­from [concept.constructible]")<I> && is_reference_v<iter_reference_t<I>> &&[same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<remove_cvref_t<iter_reference_t<I>>, typename indirectly_readable_traits<I>::value_type> &&requires(I i) {{ i++ } -> [convertible_to](concept.convertible#concept:convertible_to "18.4.4 Concept convertible_­to [concept.convertible]")<const I&>; { *i++ } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<iter_reference_t<I>>; };

template<class I>concept [*cpp17-bidirectional-iterator*](#concept:cpp17-bidirectional-iterator "24.3.2.3 Iterator traits [iterator.traits]") =[*cpp17-forward-iterator*](#concept:cpp17-forward-iterator "24.3.2.3 Iterator traits [iterator.traits]")<I> && requires(I i) {{ --i } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I&>; { i-- } -> [convertible_to](concept.convertible#concept:convertible_to "18.4.4 Concept convertible_­to [concept.convertible]")<const I&>; { *i-- } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<iter_reference_t<I>>; };

template<class I>concept [*cpp17-random-access-iterator*](#concept:cpp17-random-access-iterator "24.3.2.3 Iterator traits [iterator.traits]") =[*cpp17-bidirectional-iterator*](#concept:cpp17-bidirectional-iterator "24.3.2.3 Iterator traits [iterator.traits]")<I> && [totally_ordered](concept.totallyordered#concept:totally_ordered "18.5.5 Concept totally_­ordered [concept.totallyordered]")<I> &&requires(I i, typename incrementable_traits<I>::difference_type n) {{ i += n } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I&>; { i -= n } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I&>; { i + n } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I>; { n + i } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I>; { i - n } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I>; { i - i } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<decltype(n)>; { i[n] } -> [convertible_to](concept.convertible#concept:convertible_to "18.4.4 Concept convertible_­to [concept.convertible]")<iter_reference_t<I>>; };

[3](#iterator.traits-3)

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

The members of a specialization iterator_traits<I> generated from theiterator_traits primary template are computed as follows:

- [(3.1)](#iterator.traits-3.1)

If I has valid ([[temp.deduct]](temp.deduct "13.10.3 Template argument deduction")) member
types difference_type, value_type,reference, and iterator_category,
theniterator_traits<I> has the following publicly accessible members:using iterator_category = typename I::iterator_category;using value_type = typename I::value_type;using difference_type = typename I::difference_type;using pointer = *see below*;using reference = typename I::reference;
   If the [*qualified-id*](expr.prim.id.qual#nt:qualified-id "7.5.5.3 Qualified names [expr.prim.id.qual]") I​::​pointer is valid and
denotes a type, then iterator_traits<I>​::​pointer names that type;
otherwise, it names void[.](#iterator.traits-3.1.sentence-2)

- [(3.2)](#iterator.traits-3.2)

Otherwise, if I satisfies the exposition-only concept[*cpp17-input-iterator*](#concept:cpp17-input-iterator "24.3.2.3 Iterator traits [iterator.traits]"),iterator_traits<I> has the following
publicly accessible members:using iterator_category = *see below*;using value_type = typename indirectly_readable_traits<I>::value_type;using difference_type = typename incrementable_traits<I>::difference_type;using pointer = *see below*;using reference = *see below*;
  * [(3.2.1)](#iterator.traits-3.2.1)

      If the [*qualified-id*](expr.prim.id.qual#nt:qualified-id "7.5.5.3 Qualified names [expr.prim.id.qual]") I​::​pointer is valid and denotes a type,pointer names that type[.](#iterator.traits-3.2.1.sentence-1)
      Otherwise, ifdecltype(​declval<I&>().operator->()) is well-formed, thenpointer names that type[.](#iterator.traits-3.2.1.sentence-2)
      Otherwise, pointer names void[.](#iterator.traits-3.2.1.sentence-3)

  * [(3.2.2)](#iterator.traits-3.2.2)

      If the [*qualified-id*](expr.prim.id.qual#nt:qualified-id "7.5.5.3 Qualified names [expr.prim.id.qual]") I​::​reference is valid and denotes a
type, reference names that type[.](#iterator.traits-3.2.2.sentence-1)
      Otherwise, reference names iter_reference_t<I>[.](#iterator.traits-3.2.2.sentence-2)

  * [(3.2.3)](#iterator.traits-3.2.3)

      If the [*qualified-id*](expr.prim.id.qual#nt:qualified-id "7.5.5.3 Qualified names [expr.prim.id.qual]") I​::​iterator_category is valid and
denotes a type, iterator_category names that type[.](#iterator.traits-3.2.3.sentence-1)
      Otherwise, iterator_category names:
    +
          [(3.2.3.1)](#iterator.traits-3.2.3.1)
random_access_iterator_tag ifI satisfies [*cpp17-random-access-iterator*](#concept:cpp17-random-access-iterator "24.3.2.3 Iterator traits [iterator.traits]"),
or otherwise

    +
          [(3.2.3.2)](#iterator.traits-3.2.3.2)
bidirectional_iterator_tag ifI satisfies [*cpp17-bidirectional-iterator*](#concept:cpp17-bidirectional-iterator "24.3.2.3 Iterator traits [iterator.traits]"),
or otherwise

    +
          [(3.2.3.3)](#iterator.traits-3.2.3.3)
forward_iterator_tag ifI satisfies [*cpp17-forward-iterator*](#concept:cpp17-forward-iterator "24.3.2.3 Iterator traits [iterator.traits]"),
or otherwise

    +
          [(3.2.3.4)](#iterator.traits-3.2.3.4)
input_iterator_tag[.](#iterator.traits-3.2.3.sentence-2)

- [(3.3)](#iterator.traits-3.3)

Otherwise, if I satisfies the exposition-only concept[*cpp17-iterator*](#concept:cpp17-iterator "24.3.2.3 Iterator traits [iterator.traits]"), then iterator_traits<I> has the following publicly accessible
members:using iterator_category = output_iterator_tag;using value_type = void;using difference_type = *see below*;using pointer = void;using reference = void;
   If the [*qualified-id*](expr.prim.id.qual#nt:qualified-id "7.5.5.3 Qualified names [expr.prim.id.qual]")incrementable_traits<I>​::​difference_type is valid and denotes a type,
then difference_type names that type; otherwise, it names void[.](#iterator.traits-3.3.sentence-2)

- [(3.4)](#iterator.traits-3.4)

Otherwise, iterator_traits<I> has no members by any of the above names[.](#iterator.traits-3.sentence-1)

[4](#iterator.traits-4)

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

Explicit or partial specializations of iterator_traits may
have a member type iterator_concept that is used to indicate
conformance to the iterator concepts ([[iterator.concepts]](#iterator.concepts "24.3.4 Iterator concepts"))[.](#iterator.traits-4.sentence-1)

[*Example [1](#iterator.traits-example-1)*:

To indicate conformance to the [input_iterator](#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") concept
but a lack of conformance to
the *Cpp17InputIterator* requirements ([[input.iterators]](#input.iterators "24.3.5.3 Input iterators")),
an iterator_traits specialization might haveiterator_concept denote input_iterator_tag but not define iterator_category[.](#iterator.traits-4.sentence-2)

â *end example*]

[5](#iterator.traits-5)

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

iterator_traits is specialized for pointers asnamespace std {template<class T>requires is_object_v<T>struct iterator_traits<T*> {using iterator_concept = contiguous_iterator_tag; using iterator_category = random_access_iterator_tag; using value_type = remove_cv_t<T>; using difference_type = ptrdiff_t; using pointer = T*; using reference = T&; };}

[6](#iterator.traits-6)

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

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

To implement a genericreverse function, a C++ program can do the following:template<class BI>void reverse(BI first, BI last) {typename iterator_traits<BI>::difference_type n = distance(first, last); --n; while (n > 0) {typename iterator_traits<BI>::value_type tmp = *first; *first++ = *--last; *last = tmp;
 n -= 2; }}

â *end example*]

### [24.3.3](#iterator.cust) Customization point objects [[iterator.cust]](iterator.cust)

#### [24.3.3.1](#iterator.cust.move) ranges​::​iter_move [[iterator.cust.move]](iterator.cust.move)

[1](#iterator.cust.move-1)

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

The name ranges​::​iter_move denotes
a customization point object ([[customization.point.object]](customization.point.object "16.3.3.3.5 Customization Point Object types"))[.](#iterator.cust.move-1.sentence-1)

The expression ranges​::​iter_move(E) for a subexpression E is
expression-equivalent to:

- [(1.1)](#iterator.cust.move-1.1)

  iter_move(E), ifE has class or enumeration type anditer_move(E) is a well-formed expression when treated as an unevaluated operand,
where the meaning of iter_move is established as-if by performing
argument-dependent lookup only ([[basic.lookup.argdep]](basic.lookup.argdep "6.5.4 Argument-dependent name lookup"))[.](#iterator.cust.move-1.1.sentence-1)

- [(1.2)](#iterator.cust.move-1.2)

  Otherwise, if the expression *E is well-formed:
  * [(1.2.1)](#iterator.cust.move-1.2.1)

if *E is an lvalue, std​::​move(*E);

  * [(1.2.2)](#iterator.cust.move-1.2.2)

otherwise, *E[.](#iterator.cust.move-1.2.sentence-1)

- [(1.3)](#iterator.cust.move-1.3)

  Otherwise, ranges​::​iter_move(E) is ill-formed[.](#iterator.cust.move-1.3.sentence-1)
  [*Note [1](#iterator.cust.move-note-1)*:
  This case can result in substitution failure when ranges​::​iter_move(E) appears in the immediate context of a template instantiation[.](#iterator.cust.move-1.3.sentence-2)
 â *end note*]

[2](#iterator.cust.move-2)

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

If ranges​::​iter_move(E) is not equal to *E,
the program is ill-formed, no diagnostic required[.](#iterator.cust.move-2.sentence-1)

#### [24.3.3.2](#iterator.cust.swap) ranges​::​iter_swap [[iterator.cust.swap]](iterator.cust.swap)

[1](#iterator.cust.swap-1)

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

The name ranges​::​iter_swap denotes
a customization point object ([[customization.point.object]](customization.point.object "16.3.3.3.5 Customization Point Object types"))
that exchanges the values ([[concept.swappable]](concept.swappable "18.4.9 Concept swappable")) denoted by its
arguments[.](#iterator.cust.swap-1.sentence-1)

[2](#iterator.cust.swap-2)

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

Let *iter-exchange-move* be the exposition-only function template:

[ð](#iterator.cust.swap-itemdecl:1)

`template<class X, class Y>
  constexpr iter_value_t<X> iter-exchange-move(X&& x, Y&& y)
    noexcept(noexcept(iter_value_t<X>(iter_move(x))) &&
             noexcept(*x = iter_move(y)));
`

[3](#iterator.cust.swap-3)

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

*Effects*: Equivalent to:iter_value_t<X> old_value(iter_move(x));*x = iter_move(y);return old_value;

[4](#iterator.cust.swap-4)

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

The expression ranges​::​iter_swap(E1, E2) for subexpressionsE1 and E2 is expression-equivalent to:

- [(4.1)](#iterator.cust.swap-4.1)

  (void)iter_swap(E1, E2), if eitherE1 or E2 has class or enumeration type anditer_swap(E1, E2) is a well-formed expression
with overload resolution performed in a context that includes the declarationtemplate<class I1, class I2>void iter_swap(I1, I2) = delete; and does not include a declaration of ranges​::​iter_swap[.](#iterator.cust.swap-4.1.sentence-1)
  If the function selected by overload resolution does not exchange the values
denoted by E1 and E2,
the program is ill-formed, no diagnostic required[.](#iterator.cust.swap-4.1.sentence-2)
  [*Note [1](#iterator.cust.swap-note-1)*:
  This precludes calling unconstrained std​::​iter_swap[.](#iterator.cust.swap-4.1.sentence-3)
  When the deleted
overload is viable, program-defined overloads need to be more
specialized ([[temp.func.order]](temp.func.order "13.7.7.3 Partial ordering of function templates")) to be selected[.](#iterator.cust.swap-4.1.sentence-4)
 â *end note*]

- [(4.2)](#iterator.cust.swap-4.2)

  Otherwise, if the types of E1 and E2 each model[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]"), and if the reference types of E1 and E2 model [swappable_with](concept.swappable#concept:swappable_with "18.4.9 Concept swappable [concept.swappable]") ([[concept.swappable]](concept.swappable "18.4.9 Concept swappable")),
then ranges​::​swap(*E1, *E2)[.](#iterator.cust.swap-4.2.sentence-1)

- [(4.3)](#iterator.cust.swap-4.3)

  Otherwise, if the types T1 and T2 of E1 andE2 model [indirectly_movable_storable](#concept:indirectly_movable_storable "24.3.7.2 Concept indirectly_­movable [alg.req.ind.move]")<T1, T2> and[indirectly_movable_storable](#concept:indirectly_movable_storable "24.3.7.2 Concept indirectly_­movable [alg.req.ind.move]")<T2, T1>, then(void)(*E1 = *iter-exchange-move*(E2, E1)),
except that E1 is evaluated only once[.](#iterator.cust.swap-4.3.sentence-1)

- [(4.4)](#iterator.cust.swap-4.4)

  Otherwise, ranges​::​iter_swap(E1, E2) is ill-formed[.](#iterator.cust.swap-4.4.sentence-1)
  [*Note [2](#iterator.cust.swap-note-2)*:
  This case can result in substitution failure when ranges​::​iter_swap(E1, E2) appears in the immediate context of a template instantiation[.](#iterator.cust.swap-4.4.sentence-2)
 â *end note*]

### [24.3.4](#iterator.concepts) Iterator concepts [[iterator.concepts]](iterator.concepts)

#### [24.3.4.1](#iterator.concepts.general) General [[iterator.concepts.general]](iterator.concepts.general)

[1](#iterator.concepts.general-1)

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

For a type I, let *ITER_TRAITS*(I) denote
the type I if iterator_traits<I> names
a specialization generated from the primary template[.](#iterator.concepts.general-1.sentence-1)

Otherwise, *ITER_TRAITS*(I) denotesiterator_traits<I>[.](#iterator.concepts.general-1.sentence-2)

- [(1.1)](#iterator.concepts.general-1.1)

  If the [*qualified-id*](expr.prim.id.qual#nt:qualified-id "7.5.5.3 Qualified names [expr.prim.id.qual]")*ITER_TRAITS*(I)​::​iterator_concept is valid
 and names a type, then *ITER_CONCEPT*(I) denotes that
 type[.](#iterator.concepts.general-1.1.sentence-1)

- [(1.2)](#iterator.concepts.general-1.2)

  Otherwise, if the [*qualified-id*](expr.prim.id.qual#nt:qualified-id "7.5.5.3 Qualified names [expr.prim.id.qual]")*ITER_TRAITS*(I)​​::​iterator_category is valid and names a type, then *ITER_CONCEPT*(I) denotes that type[.](#iterator.concepts.general-1.2.sentence-1)

- [(1.3)](#iterator.concepts.general-1.3)

  Otherwise, if iterator_traits<I> names a specialization generated
 from the primary template, then *ITER_CONCEPT*(I) denotes random_access_iterator_tag[.](#iterator.concepts.general-1.3.sentence-1)

- [(1.4)](#iterator.concepts.general-1.4)

  Otherwise, *ITER_CONCEPT*(I) does not denote a type[.](#iterator.concepts.general-1.4.sentence-1)

[2](#iterator.concepts.general-2)

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

[*Note [1](#iterator.concepts.general-note-1)*:

*ITER_TRAITS* enables independent syntactic determination
of an iterator's category and concept[.](#iterator.concepts.general-2.sentence-1)

â *end note*]

[*Example [1](#iterator.concepts.general-example-1)*:

struct I {using value_type = int; using difference_type = int; int operator*() const;
 I& operator++();
 I operator++(int);
 I& operator--();
 I operator--(int); bool operator==(I) const;};iterator_traits<I>​::​iterator_category denotes input_iterator_tag,
and *ITER_CONCEPT*(I) denotes random_access_iterator_tag[.](#iterator.concepts.general-2.sentence-2)

â *end example*]

#### [24.3.4.2](#iterator.concept.readable) Concept indirectly_readable [[iterator.concept.readable]](iterator.concept.readable)

[1](#iterator.concept.readable-1)

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

Types that are indirectly readable by applying operator* model the [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") concept, including
pointers, smart pointers, and iterators[.](#iterator.concept.readable-1.sentence-1)

template<class In>concept [*indirectly-readable-impl*](#concept:indirectly-readable-impl "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") = // *exposition only*requires(const In in) {typename iter_value_t<In>; typename iter_reference_t<In>; typename iter_rvalue_reference_t<In>; { *in } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<iter_reference_t<In>>; { ranges::iter_move(in) } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<iter_rvalue_reference_t<In>>; } &&[common_reference_with](concept.commonref#concept:common_reference_with "18.4.5 Concept common_­reference_­with [concept.commonref]")<iter_reference_t<In>&&, iter_value_t<In>&> &&[common_reference_with](concept.commonref#concept:common_reference_with "18.4.5 Concept common_­reference_­with [concept.commonref]")<iter_reference_t<In>&&, iter_rvalue_reference_t<In>&&> &&[common_reference_with](concept.commonref#concept:common_reference_with "18.4.5 Concept common_­reference_­with [concept.commonref]")<iter_rvalue_reference_t<In>&&, const iter_value_t<In>&>;

template<class In>concept [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") =[*indirectly-readable-impl*](#concept:indirectly-readable-impl "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<remove_cvref_t<In>>;

[2](#iterator.concept.readable-2)

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

Given a value i of type I, I models [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") only if the expression *i is equality-preserving[.](#iterator.concept.readable-2.sentence-1)

#### [24.3.4.3](#iterator.concept.writable) Concept indirectly_writable [[iterator.concept.writable]](iterator.concept.writable)

[1](#iterator.concept.writable-1)

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

The [indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]") concept specifies the requirements
for writing a value into an iterator's referenced object[.](#iterator.concept.writable-1.sentence-1)

template<class Out, class T>concept [indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]") =requires(Out&& o, T&& t) {*o = std::forward<T>(t); // not required to be equality-preserving*std::forward<Out>(o) = std::forward<T>(t); // not required to be equality-preservingconst_cast<const iter_reference_t<Out>&&>(*o) = std::forward<T>(t); // not required to be equality-preservingconst_cast<const iter_reference_t<Out>&&>(*std::forward<Out>(o)) = std::forward<T>(t); // not required to be equality-preserving};

[2](#iterator.concept.writable-2)

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

Let E be an expression such that decltype((E)) is T,
and let o be a dereferenceable object of type Out[.](#iterator.concept.writable-2.sentence-1)

Out and T model [indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<Out, T> only if:

- [(2.1)](#iterator.concept.writable-2.1)

If Out and T model [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<Out> && [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<iter_value_t<Out>, decay_t<T>>,
 then *o after any above assignment is equal to
 the value of E before the assignment[.](#iterator.concept.writable-2.sentence-2)

[3](#iterator.concept.writable-3)

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

After evaluating any above assignment expression, o is not required to be dereferenceable[.](#iterator.concept.writable-3.sentence-1)

[4](#iterator.concept.writable-4)

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

If E is an xvalue ([[basic.lval]](basic.lval "7.2.1 Value category")), the resulting
state of the object it denotes is valid but unspecified ([[lib.types.movedfrom]](lib.types.movedfrom "16.4.6.17 Moved-from state of library types"))[.](#iterator.concept.writable-4.sentence-1)

[5](#iterator.concept.writable-5)

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

[*Note [1](#iterator.concept.writable-note-1)*:

The only valid use of an operator* is on the left side of the assignment statement[.](#iterator.concept.writable-5.sentence-1)

Assignment through the same value of the indirectly writable type happens only once[.](#iterator.concept.writable-5.sentence-2)

â *end note*]

[6](#iterator.concept.writable-6)

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

[*Note [2](#iterator.concept.writable-note-2)*:

[indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]") has the awkward const_cast expressions to reject
iterators with prvalue non-proxy reference types that permit rvalue
assignment but do not also permit const rvalue assignment[.](#iterator.concept.writable-6.sentence-1)

Consequently, an iterator type I that returns std​::​string by value does not model [indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<I, std​::​string>[.](#iterator.concept.writable-6.sentence-2)

â *end note*]

#### [24.3.4.4](#iterator.concept.winc) Concept weakly_incrementable [[iterator.concept.winc]](iterator.concept.winc)

[1](#iterator.concept.winc-1)

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

The [weakly_incrementable](#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") concept specifies the requirements on
types that can be incremented with the pre- and post-increment operators[.](#iterator.concept.winc-1.sentence-1)

The increment operations are not required to be equality-preserving,
nor is the type required to be [equality_comparable](concept.equalitycomparable#concept:equality_comparable "18.5.4 Concept equality_­comparable [concept.equalitycomparable]")[.](#iterator.concept.winc-1.sentence-2)

template<class T>constexpr bool *is-integer-like* = *see below*; // *exposition only*template<class T>constexpr bool *is-signed-integer-like* = *see below*; // *exposition only*template<class I>concept [weakly_incrementable](#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") =[movable](concepts.object#concept:movable "18.6 Object concepts [concepts.object]")<I> &&requires(I i) {typename iter_difference_t<I>; requires *is-signed-integer-like*<iter_difference_t<I>>; { ++i } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I&>; // not required to be equality-preserving i++; // not required to be equality-preserving};

[2](#iterator.concept.winc-2)

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

A type I is an [*integer-class type*](#def:type,integer-class "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") if it is in a set of implementation-defined types
that behave as integer types do, as defined below[.](#iterator.concept.winc-2.sentence-1)

[*Note [1](#iterator.concept.winc-note-1)*:

An integer-class type is not necessarily a class type[.](#iterator.concept.winc-2.sentence-2)

â *end note*]

[3](#iterator.concept.winc-3)

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

The range of representable values of an integer-class type
is the continuous set of values over which it is defined[.](#iterator.concept.winc-3.sentence-1)

For any integer-class type,
its range of representable values is
either â2Nâ1 to 2Nâ1â1 (inclusive) for some integer N,
in which case it is a [*signed-integer-class type*](#def:type,signed-integer-class "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]"), or0 to 2Nâ1 (inclusive) for some integer N,
in which case it is an [*unsigned-integer-class type*](#def:type,unsigned-integer-class "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]")[.](#iterator.concept.winc-3.sentence-2)

In both cases, N is called
the [*width*](#def:width,of_integer-class_type "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") of the integer-class type[.](#iterator.concept.winc-3.sentence-3)

The width of an integer-class type is greater than
that of every integral type of the same signedness[.](#iterator.concept.winc-3.sentence-4)

[4](#iterator.concept.winc-4)

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

A type I other than cv bool is [*integer-like*](#def:integer-like "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") if it models [integral](concepts.arithmetic#concept:integral "18.4.7 Arithmetic concepts [concepts.arithmetic]")<I> or
if it is an integer-class type[.](#iterator.concept.winc-4.sentence-1)

An integer-like type I is [*signed-integer-like*](#def:signed-integer-like "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") if it models [signed_integral](concepts.arithmetic#concept:signed_integral "18.4.7 Arithmetic concepts [concepts.arithmetic]")<I> or
if it is a signed-integer-class type[.](#iterator.concept.winc-4.sentence-2)

An integer-like type I is [*unsigned-integer-like*](#def:unsigned-integer-like "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") if it models [unsigned_integral](concepts.arithmetic#concept:unsigned_integral "18.4.7 Arithmetic concepts [concepts.arithmetic]")<I> or
if it is an unsigned-integer-class type[.](#iterator.concept.winc-4.sentence-3)

[5](#iterator.concept.winc-5)

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

For every integer-class type I,
let B(I) be a unique hypothetical extended integer type
of the same signedness with the same width ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types")) as I[.](#iterator.concept.winc-5.sentence-1)

[*Note [2](#iterator.concept.winc-note-2)*:

The corresponding hypothetical specialization numeric_limits<B(I)> meets the requirements on numeric_limits specializations
for integral types ([[numeric.limits]](numeric.limits "17.3.5 Class template numeric_­limits"))[.](#iterator.concept.winc-5.sentence-2)

â *end note*]

For every integral type J, let B(J) be the same type as J[.](#iterator.concept.winc-5.sentence-3)

[6](#iterator.concept.winc-6)

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

Expressions of integer-class type are
explicitly convertible to any integer-like type, and
implicitly convertible to any integer-class type
of equal or greater width and the same signedness[.](#iterator.concept.winc-6.sentence-1)

Expressions of integral type are
both implicitly and explicitly convertible to any integer-class type[.](#iterator.concept.winc-6.sentence-2)

Conversions between integral and integer-class types
and between two integer-class types do not exit via an exception[.](#iterator.concept.winc-6.sentence-3)

The result of such a conversion is the unique value of the destination type
that is congruent to the source modulo 2N,
where N is the width of the destination type[.](#iterator.concept.winc-6.sentence-4)

[7](#iterator.concept.winc-7)

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

Let a be an object of integer-class type I,
let b be an object of integer-like type I2 such that the expression b is implicitly convertible to I,
let x and y be, respectively,
objects of type B(I) and B(I2) as described above
that represent the same values as a and b, and
let c be an lvalue of any integral type[.](#iterator.concept.winc-7.sentence-1)

- [(7.1)](#iterator.concept.winc-7.1)

  The expressions a++ and a-- shall be prvalues of type I whose values are equal to
that of a prior to the evaluation of the expressions[.](#iterator.concept.winc-7.1.sentence-1)
  The expression a++ shall modify the value of a by adding 1 to it[.](#iterator.concept.winc-7.1.sentence-2)
  The expression a-- shall modify the value of a by subtracting 1 from it[.](#iterator.concept.winc-7.1.sentence-3)

- [(7.2)](#iterator.concept.winc-7.2)

  The expressions ++a, --a, and &a shall be
expression-equivalent toa += 1, a -= 1, and addressof(a), respectively[.](#iterator.concept.winc-7.2.sentence-1)

- [(7.3)](#iterator.concept.winc-7.3)

  For every [*unary-operator*](expr.unary.general#nt:unary-operator "7.6.2.1 General [expr.unary.general]") @ other than & for which the expression @x is well-formed, @a shall also be well-formed
 and have the same value, effects, and value category as @x[.](#iterator.concept.winc-7.3.sentence-1)
  If @x has type bool, so too does @a;
 if @x has type B(I), then @a has type I[.](#iterator.concept.winc-7.3.sentence-2)

- [(7.4)](#iterator.concept.winc-7.4)

  For every assignment operator @= for which c @= x is well-formed, c @= a shall also be well-formed and
 shall have the same value and effects as c @= x[.](#iterator.concept.winc-7.4.sentence-1)
  The expression c @= a shall be an lvalue referring to c[.](#iterator.concept.winc-7.4.sentence-2)

- [(7.5)](#iterator.concept.winc-7.5)

  For every assignment operator @= for which x @= y is well-formed,a @= b shall also be well-formed and
shall have the same effects as x @= y,
except that the value that would be stored into x is stored into a[.](#iterator.concept.winc-7.5.sentence-1)
  The expression a @= b shall be an lvalue referring to a[.](#iterator.concept.winc-7.5.sentence-2)

- [(7.6)](#iterator.concept.winc-7.6)

  For every non-assignment binary operator @ for which x @ y and y @ x are well-formed, a @ b and b @ a shall also be well-formed and
 shall have the same value, effects, and value category as x @ y and y @ x, respectively[.](#iterator.concept.winc-7.6.sentence-1)
  If x @ y or y @ x has type B(I),
 then a @ b or b @ a, respectively, has type I;
 if x @ y or y @ x has type B(I2),
 then a @ b or b @ a, respectively, has type I2;
 if x @ y or y @ x has any other type,
 then a @ b or b @ a, respectively, has that type[.](#iterator.concept.winc-7.6.sentence-2)

[8](#iterator.concept.winc-8)

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

An expression E of integer-class type I is
contextually convertible to bool as if by bool(E != I(0))[.](#iterator.concept.winc-8.sentence-1)

[9](#iterator.concept.winc-9)

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

All integer-class types model[regular](concepts.object#concept:regular "18.6 Object concepts [concepts.object]") ([[concepts.object]](concepts.object "18.6 Object concepts")) and[three_way_comparable](cmp.concept#concept:three_way_comparable "17.12.4 Concept three_­way_­comparable [cmp.concept]")<strong_ordering> ([[cmp.concept]](cmp.concept "17.12.4 Concept three_­way_­comparable"))[.](#iterator.concept.winc-9.sentence-1)

[10](#iterator.concept.winc-10)

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

A value-initialized object of integer-class type has value 0[.](#iterator.concept.winc-10.sentence-1)

[11](#iterator.concept.winc-11)

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

For every (possibly cv-qualified) integer-class type I,numeric_limits<I> is specialized such that
each static data member m has the same value as numeric_limits<B(I)>​::​m, and
each static member function f returns I(numeric_limits<B(I)>​::​f())[.](#iterator.concept.winc-11.sentence-1)

[12](#iterator.concept.winc-12)

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

For any two integer-like types I1 and I2,
at least one of which is an integer-class type,common_type_t<I1, I2> denotes an integer-class type
whose width is not less than that of I1 or I2[.](#iterator.concept.winc-12.sentence-1)

If both I1 and I2 are signed-integer-like types,
then common_type_t<I1, I2> is also a signed-integer-like type[.](#iterator.concept.winc-12.sentence-2)

[13](#iterator.concept.winc-13)

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

*is-integer-like*<I> is true if and only if I is an integer-like type[.](#iterator.concept.winc-13.sentence-1)

*is-signed-integer-like*<I> is true if and only if I is a signed-integer-like type[.](#iterator.concept.winc-13.sentence-2)

[14](#iterator.concept.winc-14)

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

Let i be an object of type I[.](#iterator.concept.winc-14.sentence-1)

When i is in the domain of
both pre- and post-increment, i is said to be [*incrementable*](#def:incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]")[.](#iterator.concept.winc-14.sentence-2)

I models [weakly_incrementable](#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]")<I> only if:

- [(14.1)](#iterator.concept.winc-14.1)

  The expressions ++i and i++ have the same domain[.](#iterator.concept.winc-14.1.sentence-1)

- [(14.2)](#iterator.concept.winc-14.2)

  If i is incrementable, then both ++i and i++ advance i to the next element[.](#iterator.concept.winc-14.2.sentence-1)

- [(14.3)](#iterator.concept.winc-14.3)

  If i is incrementable, then addressof(++i) is equal to addressof(i)[.](#iterator.concept.winc-14.3.sentence-1)

[15](#iterator.concept.winc-15)

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

*Recommended practice*: The implementation of an algorithm on a weakly incrementable type
should never attempt to pass through the same incrementable value twice;
such an algorithm should be a single-pass algorithm[.](#iterator.concept.winc-15.sentence-1)

[*Note [3](#iterator.concept.winc-note-3)*:

For [weakly_incrementable](#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") types, a equals b does not imply that ++a equals ++b[.](#iterator.concept.winc-15.sentence-2)

(Equality does not guarantee the substitution property or referential
transparency[.](#iterator.concept.winc-15.sentence-3))

Such algorithms
can be used with istreams as the source of the input data through the istream_iterator class
template[.](#iterator.concept.winc-15.sentence-4)

â *end note*]

#### [24.3.4.5](#iterator.concept.inc) Concept incrementable [[iterator.concept.inc]](iterator.concept.inc)

[1](#iterator.concept.inc-1)

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

The [incrementable](#concept:incrementable "24.3.4.5 Concept incrementable [iterator.concept.inc]") concept specifies requirements on types that can be incremented with the pre-
and post-increment operators[.](#iterator.concept.inc-1.sentence-1)

The increment operations are required to be equality-preserving,
and the type is required to be [equality_comparable](concept.equalitycomparable#concept:equality_comparable "18.5.4 Concept equality_­comparable [concept.equalitycomparable]")[.](#iterator.concept.inc-1.sentence-2)

[*Note [1](#iterator.concept.inc-note-1)*:

This supersedes the annotations on the increment expressions
in the definition of [weakly_incrementable](#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]")[.](#iterator.concept.inc-1.sentence-3)

â *end note*]

template<class I>concept [incrementable](#concept:incrementable "24.3.4.5 Concept incrementable [iterator.concept.inc]") =[regular](concepts.object#concept:regular "18.6 Object concepts [concepts.object]")<I> &&[weakly_incrementable](#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]")<I> &&requires(I i) {{ i++ } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I>; };

[2](#iterator.concept.inc-2)

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

Let a and b be incrementable objects of type I[.](#iterator.concept.inc-2.sentence-1)

I models [incrementable](#concept:incrementable "24.3.4.5 Concept incrementable [iterator.concept.inc]") only if:

- [(2.1)](#iterator.concept.inc-2.1)

  If bool(a == b) then bool(a++ == b)[.](#iterator.concept.inc-2.1.sentence-1)

- [(2.2)](#iterator.concept.inc-2.2)

  If bool(a == b) then bool(((void)a++, a) == ++b)[.](#iterator.concept.inc-2.2.sentence-1)

[3](#iterator.concept.inc-3)

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

[*Note [2](#iterator.concept.inc-note-2)*:

The requirement thata equals b implies++a equals ++b (which is not true for weakly incrementable types)
allows the use of multi-pass one-directional
algorithms with types that model [incrementable](#concept:incrementable "24.3.4.5 Concept incrementable [iterator.concept.inc]")[.](#iterator.concept.inc-3.sentence-1)

â *end note*]

#### [24.3.4.6](#iterator.concept.iterator) Concept input_or_output_iterator [[iterator.concept.iterator]](iterator.concept.iterator)

[1](#iterator.concept.iterator-1)

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

The [input_or_output_iterator](#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") concept forms the basis
of the iterator concept taxonomy; every iterator models [input_or_output_iterator](#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]")[.](#iterator.concept.iterator-1.sentence-1)

This concept specifies operations for dereferencing and incrementing
an iterator[.](#iterator.concept.iterator-1.sentence-2)

Most algorithms will require additional operations
to compare iterators with sentinels ([[iterator.concept.sentinel]](#iterator.concept.sentinel "24.3.4.7 Concept sentinel_­for")), to
read ([[iterator.concept.input]](#iterator.concept.input "24.3.4.9 Concept input_­iterator")) or write ([[iterator.concept.output]](#iterator.concept.output "24.3.4.10 Concept output_­iterator")) values, or
to provide a richer set of iterator movements ([[iterator.concept.forward]](#iterator.concept.forward "24.3.4.11 Concept forward_­iterator"), [[iterator.concept.bidir]](#iterator.concept.bidir "24.3.4.12 Concept bidirectional_­iterator"), [[iterator.concept.random.access]](#iterator.concept.random.access "24.3.4.13 Concept random_­access_­iterator"))[.](#iterator.concept.iterator-1.sentence-3)

template<class I>concept [input_or_output_iterator](#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") =requires(I i) {{ *i } -> [*can-reference*](iterator.synopsis#concept:can-reference "24.2 Header <iterator>&nbsp;synopsis [iterator.synopsis]"); } &&[weakly_incrementable](#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]")<I>;

[2](#iterator.concept.iterator-2)

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

[*Note [1](#iterator.concept.iterator-note-1)*:

Unlike the *Cpp17Iterator* requirements,
the [input_or_output_iterator](#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") concept does not require copyability[.](#iterator.concept.iterator-2.sentence-1)

â *end note*]

#### [24.3.4.7](#iterator.concept.sentinel) Concept sentinel_for [[iterator.concept.sentinel]](iterator.concept.sentinel)

[1](#iterator.concept.sentinel-1)

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

The [sentinel_for](#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") concept specifies the relationship
between an [input_or_output_iterator](#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") type and a [semiregular](concepts.object#concept:semiregular "18.6 Object concepts [concepts.object]") type
whose values denote a range[.](#iterator.concept.sentinel-1.sentence-1)

[ð](#concept:sentinel_for)

`template<class S, class I>
  concept [sentinel_for](#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]") =
    [semiregular](concepts.object#concept:semiregular "18.6 Object concepts [concepts.object]")<S> &&
    [input_or_output_iterator](#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]")<I> &&
    [weakly-equality-comparable-with](concept.equalitycomparable#concept:weakly-equality-comparable-with "18.5.4 Concept equality_­comparable [concept.equalitycomparable]")<S, I>;      // see [[concept.equalitycomparable]](concept.equalitycomparable "18.5.4 Concept equality_­comparable")
`

[2](#iterator.concept.sentinel-2)

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

Let s and i be values of type S andI such that [i, s) denotes a range[.](#iterator.concept.sentinel-2.sentence-1)

TypesS and I model [sentinel_for](#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<S, I> only if:

- [(2.1)](#iterator.concept.sentinel-2.1)

  i == s is well-defined[.](#iterator.concept.sentinel-2.1.sentence-1)

- [(2.2)](#iterator.concept.sentinel-2.2)

  If bool(i != s) then i is dereferenceable and
 [++i, s) denotes a range[.](#iterator.concept.sentinel-2.2.sentence-1)

- [(2.3)](#iterator.concept.sentinel-2.3)

  [assignable_from](concept.assignable#concept:assignable_from "18.4.8 Concept assignable_­from [concept.assignable]")<I&, S> is either modeled or not satisfied[.](#iterator.concept.sentinel-2.3.sentence-1)

[3](#iterator.concept.sentinel-3)

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

The domain of == is not static[.](#iterator.concept.sentinel-3.sentence-1)

Given an iterator i and sentinel s such that [i, s)
denotes a range and i != s, i and s are not required to
continue to denote a range after incrementing any other iterator equal
to i[.](#iterator.concept.sentinel-3.sentence-2)

Consequently, i == s is no longer required to be
well-defined[.](#iterator.concept.sentinel-3.sentence-3)

#### [24.3.4.8](#iterator.concept.sizedsentinel) Concept sized_sentinel_for [[iterator.concept.sizedsentinel]](iterator.concept.sizedsentinel)

[1](#iterator.concept.sizedsentinel-1)

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

The [sized_sentinel_for](#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") concept specifies
requirements on an [input_or_output_iterator](#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") type I and
a corresponding [sentinel_for](#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> that allow the use of the - operator to compute the distance
between them in constant time[.](#iterator.concept.sizedsentinel-1.sentence-1)

[ð](#concept:sized_sentinel_for)

`template<class S, class I>
  concept [sized_sentinel_for](#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") =
    [sentinel_for](#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<S, I> &&
    !disable_sized_sentinel_for<remove_cv_t<S>, remove_cv_t<I>> &&
    requires(const I& i, const S& s) {
      { s - i } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<iter_difference_t<I>>;
      { i - s } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<iter_difference_t<I>>;
    };
`

[2](#iterator.concept.sizedsentinel-2)

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

Let i be an iterator of type I, and s a sentinel of type S such that [i, s) denotes a range[.](#iterator.concept.sizedsentinel-2.sentence-1)

Let N be the smallest number of applications of ++i necessary to make bool(i == s) be true[.](#iterator.concept.sizedsentinel-2.sentence-2)

S and I model [sized_sentinel_for](#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<S, I> only if:

- [(2.1)](#iterator.concept.sizedsentinel-2.1)

  If N is representable by iter_difference_t<I>,
 then s - i is well-defined and equals N[.](#iterator.concept.sizedsentinel-2.1.sentence-1)

- [(2.2)](#iterator.concept.sizedsentinel-2.2)

  If âN is representable by iter_difference_t<I>,
 then i - s is well-defined and equals âN[.](#iterator.concept.sizedsentinel-2.2.sentence-1)

[ð](#lib:disable_sized_sentinel_for)

`template<class S, class I>
  constexpr bool disable_sized_sentinel_for = false;
`

[3](#iterator.concept.sizedsentinel-3)

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

*Remarks*: Pursuant to [[namespace.std]](namespace.std "16.4.5.2.1 Namespace std"),
users may specialize disable_sized_sentinel_for for cv-unqualified non-array object types S and I if S and/or I is a program-defined type[.](#iterator.concept.sizedsentinel-3.sentence-1)

Such specializations shall
be usable in constant expressions ([[expr.const]](expr.const "7.7 Constant expressions")) and
have type const bool[.](#iterator.concept.sizedsentinel-3.sentence-2)

[4](#iterator.concept.sizedsentinel-4)

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

[*Note [1](#iterator.concept.sizedsentinel-note-1)*:

disable_sized_sentinel_for allows use of sentinels and iterators with
the library that satisfy but do not in fact model [sized_sentinel_for](#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")[.](#iterator.concept.sizedsentinel-4.sentence-1)

â *end note*]

[5](#iterator.concept.sizedsentinel-5)

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

[*Example [1](#iterator.concept.sizedsentinel-example-1)*:

The [sized_sentinel_for](#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") concept is modeled by pairs of[random_access_iterator](#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]")s ([[iterator.concept.random.access]](#iterator.concept.random.access "24.3.4.13 Concept random_­access_­iterator")) and by
counted iterators and their sentinels ([[counted.iterator]](counted.iterator "24.5.7.1 Class template counted_­iterator"))[.](#iterator.concept.sizedsentinel-5.sentence-1)

â *end example*]

#### [24.3.4.9](#iterator.concept.input) Concept input_iterator [[iterator.concept.input]](iterator.concept.input)

[1](#iterator.concept.input-1)

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

The [input_iterator](#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") concept defines requirements for a type
whose referenced values can be read (from the requirement for[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") ([[iterator.concept.readable]](#iterator.concept.readable "24.3.4.2 Concept indirectly_­readable")))
and which can be both pre- and post-incremented[.](#iterator.concept.input-1.sentence-1)

[*Note [1](#iterator.concept.input-note-1)*:

Unlike the *Cpp17InputIterator* requirements ([[input.iterators]](#input.iterators "24.3.5.3 Input iterators")),
the [input_iterator](#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") concept does not need
equality comparison since iterators are typically compared to sentinels[.](#iterator.concept.input-1.sentence-2)

â *end note*]

template<class I>concept [input_iterator](#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") =[input_or_output_iterator](#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]")<I> &&[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<I> &&requires { typename *ITER_CONCEPT*(I); } &&[derived_from](concept.derived#concept:derived_from "18.4.3 Concept derived_­from [concept.derived]")<*ITER_CONCEPT*(I), input_iterator_tag>;

#### [24.3.4.10](#iterator.concept.output) Concept output_iterator [[iterator.concept.output]](iterator.concept.output)

[1](#iterator.concept.output-1)

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

The [output_iterator](#concept:output_iterator "24.3.4.10 Concept output_­iterator [iterator.concept.output]") concept defines requirements for a type that
can be used to write values (from the requirement for[indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]") ([[iterator.concept.writable]](#iterator.concept.writable "24.3.4.3 Concept indirectly_­writable")))
and which can be both pre- and post-incremented[.](#iterator.concept.output-1.sentence-1)

[*Note [1](#iterator.concept.output-note-1)*:

Output iterators are not required to model [equality_comparable](concept.equalitycomparable#concept:equality_comparable "18.5.4 Concept equality_­comparable [concept.equalitycomparable]")[.](#iterator.concept.output-1.sentence-2)

â *end note*]

template<class I, class T>concept [output_iterator](#concept:output_iterator "24.3.4.10 Concept output_­iterator [iterator.concept.output]") =[input_or_output_iterator](#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]")<I> &&[indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<I, T> &&requires(I i, T&& t) {*i++ = std::forward<T>(t); // not required to be equality-preserving};

[2](#iterator.concept.output-2)

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

Let E be an expression such that decltype((E)) is T, and let i be a
dereferenceable object of type I[.](#iterator.concept.output-2.sentence-1)

I and T model [output_iterator](#concept:output_iterator "24.3.4.10 Concept output_­iterator [iterator.concept.output]")<I, T> only if*i++ = E; has effects equivalent to:*i = E;++i;

[3](#iterator.concept.output-3)

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

*Recommended practice*: The implementation of an algorithm on output iterators
should never attempt to pass through the same iterator twice;
such an algorithm should be a single-pass algorithm[.](#iterator.concept.output-3.sentence-1)

#### [24.3.4.11](#iterator.concept.forward) Concept forward_iterator [[iterator.concept.forward]](iterator.concept.forward)

[1](#iterator.concept.forward-1)

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

The [forward_iterator](#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") concept adds
copyability, equality comparison, and
the multi-pass guarantee, specified below[.](#iterator.concept.forward-1.sentence-1)

template<class I>concept [forward_iterator](#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") =[input_iterator](#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]")<I> &&[derived_from](concept.derived#concept:derived_from "18.4.3 Concept derived_­from [concept.derived]")<*ITER_CONCEPT*(I), forward_iterator_tag> &&[incrementable](#concept:incrementable "24.3.4.5 Concept incrementable [iterator.concept.inc]")<I> &&[sentinel_for](#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I, I>;

[2](#iterator.concept.forward-2)

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

The domain of == for forward iterators is that of iterators over the same
underlying sequence[.](#iterator.concept.forward-2.sentence-1)

However, value-initialized iterators of the same type
may be compared and shall compare equal to other value-initialized iterators of the same type[.](#iterator.concept.forward-2.sentence-2)

[*Note [1](#iterator.concept.forward-note-1)*:

Value-initialized iterators behave as if they refer past the end of the same
empty sequence[.](#iterator.concept.forward-2.sentence-3)

â *end note*]

[3](#iterator.concept.forward-3)

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

Pointers and references obtained from a forward iterator into a range [i, s)
shall remain valid while [i, s) continues to denote a range[.](#iterator.concept.forward-3.sentence-1)

[4](#iterator.concept.forward-4)

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

Two dereferenceable iterators a and b of type X offer the [*multi-pass guarantee*](#def:multi-pass_guarantee "24.3.5.5 Forward iterators [forward.iterators]") if

- [(4.1)](#iterator.concept.forward-4.1)

a == b implies ++a == ++b and

- [(4.2)](#iterator.concept.forward-4.2)

the expression((void)[](X x){++x;}(a), *a) is equivalent to the expression *a[.](#iterator.concept.forward-4.sentence-1)

[5](#iterator.concept.forward-5)

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

[*Note [2](#iterator.concept.forward-note-2)*:

The requirement thata == b implies++a == ++b and the removal of the restrictions on the number of assignments through
a mutable iterator
(which applies to output iterators)
allow the use of multi-pass one-directional algorithms with forward iterators[.](#iterator.concept.forward-5.sentence-1)

â *end note*]

#### [24.3.4.12](#iterator.concept.bidir) Concept bidirectional_iterator [[iterator.concept.bidir]](iterator.concept.bidir)

[1](#iterator.concept.bidir-1)

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

The [bidirectional_iterator](#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") concept adds the ability
to move an iterator backward as well as forward[.](#iterator.concept.bidir-1.sentence-1)

template<class I>concept [bidirectional_iterator](#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") =[forward_iterator](#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]")<I> &&[derived_from](concept.derived#concept:derived_from "18.4.3 Concept derived_­from [concept.derived]")<*ITER_CONCEPT*(I), bidirectional_iterator_tag> &&requires(I i) {{ --i } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I&>; { i-- } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I>; };

[2](#iterator.concept.bidir-2)

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

A bidirectional iterator r is decrementable if and only if there exists some q such that++q == r[.](#iterator.concept.bidir-2.sentence-1)

Decrementable iterators r shall be in the domain of the expressions--r and r--[.](#iterator.concept.bidir-2.sentence-2)

[3](#iterator.concept.bidir-3)

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

Let a and b be equal objects of type I[.](#iterator.concept.bidir-3.sentence-1)

I models [bidirectional_iterator](#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") only if:

- [(3.1)](#iterator.concept.bidir-3.1)

If a and b are decrementable,
 then all of the following are true:
  * [(3.1.1)](#iterator.concept.bidir-3.1.1)

addressof(--a) == addressof(a)

  * [(3.1.2)](#iterator.concept.bidir-3.1.2)

bool(a-- == b)

  * [(3.1.3)](#iterator.concept.bidir-3.1.3)

after evaluating both a-- and --b, bool(a == b) is still true

  * [(3.1.4)](#iterator.concept.bidir-3.1.4)

bool(++(--a) == b)

- [(3.2)](#iterator.concept.bidir-3.2)

If a and b are incrementable, then bool(--(++a) == b)[.](#iterator.concept.bidir-3.sentence-2)

#### [24.3.4.13](#iterator.concept.random.access) Concept random_access_iterator [[iterator.concept.random.access]](iterator.concept.random.access)

[1](#iterator.concept.random.access-1)

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

The [random_access_iterator](#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") concept adds support for
constant-time advancement with +=, +, -=, and -,
as well as the computation of distance in constant time with -[.](#iterator.concept.random.access-1.sentence-1)

Random access iterators also support array notation via subscripting[.](#iterator.concept.random.access-1.sentence-2)

template<class I>concept [random_access_iterator](#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") =[bidirectional_iterator](#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]")<I> &&[derived_from](concept.derived#concept:derived_from "18.4.3 Concept derived_­from [concept.derived]")<*ITER_CONCEPT*(I), random_access_iterator_tag> &&[totally_ordered](concept.totallyordered#concept:totally_ordered "18.5.5 Concept totally_­ordered [concept.totallyordered]")<I> &&[sized_sentinel_for](#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<I, I> &&requires(I i, const I j, const iter_difference_t<I> n) {{ i += n } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I&>; { j + n } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I>; { n + j } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I>; { i -= n } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I&>; { j - n } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I>; { j[n] } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<iter_reference_t<I>>; };

[2](#iterator.concept.random.access-2)

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

Let a and b be valid iterators of type I such that b is reachable from a after n applications of ++a,
let D be iter_difference_t<I>,
and let n denote a value of type D[.](#iterator.concept.random.access-2.sentence-1)

I models [random_access_iterator](#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") only if:

- [(2.1)](#iterator.concept.random.access-2.1)

  (a += n) is equal to b[.](#iterator.concept.random.access-2.1.sentence-1)

- [(2.2)](#iterator.concept.random.access-2.2)

  addressof(a += n) is equal to addressof(a)[.](#iterator.concept.random.access-2.2.sentence-1)

- [(2.3)](#iterator.concept.random.access-2.3)

  (a + n) is equal to (a += n)[.](#iterator.concept.random.access-2.3.sentence-1)

- [(2.4)](#iterator.concept.random.access-2.4)

  For any two positive values x and y of type D,
 if (a + D(x + y)) is valid, then (a + D(x + y)) is equal to ((a + x) + y)[.](#iterator.concept.random.access-2.4.sentence-1)

- [(2.5)](#iterator.concept.random.access-2.5)

  (a + D(0)) is equal to a[.](#iterator.concept.random.access-2.5.sentence-1)

- [(2.6)](#iterator.concept.random.access-2.6)

  If (a + D(n - 1)) is valid, then (a + n) is equal to [](I c){ return ++c; }(a + D(n - 1))[.](#iterator.concept.random.access-2.6.sentence-1)

- [(2.7)](#iterator.concept.random.access-2.7)

  (b += D(-n)) is equal to a[.](#iterator.concept.random.access-2.7.sentence-1)

- [(2.8)](#iterator.concept.random.access-2.8)

  (b -= n) is equal to a[.](#iterator.concept.random.access-2.8.sentence-1)

- [(2.9)](#iterator.concept.random.access-2.9)

  addressof(b -= n) is equal to addressof(b)[.](#iterator.concept.random.access-2.9.sentence-1)

- [(2.10)](#iterator.concept.random.access-2.10)

  (b - n) is equal to (b -= n)[.](#iterator.concept.random.access-2.10.sentence-1)

- [(2.11)](#iterator.concept.random.access-2.11)

  If b is dereferenceable, then a[n] is valid and is equal to *b[.](#iterator.concept.random.access-2.11.sentence-1)

- [(2.12)](#iterator.concept.random.access-2.12)

  bool(a <= b) is true[.](#iterator.concept.random.access-2.12.sentence-1)

#### [24.3.4.14](#iterator.concept.contiguous) Concept contiguous_iterator [[iterator.concept.contiguous]](iterator.concept.contiguous)

[1](#iterator.concept.contiguous-1)

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

The [contiguous_iterator](#concept:contiguous_iterator "24.3.4.14 Concept contiguous_­iterator [iterator.concept.contiguous]") concept provides a guarantee that
the denoted elements are stored contiguously in memory[.](#iterator.concept.contiguous-1.sentence-1)

template<class I>concept [contiguous_iterator](#concept:contiguous_iterator "24.3.4.14 Concept contiguous_­iterator [iterator.concept.contiguous]") =[random_access_iterator](#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]")<I> &&[derived_from](concept.derived#concept:derived_from "18.4.3 Concept derived_­from [concept.derived]")<*ITER_CONCEPT*(I), contiguous_iterator_tag> && is_lvalue_reference_v<iter_reference_t<I>> &&[same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<iter_value_t<I>, remove_cvref_t<iter_reference_t<I>>> &&requires(const I& i) {{ to_address(i) } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<add_pointer_t<iter_reference_t<I>>>; };

[2](#iterator.concept.contiguous-2)

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

Let a and b be dereferenceable iterators andc be a non-dereferenceable iterator of type I such that b is reachable from a andc is reachable from b,
and let D be iter_difference_t<I>[.](#iterator.concept.contiguous-2.sentence-1)

The type I models [contiguous_iterator](#concept:contiguous_iterator "24.3.4.14 Concept contiguous_­iterator [iterator.concept.contiguous]") only if

- [(2.1)](#iterator.concept.contiguous-2.1)

to_address(a) == addressof(*a),

- [(2.2)](#iterator.concept.contiguous-2.2)

to_address(b) == to_address(a) + D(b - a),

- [(2.3)](#iterator.concept.contiguous-2.3)

to_address(c) == to_address(a) + D(c - a),

- [(2.4)](#iterator.concept.contiguous-2.4)

to_address(I{}) is well-defined,

- [(2.5)](#iterator.concept.contiguous-2.5)

ranges​::​iter_move(a) has
the same type, value category, and effects as std​::​move(*a), and

- [(2.6)](#iterator.concept.contiguous-2.6)

if ranges​::​iter_swap(a, b) is well-formed,
it has effects equivalent to ranges​::​swap(*a, *b)[.](#iterator.concept.contiguous-2.sentence-2)

### [24.3.5](#iterator.cpp17) C++17 iterator requirements [[iterator.cpp17]](iterator.cpp17)

#### [24.3.5.1](#iterator.cpp17.general) General [[iterator.cpp17.general]](iterator.cpp17.general)

[1](#iterator.cpp17.general-1)

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

In the following sections,a andb denote values of typeX or const X,difference_type and reference refer to the
types iterator_traits<X>​::​difference_type anditerator_traits<X>​::​reference, respectively,n denotes a value ofdifference_type,u,tmp,
andm denote identifiers,r denotes a value ofX&,t denotes a value of value typeT,o denotes a value of some type that is writable to the output iterator[.](#iterator.cpp17.general-1.sentence-1)

[*Note [1](#iterator.cpp17.general-note-1)*:

For an iterator type X there must be an instantiation
of iterator_traits<X> ([[iterator.traits]](#iterator.traits "24.3.2.3 Iterator traits"))[.](#iterator.cpp17.general-1.sentence-2)

â *end note*]

#### [24.3.5.2](#iterator.iterators) *Cpp17Iterator* [[iterator.iterators]](iterator.iterators)

[1](#iterator.iterators-1)

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

The *Cpp17Iterator* requirements form the basis of the iterator
taxonomy; every iterator meets the *Cpp17Iterator* requirements[.](#iterator.iterators-1.sentence-1)

This
set of requirements specifies operations for dereferencing and incrementing
an iterator[.](#iterator.iterators-1.sentence-2)

Most algorithms will require additional operations to
read ([[input.iterators]](#input.iterators "24.3.5.3 Input iterators")) or write ([[output.iterators]](#output.iterators "24.3.5.4 Output iterators")) values, or
to provide a richer set of iterator movements ([[forward.iterators]](#forward.iterators "24.3.5.5 Forward iterators"), [[bidirectional.iterators]](#bidirectional.iterators "24.3.5.6 Bidirectional iterators"), [[random.access.iterators]](#random.access.iterators "24.3.5.7 Random access iterators"))[.](#iterator.iterators-1.sentence-3)

[2](#iterator.iterators-2)

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

A type X meets the *Cpp17Iterator* requirements if

- [(2.1)](#iterator.iterators-2.1)

X meets the *Cpp17CopyConstructible*, *Cpp17CopyAssignable*, *Cpp17Swappable*, and*Cpp17Destructible* requirements ([[utility.arg.requirements]](utility.arg.requirements "16.4.4.2 Template argument requirements"), [[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")), and

- [(2.2)](#iterator.iterators-2.2)

iterator_traits<X>​::​difference_type is a signed integer type or void, and

- [(2.3)](#iterator.iterators-2.3)

the expressions in Table [78](#tab:iterator "Table 78: Cpp17Iterator requirements") are valid and have
the indicated semantics[.](#iterator.iterators-2.sentence-1)

Table [78](#tab:iterator) — *Cpp17Iterator* requirements [[tab:iterator]](./tab:iterator)  

| [ð](#tab:iterator-row-1)<br>**Expression** | **Return type** | **Operational** | **Assertion/note** |
| --- | --- | --- | --- |
| [ð](#tab:iterator-row-2) |  | **semantics** | **pre-/post-condition** |
| [ð](#tab:iterator-row-3)<br>*r | unspecified |  | *Preconditions*: r is dereferenceable[.](#tab:iterator-row-3-column-4-sentence-1) |
| [ð](#tab:iterator-row-4)<br>++r | X& |  |  |

#### [24.3.5.3](#input.iterators) Input iterators [[input.iterators]](input.iterators)

[1](#input.iterators-1)

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

A class or pointer typeX meets the requirements of an input iterator for the value typeT ifX meets the *Cpp17Iterator* ([[iterator.iterators]](#iterator.iterators "24.3.5.2 Cpp17Iterator")) and*Cpp17EqualityComparable* (Table [28](utility.arg.requirements#tab:cpp17.equalitycomparable "Table 28: Cpp17EqualityComparable requirements")) requirements and
the expressions in Table [79](#tab:inputiterator "Table 79: Cpp17InputIterator requirements (in addition to Cpp17Iterator)") are valid and have
the indicated semantics[.](#input.iterators-1.sentence-1)

[2](#input.iterators-2)

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

In Table [79](#tab:inputiterator "Table 79: Cpp17InputIterator requirements (in addition to Cpp17Iterator)"), the term[*the domain of ==*](#def:the_domain_of_==) is used in the ordinary mathematical sense to denote
the set of values over which== is (required to be) defined[.](#input.iterators-2.sentence-1)

This set can change over time[.](#input.iterators-2.sentence-2)

Each algorithm places additional requirements on the domain of== for the iterator values it uses[.](#input.iterators-2.sentence-3)

These requirements can be inferred from the uses that algorithm
makes of == and !=[.](#input.iterators-2.sentence-4)

[*Example [1](#input.iterators-example-1)*:

The call find(a,b,x) is defined only if the value of a has the property *p* defined as follows:b has property *p* and a value i has property *p* if
(*i==x)
or if
(*i!=x and++i has property*p*)[.](#input.iterators-2.sentence-5)

â *end example*]

Table [79](#tab:inputiterator) — *Cpp17InputIterator* requirements (in addition to *Cpp17Iterator*) [[tab:inputiterator]](./tab:inputiterator)  

| [ð](#tab:inputiterator-row-1)<br>**Expression** | **Return type** | **Operational** | **Assertion/note** |
| --- | --- | --- | --- |
| [ð](#tab:inputiterator-row-2) |  | **semantics** | **pre-/post-condition** |
| [ð](#tab:inputiterator-row-3)<br>a != b | decltype(a != b) models *boolean-testable* | !(a == b) | *Preconditions*: (a, b) is in the domain of ==[.](#tab:inputiterator-row-3-column-4-sentence-1) |
| [ð](#tab:inputiterator-row-4)<br>*a | reference, convertible to T |  | *Preconditions*: a is dereferenceable[.](#tab:inputiterator-row-4-column-4-sentence-1)<br>   The expression   (void)*a, *a is equivalent to *a[.](#tab:inputiterator-row-4-column-4-sentence-2)<br>   If a == b and (a, b) is in the domain of ==  then *a is equivalent to *b[.](#tab:inputiterator-row-4-column-4-sentence-3) |
| [ð](#tab:inputiterator-row-5)<br>a->m |  | (*a).m | *Preconditions*: a is dereferenceable[.](#tab:inputiterator-row-5-column-4-sentence-1) |
| [ð](#tab:inputiterator-row-6)<br>++r | X& |  | *Preconditions*: r is dereferenceable[.](#tab:inputiterator-row-6-column-4-sentence-1)<br>   *Postconditions*: r is dereferenceable or r is past-the-end;   any copies of the previous value of r are no longer  required to be dereferenceable nor to be in the domain of ==[.](#tab:inputiterator-row-6-column-4-sentence-2) |
| [ð](#tab:inputiterator-row-7)<br>(void)r++ |  |  | equivalent to (void)++r |
| [ð](#tab:inputiterator-row-8)<br>*r++ | convertible to T | { T tmp = *r;   ++r;   return tmp; } |  |

[3](#input.iterators-3)

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

*Recommended practice*: The implementation of an algorithm on input iterators
should never attempt to pass through the same iterator twice;
such an algorithm should be a single pass algorithm[.](#input.iterators-3.sentence-1)

[*Note [1](#input.iterators-note-1)*:

For input iterators, a == b does not imply ++a == ++b[.](#input.iterators-3.sentence-2)

(Equality does not guarantee the substitution property or referential transparency[.](#input.iterators-3.sentence-3))

Value type T is not required to be a *Cpp17CopyAssignable* type (Table [34](utility.arg.requirements#tab:cpp17.copyassignable "Table 34: Cpp17CopyAssignable requirements (in addition to Cpp17MoveAssignable)"))[.](#input.iterators-3.sentence-4)

Such an algorithm can be used with istreams as the source of the input data through theistream_iterator class template[.](#input.iterators-3.sentence-5)

â *end note*]

#### [24.3.5.4](#output.iterators) Output iterators [[output.iterators]](output.iterators)

[1](#output.iterators-1)

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

A class or pointer typeX meets the requirements of an output iterator
if X meets the *Cpp17Iterator* requirements ([[iterator.iterators]](#iterator.iterators "24.3.5.2 Cpp17Iterator"))
and the expressions in Table [80](#tab:outputiterator "Table 80: Cpp17OutputIterator requirements (in addition to Cpp17Iterator)") are valid and have the indicated semantics[.](#output.iterators-1.sentence-1)

Table [80](#tab:outputiterator) — *Cpp17OutputIterator* requirements (in addition to *Cpp17Iterator*) [[tab:outputiterator]](./tab:outputiterator)  

| [ð](#tab:outputiterator-row-1)<br>**Expression** | **Return type** | **Operational** | **Assertion/note** |
| --- | --- | --- | --- |
| [ð](#tab:outputiterator-row-2) |  | **semantics** | **pre-/post-condition** |
| [ð](#tab:outputiterator-row-3)<br>*r = o | result is not used |  | *Remarks*: After this operation r is not required to be dereferenceable[.](#tab:outputiterator-row-3-column-4-sentence-1)<br>   *Postconditions*: r is incrementable[.](#tab:outputiterator-row-3-column-4-sentence-2) |
| [ð](#tab:outputiterator-row-4)<br>++r | X& |  | addressof(r) == addressof(++r)[.](#tab:outputiterator-row-4-column-4-sentence-1)<br>   *Remarks*: After this operation r is not required to be dereferenceable[.](#tab:outputiterator-row-4-column-4-sentence-2)<br>   *Postconditions*: r is incrementable[.](#tab:outputiterator-row-4-column-4-sentence-3) |
| [ð](#tab:outputiterator-row-5)<br>r++ | convertible to const X& | { X tmp = r;    ++r;    return tmp; } | *Remarks*: After this operation r is not required to be dereferenceable[.](#tab:outputiterator-row-5-column-4-sentence-1)<br>   *Postconditions*: r is incrementable[.](#tab:outputiterator-row-5-column-4-sentence-2) |
| [ð](#tab:outputiterator-row-6)<br>*r++ = o | result is not used |  | *Remarks*: After this operation r is not required to be dereferenceable[.](#tab:outputiterator-row-6-column-4-sentence-1)<br>   *Postconditions*: r is incrementable[.](#tab:outputiterator-row-6-column-4-sentence-2) |

[2](#output.iterators-2)

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

*Recommended practice*: The implementation of an algorithm on output iterators
should never attempt to pass through the same iterator twice;
such an algorithm should be a single-pass algorithm[.](#output.iterators-2.sentence-1)

[*Note [1](#output.iterators-note-1)*:

The only valid use of an operator* is on the left side of the assignment statement[.](#output.iterators-2.sentence-2)

Assignment through the same value of the iterator happens only once[.](#output.iterators-2.sentence-3)

Equality and inequality are not necessarily defined[.](#output.iterators-2.sentence-4)

â *end note*]

#### [24.3.5.5](#forward.iterators) Forward iterators [[forward.iterators]](forward.iterators)

[1](#forward.iterators-1)

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

A class or pointer typeX meets the *Cpp17ForwardIterator* requirements if

- [(1.1)](#forward.iterators-1.1)

X meets the *Cpp17InputIterator* requirements ([[input.iterators]](#input.iterators "24.3.5.3 Input iterators")),

- [(1.2)](#forward.iterators-1.2)

X meets the *Cpp17DefaultConstructible* requirements ([[utility.arg.requirements]](utility.arg.requirements "16.4.4.2 Template argument requirements")),

- [(1.3)](#forward.iterators-1.3)

if X is a mutable iterator, reference is a reference to T;
if X is a constant iterator, reference is a reference to const T,

- [(1.4)](#forward.iterators-1.4)

the expressions in Table [81](#tab:forwarditerator "Table 81: Cpp17ForwardIterator requirements (in addition to Cpp17InputIterator)") are valid and have the indicated semantics, and

- [(1.5)](#forward.iterators-1.5)

objects of type X offer the multi-pass guarantee, described below[.](#forward.iterators-1.sentence-1)

[2](#forward.iterators-2)

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

The domain of == for forward iterators is that of iterators over the same
underlying sequence[.](#forward.iterators-2.sentence-1)

However, value-initialized iterators may be compared and
shall compare equal to other value-initialized iterators of the same type[.](#forward.iterators-2.sentence-2)

[*Note [1](#forward.iterators-note-1)*:

Value-initialized iterators behave as if they refer past the end of
the same empty sequence[.](#forward.iterators-2.sentence-3)

â *end note*]

[3](#forward.iterators-3)

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

Two dereferenceable iterators a and b of type X offer the[*multi-pass guarantee*](#def:multi-pass_guarantee "24.3.5.5 Forward iterators [forward.iterators]") if

- [(3.1)](#forward.iterators-3.1)

a == b implies ++a == ++b and

- [(3.2)](#forward.iterators-3.2)

X is a pointer type or the expression(void)++X(a), *a is equivalent to the expression *a[.](#forward.iterators-3.sentence-1)

[4](#forward.iterators-4)

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

[*Note [2](#forward.iterators-note-2)*:

The requirement thata == b implies++a == ++b (which is not true for input and output iterators)
and the removal of the restrictions on the number of the assignments through
a mutable iterator
(which applies to output iterators)
allows the use of multi-pass one-directional algorithms with forward iterators[.](#forward.iterators-4.sentence-1)

â *end note*]

Table [81](#tab:forwarditerator) — *Cpp17ForwardIterator* requirements (in addition to *Cpp17InputIterator*) [[tab:forwarditerator]](./tab:forwarditerator)  

| [ð](#tab:forwarditerator-row-1)<br>**Expression** | **Return type** | **Operational** | **Assertion/note** |
| --- | --- | --- | --- |
| [ð](#tab:forwarditerator-row-2) |  | **semantics** | **pre-/post-condition** |
| [ð](#tab:forwarditerator-row-3)<br>r++ | convertible to const X& | { X tmp = r;    ++r;    return tmp; } |  |
| [ð](#tab:forwarditerator-row-4)<br>*r++ | reference |  |  |

[5](#forward.iterators-5)

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

If a and b are equal, then either a and b are both dereferenceable
or else neither is dereferenceable[.](#forward.iterators-5.sentence-1)

[6](#forward.iterators-6)

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

If a and b are both dereferenceable, then a == b if and only if*a and *b are bound to the same object[.](#forward.iterators-6.sentence-1)

#### [24.3.5.6](#bidirectional.iterators) Bidirectional iterators [[bidirectional.iterators]](bidirectional.iterators)

[1](#bidirectional.iterators-1)

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

A class or pointer typeX meets the requirements of a bidirectional iterator if,
in addition to meeting the *Cpp17ForwardIterator* requirements,
the following expressions are valid as shown in Table [82](#tab:bidirectionaliterator "Table 82: Cpp17BidirectionalIterator requirements (in addition to Cpp17ForwardIterator)")[.](#bidirectional.iterators-1.sentence-1)

Table [82](#tab:bidirectionaliterator) — *Cpp17BidirectionalIterator* requirements (in addition to *Cpp17ForwardIterator*) [[tab:bidirectionaliterator]](./tab:bidirectionaliterator)  

| [ð](#tab:bidirectionaliterator-row-1)<br>**Expression** | **Return type** | **Operational** | **Assertion/note** |
| --- | --- | --- | --- |
| [ð](#tab:bidirectionaliterator-row-2) |  | **semantics** | **pre-/post-condition** |
| [ð](#tab:bidirectionaliterator-row-3)<br>--r | X& |  | *Preconditions*: there exists s such that r == ++s[.](#tab:bidirectionaliterator-row-3-column-4-sentence-1)<br>   *Postconditions*: r is dereferenceable[.](#tab:bidirectionaliterator-row-3-column-4-sentence-2)<br>   --(++r) == r[.](#tab:bidirectionaliterator-row-3-column-4-sentence-3)<br>   --r == --s implies r == s[.](#tab:bidirectionaliterator-row-3-column-4-sentence-4)<br>   addressof(r) == addressof(--r)[.](#tab:bidirectionaliterator-row-3-column-4-sentence-5) |
| [ð](#tab:bidirectionaliterator-row-4)<br>r-- | convertible to const X& | { X tmp = r;    --r;    return tmp; } |  |
| [ð](#tab:bidirectionaliterator-row-5)<br>*r-- | reference |  |  |

[2](#bidirectional.iterators-2)

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

[*Note [1](#bidirectional.iterators-note-1)*:

Bidirectional iterators allow algorithms to move iterators backward as well as forward[.](#bidirectional.iterators-2.sentence-1)

â *end note*]

#### [24.3.5.7](#random.access.iterators) Random access iterators [[random.access.iterators]](random.access.iterators)

[1](#random.access.iterators-1)

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

A class or pointer typeX meets the requirements of a random access iterator if,
in addition to meeting the *Cpp17BidirectionalIterator* requirements,
the following expressions are valid as shown in Table [83](#tab:randomaccessiterator "Table 83: Cpp17RandomAccessIterator requirements (in addition to Cpp17BidirectionalIterator)")[.](#random.access.iterators-1.sentence-1)

Table [83](#tab:randomaccessiterator) — *Cpp17RandomAccessIterator* requirements (in addition to *Cpp17BidirectionalIterator*) [[tab:randomaccessiterator]](./tab:randomaccessiterator)  

| [ð](#tab:randomaccessiterator-row-1)<br>**Expression** | **Return type** | **Operational** | **Assertion/note** |
| --- | --- | --- | --- |
| [ð](#tab:randomaccessiterator-row-2) |  | **semantics** | **pre-/post-condition** |
| [ð](#tab:randomaccessiterator-row-3)<br>r += n | X& | { difference_type m = n;    if (m >= 0)    while (m--)    ++r;    else    while (m++)    --r;    return r; } |  |
| [ð](#tab:randomaccessiterator-row-4)<br>a + n   n + a | X | { X tmp = a;    return tmp += n; } | a + n == n + a[.](#tab:randomaccessiterator-row-4-column-4-sentence-1) |
| [ð](#tab:randomaccessiterator-row-5)<br>r -= n | X& | return r += -n; | *Preconditions*: the absolute value of n is in the range of  representable values of difference_type[.](#tab:randomaccessiterator-row-5-column-4-sentence-1) |
| [ð](#tab:randomaccessiterator-row-6)<br>a - n | X | { X tmp = a;    return tmp -= n; } |  |
| [ð](#tab:randomaccessiterator-row-7)<br>b - a | difference_type | return n; | *Preconditions*: there exists a value n of type difference_type such that a + n == b[.](#tab:randomaccessiterator-row-7-column-4-sentence-1)<br>   b == a + (b - a)[.](#tab:randomaccessiterator-row-7-column-4-sentence-2) |
| [ð](#tab:randomaccessiterator-row-8)<br>a[n] | convertible to reference | *(a + n) |  |
| [ð](#tab:randomaccessiterator-row-9)<br>a < b | decltype(a < b) models *boolean-testable* | *Effects*: Equivalent to: return b - a > 0; | < is a total ordering relation |
| [ð](#tab:randomaccessiterator-row-10)<br>a > b | decltype(a > b) models *boolean-testable* | b < a | > is a total ordering relation opposite to <[.](#tab:randomaccessiterator-row-10-column-4-sentence-1) |
| [ð](#tab:randomaccessiterator-row-11)<br>a >= b | decltype(a >= b) models *boolean-testable* | !(a < b) |  |
| [ð](#tab:randomaccessiterator-row-12)<br>a <= b | decltype(a <= b) models *boolean-testable* | !(a > b) |  |

### [24.3.6](#indirectcallable) Indirect callable requirements [[indirectcallable]](indirectcallable)

#### [24.3.6.1](#indirectcallable.general) General [[indirectcallable.general]](indirectcallable.general)

[1](#indirectcallable.general-1)

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

There are several concepts that group requirements of algorithms that
take callable objects ([[func.def]](func.def "22.10.3 Definitions")) as arguments[.](#indirectcallable.general-1.sentence-1)

#### [24.3.6.2](#indirectcallable.traits) Indirect callable traits [[indirectcallable.traits]](indirectcallable.traits)

[1](#indirectcallable.traits-1)

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

To implement algorithms taking projections,
it is necessary to determine the projected type of an iterator's value type[.](#indirectcallable.traits-1.sentence-1)

For the exposition-only alias template *indirect-value-t*,*indirect-value-t*<T> denotes

- [(1.1)](#indirectcallable.traits-1.1)

invoke_result_t<Proj&, *indirect-value-t*<I>> if T names projected<I, Proj>, and

- [(1.2)](#indirectcallable.traits-1.2)

iter_value_t<T>& otherwise[.](#indirectcallable.traits-1.sentence-2)

#### [24.3.6.3](#indirectcallable.indirectinvocable) Indirect callables [[indirectcallable.indirectinvocable]](indirectcallable.indirectinvocable)

[1](#indirectcallable.indirectinvocable-1)

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

The indirect callable concepts are used to constrain those algorithms
that accept callable objects ([[func.def]](func.def "22.10.3 Definitions")) as arguments[.](#indirectcallable.indirectinvocable-1.sentence-1)

namespace std {template<class F, class I>concept [indirectly_unary_invocable](#concept:indirectly_unary_invocable "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]") =[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<I> &&[copy_constructible](concept.copyconstructible#concept:copy_constructible "18.4.14 Concept copy_­constructible [concept.copyconstructible]")<F> &&[invocable](concept.invocable#concept:invocable "18.7.2 Concept invocable [concept.invocable]")<F&, *indirect-value-t*<I>> &&[invocable](concept.invocable#concept:invocable "18.7.2 Concept invocable [concept.invocable]")<F&, iter_reference_t<I>> &&[common_reference_with](concept.commonref#concept:common_reference_with "18.4.5 Concept common_­reference_­with [concept.commonref]")< invoke_result_t<F&, *indirect-value-t*<I>>,
 invoke_result_t<F&, iter_reference_t<I>>>; template<class F, class I>concept [indirectly_regular_unary_invocable](#concept:indirectly_regular_unary_invocable "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]") =[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<I> &&[copy_constructible](concept.copyconstructible#concept:copy_constructible "18.4.14 Concept copy_­constructible [concept.copyconstructible]")<F> &&[regular_invocable](concept.regularinvocable#concept:regular_invocable "18.7.3 Concept regular_­invocable [concept.regularinvocable]")<F&, *indirect-value-t*<I>> &&[regular_invocable](concept.regularinvocable#concept:regular_invocable "18.7.3 Concept regular_­invocable [concept.regularinvocable]")<F&, iter_reference_t<I>> &&[common_reference_with](concept.commonref#concept:common_reference_with "18.4.5 Concept common_­reference_­with [concept.commonref]")< invoke_result_t<F&, *indirect-value-t*<I>>,
 invoke_result_t<F&, iter_reference_t<I>>>; template<class F, class I>concept [indirect_unary_predicate](#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]") =[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<I> &&[copy_constructible](concept.copyconstructible#concept:copy_constructible "18.4.14 Concept copy_­constructible [concept.copyconstructible]")<F> &&[predicate](concept.predicate#concept:predicate "18.7.4 Concept predicate [concept.predicate]")<F&, *indirect-value-t*<I>> &&[predicate](concept.predicate#concept:predicate "18.7.4 Concept predicate [concept.predicate]")<F&, iter_reference_t<I>>; template<class F, class I1, class I2>concept [indirect_binary_predicate](#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]") =[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<I1> && [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<I2> &&[copy_constructible](concept.copyconstructible#concept:copy_constructible "18.4.14 Concept copy_­constructible [concept.copyconstructible]")<F> &&[predicate](concept.predicate#concept:predicate "18.7.4 Concept predicate [concept.predicate]")<F&, *indirect-value-t*<I1>, *indirect-value-t*<I2>> &&[predicate](concept.predicate#concept:predicate "18.7.4 Concept predicate [concept.predicate]")<F&, *indirect-value-t*<I1>, iter_reference_t<I2>> &&[predicate](concept.predicate#concept:predicate "18.7.4 Concept predicate [concept.predicate]")<F&, iter_reference_t<I1>, *indirect-value-t*<I2>> &&[predicate](concept.predicate#concept:predicate "18.7.4 Concept predicate [concept.predicate]")<F&, iter_reference_t<I1>, iter_reference_t<I2>>; template<class F, class I1, class I2 = I1>concept [indirect_equivalence_relation](#concept:indirect_equivalence_relation "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]") =[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<I1> && [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<I2> &&[copy_constructible](concept.copyconstructible#concept:copy_constructible "18.4.14 Concept copy_­constructible [concept.copyconstructible]")<F> &&[equivalence_relation](concept.equiv#concept:equivalence_relation "18.7.6 Concept equivalence_­relation [concept.equiv]")<F&, *indirect-value-t*<I1>, *indirect-value-t*<I2>> &&[equivalence_relation](concept.equiv#concept:equivalence_relation "18.7.6 Concept equivalence_­relation [concept.equiv]")<F&, *indirect-value-t*<I1>, iter_reference_t<I2>> &&[equivalence_relation](concept.equiv#concept:equivalence_relation "18.7.6 Concept equivalence_­relation [concept.equiv]")<F&, iter_reference_t<I1>, *indirect-value-t*<I2>> &&[equivalence_relation](concept.equiv#concept:equivalence_relation "18.7.6 Concept equivalence_­relation [concept.equiv]")<F&, iter_reference_t<I1>, iter_reference_t<I2>>; template<class F, class I1, class I2 = I1>concept [indirect_strict_weak_order](#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]") =[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<I1> && [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<I2> &&[copy_constructible](concept.copyconstructible#concept:copy_constructible "18.4.14 Concept copy_­constructible [concept.copyconstructible]")<F> &&[strict_weak_order](concept.strictweakorder#concept:strict_weak_order "18.7.7 Concept strict_­weak_­order [concept.strictweakorder]")<F&, *indirect-value-t*<I1>, *indirect-value-t*<I2>> &&[strict_weak_order](concept.strictweakorder#concept:strict_weak_order "18.7.7 Concept strict_­weak_­order [concept.strictweakorder]")<F&, *indirect-value-t*<I1>, iter_reference_t<I2>> &&[strict_weak_order](concept.strictweakorder#concept:strict_weak_order "18.7.7 Concept strict_­weak_­order [concept.strictweakorder]")<F&, iter_reference_t<I1>, *indirect-value-t*<I2>> &&[strict_weak_order](concept.strictweakorder#concept:strict_weak_order "18.7.7 Concept strict_­weak_­order [concept.strictweakorder]")<F&, iter_reference_t<I1>, iter_reference_t<I2>>;}

#### [24.3.6.4](#projected) Alias template projected [[projected]](projected)

[1](#projected-1)

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

Alias template projected is used to constrain algorithms
that accept callable objects and projections ([[defns.projection]](defns.projection "3.44 projection"))[.](#projected-1.sentence-1)

It combines an [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") type I and
a callable object type Proj into a new [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") type
whose reference type is the result of applyingProj to the iter_reference_t of I[.](#projected-1.sentence-2)

[ð](#lib:projected)

namespace std {template<class I, class Proj>struct *projected-impl* { // *exposition only*struct *type* { // *exposition only*using value_type = remove_cvref_t<indirect_result_t<Proj&, I>>; using difference_type = iter_difference_t<I>; // present only if I// models [weakly_incrementable](#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") indirect_result_t<Proj&, I> operator*() const; // *not defined*}; }; template<[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") I, [indirectly_regular_unary_invocable](#concept:indirectly_regular_unary_invocable "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<I> Proj>using projected = *projected-impl*<I, Proj>::*type*;}

### [24.3.7](#alg.req) Common algorithm requirements [[alg.req]](alg.req)

#### [24.3.7.1](#alg.req.general) General [[alg.req.general]](alg.req.general)

[1](#alg.req.general-1)

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

There are several additional iterator concepts that are commonly applied
to families of algorithms[.](#alg.req.general-1.sentence-1)

These group together iterator requirements
of algorithm families[.](#alg.req.general-1.sentence-2)

There are three relational concepts that specify
how element values are transferred between[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") and [indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]") types:[indirectly_movable](#concept:indirectly_movable "24.3.7.2 Concept indirectly_­movable [alg.req.ind.move]"),[indirectly_copyable](#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]"), and[indirectly_swappable](#concept:indirectly_swappable "24.3.7.4 Concept indirectly_­swappable [alg.req.ind.swap]")[.](#alg.req.general-1.sentence-3)

There are three relational concepts for rearrangements:[permutable](#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]"),[mergeable](#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]"), and[sortable](#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]")[.](#alg.req.general-1.sentence-4)

There is one relational concept for comparing values from different sequences:[indirectly_comparable](#concept:indirectly_comparable "24.3.7.5 Concept indirectly_­comparable [alg.req.ind.cmp]")[.](#alg.req.general-1.sentence-5)

[2](#alg.req.general-2)

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

[*Note [1](#alg.req.general-note-1)*:

The ranges​::​less function object type
used in the concepts below imposes constraints on the concepts' arguments
in addition to those that appear in the concepts' bodies ([[range.cmp]](range.cmp "22.10.9 Concept-constrained comparisons"))[.](#alg.req.general-2.sentence-1)

â *end note*]

#### [24.3.7.2](#alg.req.ind.move) Concept indirectly_movable [[alg.req.ind.move]](alg.req.ind.move)

[1](#alg.req.ind.move-1)

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

The [indirectly_movable](#concept:indirectly_movable "24.3.7.2 Concept indirectly_­movable [alg.req.ind.move]") concept specifies the relationship between
an [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") type and an [indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]") type
between which values may be moved[.](#alg.req.ind.move-1.sentence-1)

template<class In, class Out>concept [indirectly_movable](#concept:indirectly_movable "24.3.7.2 Concept indirectly_­movable [alg.req.ind.move]") =[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<In> &&[indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<Out, iter_rvalue_reference_t<In>>;

[2](#alg.req.ind.move-2)

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

The [indirectly_movable_storable](#concept:indirectly_movable_storable "24.3.7.2 Concept indirectly_­movable [alg.req.ind.move]") concept augments[indirectly_movable](#concept:indirectly_movable "24.3.7.2 Concept indirectly_­movable [alg.req.ind.move]") with additional requirements enabling
the transfer to be performed through an intermediate object of the[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") type's value type[.](#alg.req.ind.move-2.sentence-1)

template<class In, class Out>concept [indirectly_movable_storable](#concept:indirectly_movable_storable "24.3.7.2 Concept indirectly_­movable [alg.req.ind.move]") =[indirectly_movable](#concept:indirectly_movable "24.3.7.2 Concept indirectly_­movable [alg.req.ind.move]")<In, Out> &&[indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<Out, iter_value_t<In>> &&[movable](concepts.object#concept:movable "18.6 Object concepts [concepts.object]")<iter_value_t<In>> &&[constructible_from](concept.constructible#concept:constructible_from "18.4.11 Concept constructible_­from [concept.constructible]")<iter_value_t<In>, iter_rvalue_reference_t<In>> &&[assignable_from](concept.assignable#concept:assignable_from "18.4.8 Concept assignable_­from [concept.assignable]")<iter_value_t<In>&, iter_rvalue_reference_t<In>>;

[3](#alg.req.ind.move-3)

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

Let i be a dereferenceable value of type In[.](#alg.req.ind.move-3.sentence-1)

In and Out model [indirectly_movable_storable](#concept:indirectly_movable_storable "24.3.7.2 Concept indirectly_­movable [alg.req.ind.move]")<In, Out> only if after the initialization of the object obj initer_value_t<In> obj(ranges::iter_move(i));obj is equal to the value previously denoted by *i[.](#alg.req.ind.move-3.sentence-2)

Ifiter_rvalue_reference_t<In> is an rvalue reference type,
the resulting state of the value denoted by *i is
valid but unspecified ([[lib.types.movedfrom]](lib.types.movedfrom "16.4.6.17 Moved-from state of library types"))[.](#alg.req.ind.move-3.sentence-3)

#### [24.3.7.3](#alg.req.ind.copy) Concept indirectly_copyable [[alg.req.ind.copy]](alg.req.ind.copy)

[1](#alg.req.ind.copy-1)

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

The [indirectly_copyable](#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]") concept specifies the relationship between
an [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") type and an [indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]") type
between which values may be copied[.](#alg.req.ind.copy-1.sentence-1)

template<class In, class Out>concept [indirectly_copyable](#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]") =[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<In> &&[indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<Out, iter_reference_t<In>>;

[2](#alg.req.ind.copy-2)

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

The [indirectly_copyable_storable](#concept:indirectly_copyable_storable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]") concept augments[indirectly_copyable](#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]") with additional requirements enabling
the transfer to be performed through an intermediate object of the[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") type's value type[.](#alg.req.ind.copy-2.sentence-1)

It also requires the capability
to make copies of values[.](#alg.req.ind.copy-2.sentence-2)

template<class In, class Out>concept [indirectly_copyable_storable](#concept:indirectly_copyable_storable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]") =[indirectly_copyable](#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<In, Out> &&[indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<Out, iter_value_t<In>&> &&[indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<Out, const iter_value_t<In>&> &&[indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<Out, iter_value_t<In>&&> &&[indirectly_writable](#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<Out, const iter_value_t<In>&&> &&[copyable](concepts.object#concept:copyable "18.6 Object concepts [concepts.object]")<iter_value_t<In>> &&[constructible_from](concept.constructible#concept:constructible_from "18.4.11 Concept constructible_­from [concept.constructible]")<iter_value_t<In>, iter_reference_t<In>> &&[assignable_from](concept.assignable#concept:assignable_from "18.4.8 Concept assignable_­from [concept.assignable]")<iter_value_t<In>&, iter_reference_t<In>>;

[3](#alg.req.ind.copy-3)

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

Let i be a dereferenceable value of type In[.](#alg.req.ind.copy-3.sentence-1)

In and Out model [indirectly_copyable_storable](#concept:indirectly_copyable_storable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<In, Out> only if after the initialization of the object obj initer_value_t<In> obj(*i);obj is equal to the value previously denoted by *i[.](#alg.req.ind.copy-3.sentence-2)

Ifiter_reference_t<In> is an rvalue reference type, the resulting state
of the value denoted by *i is
valid but unspecified ([[lib.types.movedfrom]](lib.types.movedfrom "16.4.6.17 Moved-from state of library types"))[.](#alg.req.ind.copy-3.sentence-3)

#### [24.3.7.4](#alg.req.ind.swap) Concept indirectly_swappable [[alg.req.ind.swap]](alg.req.ind.swap)

[1](#alg.req.ind.swap-1)

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

The [indirectly_swappable](#concept:indirectly_swappable "24.3.7.4 Concept indirectly_­swappable [alg.req.ind.swap]") concept specifies a swappable relationship
between the values referenced by two [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]") types[.](#alg.req.ind.swap-1.sentence-1)

template<class I1, class I2 = I1>concept [indirectly_swappable](#concept:indirectly_swappable "24.3.7.4 Concept indirectly_­swappable [alg.req.ind.swap]") =[indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<I1> && [indirectly_readable](#concept:indirectly_readable "24.3.4.2 Concept indirectly_­readable [iterator.concept.readable]")<I2> &&requires(const I1 i1, const I2 i2) { ranges::iter_swap(i1, i1);
 ranges::iter_swap(i2, i2);
 ranges::iter_swap(i1, i2);
 ranges::iter_swap(i2, i1); };

#### [24.3.7.5](#alg.req.ind.cmp) Concept indirectly_comparable [[alg.req.ind.cmp]](alg.req.ind.cmp)

[1](#alg.req.ind.cmp-1)

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

The [indirectly_comparable](#concept:indirectly_comparable "24.3.7.5 Concept indirectly_­comparable [alg.req.ind.cmp]") concept specifies
the common requirements of algorithms that
compare values from two different sequences[.](#alg.req.ind.cmp-1.sentence-1)

template<class I1, class I2, class R, class P1 = identity, class P2 = identity>concept [indirectly_comparable](#concept:indirectly_comparable "24.3.7.5 Concept indirectly_­comparable [alg.req.ind.cmp]") =[indirect_binary_predicate](#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<R, projected<I1, P1>, projected<I2, P2>>;

#### [24.3.7.6](#alg.req.permutable) Concept permutable [[alg.req.permutable]](alg.req.permutable)

[1](#alg.req.permutable-1)

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

The [permutable](#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]") concept specifies the common requirements
of algorithms that reorder elements in place by moving or swapping them[.](#alg.req.permutable-1.sentence-1)

template<class I>concept [permutable](#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]") =[forward_iterator](#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]")<I> &&[indirectly_movable_storable](#concept:indirectly_movable_storable "24.3.7.2 Concept indirectly_­movable [alg.req.ind.move]")<I, I> &&[indirectly_swappable](#concept:indirectly_swappable "24.3.7.4 Concept indirectly_­swappable [alg.req.ind.swap]")<I, I>;

#### [24.3.7.7](#alg.req.mergeable) Concept mergeable [[alg.req.mergeable]](alg.req.mergeable)

[1](#alg.req.mergeable-1)

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

The [mergeable](#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]") concept specifies the requirements of algorithms
that merge sorted sequences into an output sequence by copying elements[.](#alg.req.mergeable-1.sentence-1)

template<class I1, class I2, class Out, class R = ranges::less, class P1 = identity, class P2 = identity>concept [mergeable](#concept:mergeable "24.3.7.7 Concept mergeable [alg.req.mergeable]") =[input_iterator](#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]")<I1> &&[input_iterator](#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]")<I2> &&[weakly_incrementable](#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]")<Out> &&[indirectly_copyable](#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<I1, Out> &&[indirectly_copyable](#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<I2, Out> &&[indirect_strict_weak_order](#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<R, projected<I1, P1>, projected<I2, P2>>;

#### [24.3.7.8](#alg.req.sortable) Concept sortable [[alg.req.sortable]](alg.req.sortable)

[1](#alg.req.sortable-1)

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

The [sortable](#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") concept specifies the common requirements of
algorithms that permute sequences into ordered sequences (e.g., sort)[.](#alg.req.sortable-1.sentence-1)

template<class I, class R = ranges::less, class P = identity>concept [sortable](#concept:sortable "24.3.7.8 Concept sortable [alg.req.sortable]") =[permutable](#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")<I> &&[indirect_strict_weak_order](#concept:indirect_strict_weak_order "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<R, projected<I, P>>;
