[iterator.requirements] - C++17 → C++20

Files changed (1) hide show

tmp/tmpjapicmag/{from.md → to.md} +1389 -125

tmp/tmpjapicmag/{from.md → to.md} RENAMED Viewed

@@ -1,50 +1,62 @@
 ## Iterator requirements <a id="iterator.requirements">[[iterator.requirements]]</a>
 ### In general <a id="iterator.requirements.general">[[iterator.requirements.general]]</a>
 Iterators are a generalization of pointers that allow a C++ program to
-work with different data structures (containers) in a uniform manner. 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. An input iterator `i` supports the expression
-`*i`, resulting in a value of some object type `T`, called the *value
-type* of the iterator. An output iterator `i` has a non-empty set of
-types that are *writable* to the iterator; for each such type `T`, the
-expression `*i = o` is valid where `o` is a value of type `T`. An
-iterator `i` for which the expression `(*i).m` is well-defined supports
-the expression `i->m` with the same semantics as `(*i).m`. For every
-iterator type `X` for which equality is defined, there is a
-corresponding signed integer type called the *difference type* of the
-iterator.
-Since iterators are an abstraction of pointers, their semantics is a
 generalization of most of the semantics of pointers in C++. This ensures
 that every function template that takes iterators works as well with
-regular pointers. This International Standard defines five categories of
-iterators, according to the operations defined on them: *input
-iterators*, *output iterators*, *forward iterators*, *bidirectional
-iterators* and *random access iterators*, as shown in Table
-[[tab:iterators.relations]].
-**Table: Relations among iterator categories** <a id="tab:iterators.relations">[tab:iterators.relations]</a>
-| |                                 |                           |                          |
-| ----------------- | ------------------------------- | ------------------------- | ------------------------ |
-| **Random Access** | $\rightarrow$ **Bidirectional** | $\rightarrow$ **Forward** | $\rightarrow$ **Input**  |
-| |                                 |                           | $\rightarrow$ **Output** |
-Forward iterators satisfy all the requirements of input iterators and
-can be used whenever an input iterator is specified; Bidirectional
-iterators also satisfy all the requirements of forward iterators and can
-be used whenever a forward iterator is specified; Random access
-iterators also satisfy all the requirements of bidirectional iterators
-and can be used whenever a bidirectional iterator is specified.
-Iterators that further satisfy the requirements of output iterators are
 called *mutable iterators*. Nonmutable iterators are referred to as
 *constant iterators*.
 In addition to the requirements in this subclause, the nested
 *typedef-name*s specified in [[iterator.traits]] shall be provided for
@@ -52,24 +64,14 @@ the iterator type.
 [*Note 1*: Either the iterator type must provide the *typedef-name*s
 directly (in which case `iterator_traits` pick them up automatically),
 or an `iterator_traits` specialization must provide them. — *end note*]
-Iterators that further satisfy the requirement that, for integral values
-`n` and dereferenceable iterator values `a` and `(a + n)`, `*(a + n)` is
-equivalent to `*(addressof(*a) + n)`, are called *contiguous iterators*.
-[*Note 2*: For example, the type “pointer to `int`” is a contiguous
-iterator, but `reverse_iterator<int *>` is not. For a valid iterator
-range [`a`,`b`) with dereferenceable `a`, the corresponding range
-denoted by pointers is [`addressof(*a)`,`addressof(*a) + (b - a)`); `b`
-might not be dereferenceable. — *end note*]
 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. These values are called *past-the-end* values.
 Values of an iterator `i` for which the expression `*i` is defined are
 called *dereferenceable*. The library never assumes that past-the-end
 values are dereferenceable. Iterators can also have singular values that
 are not associated with any sequence.
@@ -78,135 +80,1123 @@ with `int* x;`), `x` must always be assumed to have a singular value of
 a pointer. — *end example*]
 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 satisfy the `DefaultConstructible`
 requirements, using a value-initialized iterator as the source of a copy
 or move operation.
-[*Note 3*: 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. — *end note*]
 In these cases the singular value is overwritten the same way as any
 other value. Dereferenceable values are always non-singular.
-An iterator `j` is called *reachable* from an iterator `i` if and only
-if there is a finite sequence of applications of the expression `++i`
-that makes `i == j`. If `j` is reachable from `i`, they refer to
-elements of the same sequence.
 Most of the library’s algorithmic templates that operate on data
-structures have interfaces that use ranges. A *range* is a pair of
-iterators that designate the beginning and end of the computation. A
-range \[`i`, `i`) is an empty range; in general, a range \[`i`, `j`)
-refers to the elements in the data structure starting with the element
-pointed to by `i` and up to but not including the element pointed to by
-`j`. Range \[`i`, `j`) is valid if and only if `j` is reachable from
-`i`. The result of the application of functions in the library to
-invalid ranges is undefined.
 All the categories of iterators require only those functions that are
 realizable for a given category in constant time (amortized). Therefore,
-requirement tables for the iterators do not have a complexity column.
-Destruction of an iterator may invalidate pointers and references
-previously obtained from that iterator.
-An *invalid* iterator is an iterator that may be singular.[^1]
 In the following sections, `a` and `b` denote values of type `X` or
 `const X`, `difference_type` and `reference` refer to the types
 `iterator_traits<X>::difference_type` and
 `iterator_traits<X>::reference`, respectively, `n` denotes a value of
 `difference_type`, `u`, `tmp`, and `m` denote identifiers, `r` denotes a
 value of `X&`, `t` denotes a value of value type `T`, `o` denotes a
 value of some type that is writable to the output iterator.
-[*Note 4*: For an iterator type `X` there must be an instantiation of
-`iterator_traits<X>` ([[iterator.traits]]). — *end note*]
-### Iterator <a id="iterator.iterators">[[iterator.iterators]]</a>
-The `Iterator` requirements form the basis of the iterator concept
-taxonomy; every iterator satisfies the `Iterator` requirements. This set
-of requirements specifies operations for dereferencing and incrementing
-an iterator. Most algorithms will require additional operations to
-read ([[input.iterators]]) or write ([[output.iterators]]) values, or
-to provide a richer set of iterator movements ([[forward.iterators]],
-[[bidirectional.iterators]], [[random.access.iterators]]).
-A type `X` satisfies the `Iterator` requirements if:
-- `X` satisfies the `CopyConstructible`, `CopyAssignable`, and
- `Destructible` requirements ([[utility.arg.requirements]]) and
-  lvalues of type `X` are swappable ([[swappable.requirements]]), and
-- the expressions in Table  [[tab:iterator.requirements]] are valid and
- have the indicated semantics.
-### Input iterators <a id="input.iterators">[[input.iterators]]</a>
-A class or pointer type `X` satisfies the requirements of an input
-iterator for the value type `T` if `X` satisfies the `Iterator` (
-[[iterator.iterators]]) and `EqualityComparable` (Table
-[[tab:equalitycomparable]]) requirements and the expressions in Table
-[[tab:iterator.input.requirements]] are valid and have the indicated
   semantics.
-In Table  [[tab:iterator.input.requirements]], the term *the domain of
-`==`* is used in the ordinary mathematical sense to denote the set of
-values over which `==` is (required to be) defined. This set can change
-over time. Each algorithm places additional requirements on the domain
-of `==` for the iterator values it uses. These requirements can be
-inferred from the uses that algorithm makes of `==` and `!=`.
 [*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*). — *end example*]
 [*Note 1*: For input iterators, `a == b` does not imply `++a == ++b`.
 (Equality does not guarantee the substitution property or referential
 transparency.) Algorithms on input iterators should never attempt to
 pass through the same iterator twice. They should be *single pass*
-algorithms. Value type `T` is not required to be a `CopyAssignable` type
-(Table  [[tab:copyassignable]]). These algorithms can be used with
 istreams as the source of the input data through the `istream_iterator`
 class template. — *end note*]
-### Output iterators <a id="output.iterators">[[output.iterators]]</a>
-A class or pointer type `X` satisfies the requirements of an output
-iterator if `X` satisfies the `Iterator` requirements (
-[[iterator.iterators]]) and the expressions in Table
-[[tab:iterator.output.requirements]] are valid and have the indicated
 semantics.
 [*Note 1*: The only valid use of an `operator*` is on the left side of
-the assignment statement. *Assignment through the same value of the
-iterator happens only once.* Algorithms on output iterators should never
-attempt to pass through the same iterator twice. They should be *single
-pass* algorithms. Equality and inequality might not be defined.
-Algorithms that take output iterators can be used with ostreams as the
-destination for placing data through the `ostream_iterator` class as
-well as with insert iterators and insert pointers. — *end note*]
-### Forward iterators <a id="forward.iterators">[[forward.iterators]]</a>
-A class or pointer type `X` satisfies the requirements of a forward
-iterator if
-- `X` satisfies the requirements of an input iterator (
-  [[input.iterators]]),
-- `X` satisfies the `DefaultConstructible` requirements (
-  [[utility.arg.requirements]]),
 - 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`,
-- the expressions in Table  [[tab:iterator.forward.requirements]] are
- valid and have the indicated semantics, and
 - objects of type `X` offer the multi-pass guarantee, described below.
 The domain of `==` for forward iterators is that of iterators over the
 same underlying sequence. However, value-initialized iterators may be
 compared and shall compare equal to other value-initialized iterators of
@@ -232,22 +1222,296 @@ If `a` and `b` are equal, then either `a` and `b` are both
 dereferenceable or else neither is dereferenceable.
 If `a` and `b` are both dereferenceable, then `a == b` if and only if
 `*a` and `*b` are bound to the same object.
-### Bidirectional iterators <a id="bidirectional.iterators">[[bidirectional.iterators]]</a>
-A class or pointer type `X` satisfies the requirements of a
-bidirectional iterator if, in addition to satisfying the requirements
-for forward iterators, the following expressions are valid as shown in
-Table  [[tab:iterator.bidirectional.requirements]].
 [*Note 1*: Bidirectional iterators allow algorithms to move iterators
 backward as well as forward. — *end note*]
-### Random access iterators <a id="random.access.iterators">[[random.access.iterators]]</a>
-A class or pointer type `X` satisfies the requirements of a random
-access iterator if, in addition to satisfying the requirements for
-bidirectional iterators, the following expressions are valid as shown in
-Table  [[tab:iterator.random.access.requirements]].

 ## Iterator requirements <a id="iterator.requirements">[[iterator.requirements]]</a>
 ### In general <a id="iterator.requirements.general">[[iterator.requirements.general]]</a>
 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. 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. An input iterator `i` supports
+the expression `*i`, resulting in a value of some object type `T`,
+called the *value type* of the iterator. An output iterator `i` has a
+non-empty set of types that are `indirectly_writable` to the iterator;
+for each such type `T`, the expression `*i = o` is valid where `o` is a
+value of type `T`. For every iterator type `X`, there is a corresponding
+signed integer-like type [[iterator.concept.winc]] called the
+*difference type* of the iterator.
+Since iterators are an abstraction of pointers, their semantics are a
 generalization of most of the semantics of pointers in C++. This ensures
 that every function template that takes iterators works as well with
+regular pointers. This document defines six categories of iterators,
+according to the operations defined on them: *input iterators*, *output
+iterators*, *forward iterators*, *bidirectional iterators*, *random
+access iterators*, and *contiguous iterators*, as shown in
+[[iterators.relations]].
+**Table: Relations among iterator categories** <a id="iterators.relations">[iterators.relations]</a>
+| |                                 |                                 |                           |                          |
+| -------------- | ------------------------------- | ------------------------------- | ------------------------- | ------------------------ |
+| **Contiguous** | $\rightarrow$ **Random Access** | $\rightarrow$ **Bidirectional** | $\rightarrow$ **Forward** | $\rightarrow$ **Input**  |
+| |                                 |                                 |                           | $\rightarrow$ **Output** |
+The six categories of iterators correspond to the iterator concepts
+- `input_iterator` [[iterator.concept.input]],
+- `output_iterator` [[iterator.concept.output]],
+- `forward_iterator` [[iterator.concept.forward]],
+- `bidirectional_iterator` [[iterator.concept.bidir]]
+- `random_access_iterator` [[iterator.concept.random.access]], and
+- `contiguous_iterator` [[iterator.concept.contiguous]],
+respectively. The generic term *iterator* refers to any type that models
+the `input_or_output_iterator` concept [[iterator.concept.iterator]].
+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.
+Iterators that further meet the requirements of output iterators are
 called *mutable iterators*. Nonmutable iterators are referred to as
 *constant iterators*.
 In addition to the requirements in this subclause, the nested
 *typedef-name*s specified in [[iterator.traits]] shall be provided for
 [*Note 1*: Either the iterator type must provide the *typedef-name*s
 directly (in which case `iterator_traits` pick them up automatically),
 or an `iterator_traits` specialization must provide them. — *end note*]
 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. Such a value is called a *past-the-end value*.
 Values of an iterator `i` for which the expression `*i` is defined are
 called *dereferenceable*. The library never assumes that past-the-end
 values are dereferenceable. Iterators can also have singular values that
 are not associated with any sequence.
 a pointer. — *end example*]
 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.
+[*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. — *end note*]
 In these cases the singular value is overwritten the same way as any
 other value. Dereferenceable values are always non-singular.
 Most of the library’s algorithmic templates that operate on data
+structures have interfaces that use ranges. A *range* is an iterator and
+a *sentinel* 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.[^1]
+An iterator and a sentinel denoting a range are comparable. 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 by
+`i` and up to but not including the element, if any, pointed to by the
+first iterator `j` such that `j == s`.
+A sentinel `s` is called *reachable from* an iterator `i` if and only if
+there is a finite sequence of applications of the expression `++i` that
+makes `i == s`. If `s` is reachable from `i`, \[`i`, `s`) denotes a
+valid range.
+A *counted range* `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`.
+A counted range `i`+\[0, `n`) is valid if and only if `n == 0`; or `n`
+is positive, `i` is dereferenceable, and `++i`+\[0, `-``-``n`) is valid.
+The result of the application of library functions to invalid ranges is
+undefined.
 All the categories of iterators require only those functions that are
 realizable for a given category in constant time (amortized). Therefore,
+requirement tables and concept definitions for the iterators do not
+specify complexity.
+Destruction of a non-forward iterator may invalidate pointers and
+references previously obtained from that iterator.
+An *invalid iterator* is an iterator that may be singular.[^2]
+Iterators are called *constexpr iterators* if all operations provided to
+meet iterator category requirements are constexpr functions.
+[*Note 3*: For example, the types “pointer to `int`” and
+`reverse_iterator<int*>` are constexpr iterators. — *end note*]
+### Associated types <a id="iterator.assoc.types">[[iterator.assoc.types]]</a>
+#### Incrementable traits <a id="incrementable.traits">[[incrementable.traits]]</a>
+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. Accordingly, it is required that if `WI`
+is the name of a type that models the `weakly_incrementable` concept
+[[iterator.concept.winc]], the type
+``` cpp
+iter_difference_t<WI>
+```
+be defined as the incrementable type’s difference type.
+``` cpp
+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; })
+  struct incrementable_traits<T> {
+    using difference_type = make_signed_t<decltype(declval<T>() - declval<T>())>;
+  };
+  template<class T>
+    using iter_difference_t = see below;
+}
+```
+Let R_`I` be `remove_cvref_t<I>`. The type `iter_difference_t<I>`
+denotes
+- `incrementable_traits<R_I>::difference_type` if `iterator_traits<R_I>`
+  names a specialization generated from the primary template, and
+- `iterator_traits<R_I>::difference_type` otherwise.
+Users may specialize `incrementable_traits` on program-defined types.
+#### Indirectly readable traits <a id="readable.traits">[[readable.traits]]</a>
+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. Accordingly, it is required that if
+`R` is the name of a type that models the `indirectly_readable` concept
+[[iterator.concept.readable]], the type
+``` cpp
+iter_value_t<R>
+```
+be defined as the indirectly readable type’s value type.
+``` cpp
+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> 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<class T>
+  requires requires { typename T::value_type; }
+struct indirectly_readable_traits<T>
+  : cond-value-type<typename T::value_type> { };
+template<class T>
+  requires requires { typename T::element_type; }
+struct indirectly_readable_traits<T>
+  : cond-value-type<typename T::element_type> { };
+template<class T> using iter_value_t = see below;
+```
+Let R_`I` be `remove_cvref_t<I>`. The type `iter_value_t<I>` denotes
+- `indirectly_readable_traits<R_I>::value_type` if
+  `iterator_traits<R_I>` names a specialization generated from the
+  primary template, and
+- `iterator_traits<R_I>::value_type` otherwise.
+Class template `indirectly_readable_traits` may be specialized on
+program-defined types.
+[*Note 1*: Some legacy output iterators define a nested type named
+`value_type` that is an alias for `void`. These types are not
+`indirectly_readable` and have no associated value types. — *end note*]
+[*Note 2*: Smart pointers like `shared_ptr<int>` are
+`indirectly_readable` and have an associated value type, but a smart
+pointer like `shared_ptr<void>` is not `indirectly_readable` and has no
+associated value type. — *end note*]
+#### Iterator traits <a id="iterator.traits">[[iterator.traits]]</a>
+To implement algorithms only in terms of iterators, it is sometimes
+necessary to determine the iterator category that corresponds to a
+particular iterator type. Accordingly, it is required that if `I` is the
+type of an iterator, the type
+``` cpp
+iterator_traits<I>::iterator_category
+```
+be defined as the iterator’s iterator category. In addition, the types
+``` cpp
+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 as
+`decltype(a.operator->())` and `decltype(*a)`, respectively. The type
+`iterator_traits<I>::pointer` shall be `void` for an iterator of class
+type `I` that does not support `operator->`. Additionally, in the case
+of an output iterator, the types
+``` cpp
+iterator_traits<I>::value_type
+iterator_traits<I>::difference_type
+iterator_traits<I>::reference
+```
+may be defined as `void`.
+The definitions in this subclause make use of the following
+exposition-only concepts:
+``` cpp
+template<class I>
+concept cpp17-iterator =
+  copyable<I> && requires(I i) {
+    {   *i } -> can-reference;
+    {  ++i } -> same_as<I&>;
+    { *i++ } -> can-reference;
+  };
+template<class I>
+concept cpp17-input-iterator =
+  cpp17-iterator<I> && equality_comparable<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<typename incrementable_traits<I>::difference_type>;
+  };
+template<class I>
+concept cpp17-forward-iterator =
+  cpp17-input-iterator<I> && constructible_from<I> &&
+  is_lvalue_reference_v<iter_reference_t<I>> &&
+  same_as<remove_cvref_t<iter_reference_t<I>>,
+          typename indirectly_readable_traits<I>::value_type> &&
+  requires(I i) {
+    {  i++ } -> convertible_to<const I&>;
+    { *i++ } -> same_as<iter_reference_t<I>>;
+  };
+template<class I>
+concept cpp17-bidirectional-iterator =
+  cpp17-forward-iterator<I> && requires(I i) {
+    {  --i } -> same_as<I&>;
+    {  i-- } -> convertible_to<const I&>;
+    { *i-- } -> same_as<iter_reference_t<I>>;
+  };
+template<class I>
+concept cpp17-random-access-iterator =
+  cpp17-bidirectional-iterator<I> && totally_ordered<I> &&
+  requires(I i, typename incrementable_traits<I>::difference_type n) {
+    { i += n } -> same_as<I&>;
+    { i -= n } -> same_as<I&>;
+    { i +  n } -> same_as<I>;
+    { n +  i } -> same_as<I>;
+    { i -  n } -> same_as<I>;
+    { i -  i } -> same_as<decltype(n)>;
+    {  i[n]  } -> convertible_to<iter_reference_t<I>>;
+  };
+```
+The members of a specialization `iterator_traits<I>` generated from the
+`iterator_traits` primary template are computed as follows:
+- If `I` has valid [[temp.deduct]] member types `difference_type`,
+  `value_type`, `reference`, and `iterator_category`, then
+  `iterator_traits<I>` has the following publicly accessible members:
+  ``` cpp
+  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* `I::pointer` is valid and denotes a type, then
+  `iterator_traits<I>::pointer` names that type; otherwise, it names
+  `void`.
+- Otherwise, if `I` satisfies the exposition-only concept
+  `cpp17-input-iterator`, `iterator_traits<I>` has the following
+  publicly accessible members:
+  ``` cpp
+  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;
+  ```
+  - If the *qualified-id* `I::pointer` is valid and denotes a type,
+    `pointer` names that type. Otherwise, if
+    `decltype({}declval<I&>().operator->())` is well-formed, then
+    `pointer` names that type. Otherwise, `pointer` names `void`.
+  - If the *qualified-id* `I::reference` is valid and denotes a type,
+    `reference` names that type. Otherwise, `reference` names
+    `iter_reference_t<I>`.
+  - If the *qualified-id* `I::iterator_category` is valid and denotes a
+    type, `iterator_category` names that type. Otherwise,
+    `iterator_category` names:
+    - `random_access_iterator_tag` if `I` satisfies
+      `cpp17-random-access-iterator`, or otherwise
+    - `bidirectional_iterator_tag` if `I` satisfies
+      `cpp17-bidirectional-iterator`, or otherwise
+    - `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`,
+      or otherwise
+    - `input_iterator_tag`.
+- Otherwise, if `I` satisfies the exposition-only concept
+  `cpp17-iterator`, then `iterator_traits<I>` has the following publicly
+  accessible members:
+  ``` cpp
+  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* `incrementable_traits<I>::difference_type` is
+  valid and denotes a type, then `difference_type` names that type;
+  otherwise, it names `void`.
+- Otherwise, `iterator_traits<I>` has no members by any of the above
+  names.
+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_traits` is specialized for pointers as
+``` cpp
+namespace 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&;
+  };
+}
+```
+[*Example 1*:
+To implement a generic `reverse` function, a C++ program can do the
+following:
+``` cpp
+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*]
+### Customization points <a id="iterator.cust">[[iterator.cust]]</a>
+#### `ranges::iter_move` <a id="iterator.cust.move">[[iterator.cust.move]]</a>
+The name `ranges::iter_move` denotes a customization point object
+[[customization.point.object]]. The expression `ranges::iter_move(E)`
+for a subexpression `E` is expression-equivalent to:
+- `iter_move(E)`, if `E` has class or enumeration type and
+  `iter_move(E)` is a well-formed expression when treated as an
+  unevaluated operand, with overload resolution performed in a context
+  that does not include a declaration of `ranges::iter_move` but does
+  include the declaration
+  ``` cpp
+  void iter_move();
+  ```
+- Otherwise, if the expression `*E` is well-formed:
+  - if `*E` is an lvalue, `std::move(*E)`;
+  - otherwise, `*E`.
+- Otherwise, `ranges::iter_move(E)` is ill-formed. \[*Note 1*: This case
+  can result in substitution failure when `ranges::iter_move(E)` appears
+  in the immediate context of a template instantiation. — *end note*]
+If `ranges::iter_move(E)` is not equal to `*E`, the program is
+ill-formed, no diagnostic required.
+#### `ranges::iter_swap` <a id="iterator.cust.swap">[[iterator.cust.swap]]</a>
+The name `ranges::iter_swap` denotes a customization point object
+[[customization.point.object]] that exchanges the values
+[[concept.swappable]] denoted by its arguments.
+Let *`iter-exchange-move`* be the exposition-only function:
+``` cpp
+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)));
+```
+*Effects:* Equivalent to:
+``` cpp
+iter_value_t<X> old_value(iter_move(x));
+*x = iter_move(y);
+return old_value;
+```
+The expression `ranges::iter_swap(E1, E2)` for subexpressions `E1` and
+`E2` is expression-equivalent to:
+- `(void)iter_swap(E1, E2)`, if either `E1` or `E2` has class or
+  enumeration type and `iter_swap(E1, E2)` is a well-formed expression
+  with overload resolution performed in a context that includes the
+  declaration
+  ``` cpp
+  template<class I1, class I2>
+    void iter_swap(I1, I2) = delete;
+  ```
+  and does not include a declaration of `ranges::iter_swap`. 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.
+- Otherwise, if the types of `E1` and `E2` each model
+  `indirectly_readable`, and if the reference types of `E1` and `E2`
+  model `swappable_with` [[concept.swappable]], then
+  `ranges::swap(*E1, *E2)`.
+- Otherwise, if the types `T1` and `T2` of `E1` and `E2` model
+  `indirectly_movable_storable<T1, T2>` and
+  `indirectly_movable_storable<T2, T1>`, then
+  `(void)(*E1 = iter-exchange-move(E2, E1))`, except that `E1` is
+  evaluated only once.
+- Otherwise, `ranges::iter_swap(E1, E2)` is ill-formed. \[*Note 1*: This
+  case can result in substitution failure when
+  `ranges::iter_swap(E1, E2)` appears in the immediate context of a
+  template instantiation. — *end note*]
+### Iterator concepts <a id="iterator.concepts">[[iterator.concepts]]</a>
+#### General <a id="iterator.concepts.general">[[iterator.concepts.general]]</a>
+For a type `I`, let `ITER_TRAITS(I)` denote the type `I` if
+`iterator_traits<I>` names a specialization generated from the primary
+template. Otherwise, `ITER_TRAITS(I)` denotes `iterator_traits<I>`.
+- If the *qualified-id* `ITER_TRAITS(I)::iterator_concept` is valid and
+  names a type, then `ITER_CONCEPT(I)` denotes that type.
+- Otherwise, if the *qualified-id* `ITER_TRAITS(I){}::iterator_category`
+  is valid and names a type, then `ITER_CONCEPT(I)` denotes that type.
+- Otherwise, if `iterator_traits<I>` names a specialization generated
+  from the primary template, then `ITER_CONCEPT(I)` denotes
+  `random_access_iterator_tag`.
+- Otherwise, `ITER_CONCEPT(I)` does not denote a type.
+[*Note 1*: `ITER_TRAITS` enables independent syntactic determination of
+an iterator’s category and concept. — *end note*]
+[*Example 1*:
+``` cpp
+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;
+  bool operator!=(I) const;
+};
+```
+`iterator_traits<I>::iterator_category` denotes `input_iterator_tag`,
+and `ITER_CONCEPT(I)` denotes `random_access_iterator_tag`.
+— *end example*]
+#### Concept  <a id="iterator.concept.readable">[[iterator.concept.readable]]</a>
+Types that are indirectly readable by applying `operator*` model the
+`indirectly_readable` concept, including pointers, smart pointers, and
+iterators.
+``` cpp
+template<class In>
+  concept indirectly-readable-impl =
+    requires(const In in) {
+      typename iter_value_t<In>;
+      typename iter_reference_t<In>;
+      typename iter_rvalue_reference_t<In>;
+      { *in } -> same_as<iter_reference_t<In>>;
+      { ranges::iter_move(in) } -> same_as<iter_rvalue_reference_t<In>>;
+    } &&
+    common_reference_with<iter_reference_t<In>&&, iter_value_t<In>&> &&
+    common_reference_with<iter_reference_t<In>&&, iter_rvalue_reference_t<In>&&> &&
+    common_reference_with<iter_rvalue_reference_t<In>&&, const iter_value_t<In>&>;
+```
+``` cpp
+template<class In>
+  concept indirectly_readable =
+    indirectly-readable-impl<remove_cvref_t<In>>;
+```
+Given a value `i` of type `I`, `I` models `indirectly_readable` only if
+the expression `*i` is equality-preserving.
+[*Note 1*: The expression `*i` is indirectly required to be valid via
+the exposition-only `dereferenceable` concept
+[[iterator.synopsis]]. — *end note*]
+#### Concept  <a id="iterator.concept.writable">[[iterator.concept.writable]]</a>
+The `indirectly_writable` concept specifies the requirements for writing
+a value into an iterator’s referenced object.
+``` cpp
+template<class Out, class T>
+  concept indirectly_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-preserving
+      const_cast<const iter_reference_t<Out>&&>(*o) =
+        std::forward<T>(t);     // not required to be equality-preserving
+      const_cast<const iter_reference_t<Out>&&>(*std::forward<Out>(o)) =
+        std::forward<T>(t);     // not required to be equality-preserving
+    };
+```
+Let `E` be an expression such that `decltype((E))` is `T`, and let `o`
+be a dereferenceable object of type `Out`. `Out` and `T` model
+`indirectly_writable<Out, T>` only if
+- If `Out` and `T` model
+  `indirectly_readable<Out> && same_as<iter_value_t<Out>, decay_t<T>{>}`,
+  then `*o` after any above assignment is equal to the value of `E`
+  before the assignment.
+After evaluating any above assignment expression, `o` is not required to
+be dereferenceable.
+If `E` is an xvalue [[basic.lval]], the resulting state of the object it
+denotes is valid but unspecified [[lib.types.movedfrom]].
+[*Note 1*: The only valid use of an `operator*` is on the left side of
+the assignment statement. Assignment through the same value of the
+indirectly writable type happens only once. — *end note*]
+[*Note 2*: `indirectly_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. Consequently, an iterator type `I` that returns
+`std::string` by value does not model
+`indirectly_writable<I, std::string>`. — *end note*]
+#### Concept  <a id="iterator.concept.winc">[[iterator.concept.winc]]</a>
+The `weakly_incrementable` concept specifies the requirements on types
+that can be incremented with the pre- and post-increment operators. The
+increment operations are not required to be equality-preserving, nor is
+the type required to be `equality_comparable`.
+``` cpp
+template<class T>
+  inline constexpr bool is-integer-like = see below;            // exposition only
+template<class T>
+  inline constexpr bool is-signed-integer-like = see below;     // exposition only
+template<class I>
+  concept weakly_incrementable =
+    default_initializable<I> && movable<I> &&
+    requires(I i) {
+      typename iter_difference_t<I>;
+      requires is-signed-integer-like<iter_difference_t<I>>;
+      { ++i } -> same_as<I&>;   // not required to be equality-preserving
+      i++;                      // not required to be equality-preserving
+    };
+```
+A type `I` is an *integer-class type* if it is in a set of
+implementation-defined class types that behave as integer types do, as
+defined in below.
+The range of representable values of an integer-class type is the
+continuous set of values over which it is defined. The values 0 and 1
+are part of the range of every integer-class type. If any negative
+numbers are part of the range, the type is a
+*signed-integer-class type*; otherwise, it is an
+*unsigned-integer-class type*.
+For every integer-class type `I`, let `B(I)` be a hypothetical extended
+integer type of the same signedness with the smallest width
+[[basic.fundamental]] capable of representing the same range of values.
+The width of `I` is equal to the width of `B(I)`.
+Let `a` and `b` be objects of integer-class type `I`, let `x` and `y` be
+objects of type `B(I)` as described above that represent the same values
+as `a` and `b` respectively, and let `c` be an lvalue of any integral
+type.
+- For every unary operator `@` 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` provided that value is
+  representable by `I`. If `@x` has type `bool`, so too does `@a`; if
+  `@x` has type `B(I)`, then `@a` has type `I`.
+- 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`. The expression `c @= a` shall be an lvalue
+  referring to `c`.
+- For every binary operator `@` for which `x @ y` is well-formed,
+  `a @ b` shall also be well-formed and shall have the same value,
+  effects, and value category as `x @ y` provided that value is
+  representable by `I`. If `x @ y` has type `bool`, so too does `a @ b`;
+  if `x @ y` has type `B(I)`, then `a @ b` has type `I`.
+Expressions of integer-class type are explicitly convertible to any
+integral type. Expressions of integral type are both implicitly and
+explicitly convertible to any integer-class type. Conversions between
+integral and integer-class types do not exit via an exception.
+An expression `E` of integer-class type `I` is contextually convertible
+to `bool` as if by `bool(E != I(0))`.
+All integer-class types model `regular` [[concepts.object]] and
+`totally_ordered` [[concept.totallyordered]].
+A value-initialized object of integer-class type has value 0.
+For every (possibly cv-qualified) integer-class type `I`,
+`numeric_limits<I>` is specialized such that:
+- `numeric_limits<I>::is_specialized` is `true`,
+- `numeric_limits<I>::is_signed` is `true` if and only if `I` is a
+  signed-integer-class type,
+- `numeric_limits<I>::is_integer` is `true`,
+- `numeric_limits<I>::is_exact` is `true`,
+- `numeric_limits<I>::digits` is equal to the width of the integer-class
+  type,
+- `numeric_limits<I>::digits10` is equal to
+  `static_cast<int>(digits * log10(2))`, and
+- `numeric_limits<I>::min()` and `numeric_limits<I>::max()` return the
+  lowest and highest representable values of `I`, respectively, and
+  `numeric_limits<I>::lowest()` returns `numeric_limits<I>::{}min()`.
+A type `I` is *integer-like* if it models `integral<I>` or if it is an
+integer-class type. A type `I` is *signed-integer-like* if it models
+`signed_integral<I>` or if it is a signed-integer-class type. A type `I`
+is *unsigned-integer-like* if it models `unsigned_integral<I>` or if it
+is an unsigned-integer-class type.
+`is-integer-like<I>` is `true` if and only if `I` is an integer-like
+type. `is-signed-integer-like<I>` is `true` if and only if I is a
+signed-integer-like type.
+Let `i` be an object of type `I`. When `i` is in the domain of both pre-
+and post-increment, `i` is said to be *incrementable*. `I` models
+`weakly_incrementable<I>` only if
+- The expressions `++i` and `i++` have the same domain.
+- If `i` is incrementable, then both `++i` and `i++` advance `i` to the
+  next element.
+- If `i` is incrementable, then `addressof(++i)` is equal to
+  `addressof(i)`.
+[*Note 1*: For `weakly_incrementable` types, `a` equals `b` does not
+imply that `++a` equals `++b`. (Equality does not guarantee the
+substitution property or referential transparency.) Algorithms on weakly
+incrementable types should never attempt to pass through the same
+incrementable value twice. They should be single-pass algorithms. These
+algorithms can be used with istreams as the source of the input data
+through the `istream_iterator` class template. — *end note*]
+#### Concept  <a id="iterator.concept.inc">[[iterator.concept.inc]]</a>
+The `incrementable` concept specifies requirements on types that can be
+incremented with the pre- and post-increment operators. The increment
+operations are required to be equality-preserving, and the type is
+required to be `equality_comparable`.
+[*Note 1*: This supersedes the annotations on the increment expressions
+in the definition of `weakly_incrementable`. — *end note*]
+``` cpp
+template<class I>
+  concept incrementable =
+    regular<I> &&
+    weakly_incrementable<I> &&
+    requires(I i) {
+      { i++ } -> same_as<I>;
+    };
+```
+Let `a` and `b` be incrementable objects of type `I`. `I` models
+`incrementable` only if
+- If `bool(a == b)` then `bool(a++ == b)`.
+- If `bool(a == b)` then `bool(((void)a++, a) == ++b)`.
+[*Note 2*: The requirement that `a` 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`. — *end note*]
+#### Concept  <a id="iterator.concept.iterator">[[iterator.concept.iterator]]</a>
+The `input_or_output_iterator` concept forms the basis of the iterator
+concept taxonomy; every iterator models `input_or_output_iterator`. This
+concept specifies operations for dereferencing and incrementing an
+iterator. Most algorithms will require additional operations to compare
+iterators with sentinels [[iterator.concept.sentinel]], to read
+[[iterator.concept.input]] or write [[iterator.concept.output]] values,
+or to provide a richer set of iterator movements (
+[[iterator.concept.forward]], [[iterator.concept.bidir]],
+[[iterator.concept.random.access]]).
+``` cpp
+template<class I>
+  concept input_or_output_iterator =
+    requires(I i) {
+      { *i } -> can-reference;
+    } &&
+    weakly_incrementable<I>;
+```
+[*Note 1*: Unlike the *Cpp17Iterator* requirements, the
+`input_or_output_iterator` concept does not require
+copyability. — *end note*]
+#### Concept  <a id="iterator.concept.sentinel">[[iterator.concept.sentinel]]</a>
+The `sentinel_for` concept specifies the relationship between an
+`input_or_output_iterator` type and a `semiregular` type whose values
+denote a range.
+``` cpp
+template<class S, class I>
+  concept sentinel_for =
+    semiregular<S> &&
+    input_or_output_iterator<I> &&
+    weakly-equality-comparable-with<S, I>; // See [concept.equalitycomparable]
+```
+Let `s` and `i` be values of type `S` and `I` such that \[`i`, `s`)
+denotes a range. Types `S` and `I` model `sentinel_for<S, I>` only if
+- `i == s` is well-defined.
+- If `bool(i != s)` then `i` is dereferenceable and \[`++i`, `s`)
+  denotes a range.
+The domain of `==` is not static. 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`. Consequently, `i == s` is no longer required to
+be well-defined.
+#### Concept  <a id="iterator.concept.sizedsentinel">[[iterator.concept.sizedsentinel]]</a>
+The `sized_sentinel_for` concept specifies requirements on an
+`input_or_output_iterator` type `I` and a corresponding
+`sentinel_for<I>` that allow the use of the `-` operator to compute the
+distance between them in constant time.
+``` cpp
+template<class S, class I>
+  concept sized_sentinel_for =
+    sentinel_for<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<iter_difference_t<I>>;
+      { i - s } -> same_as<iter_difference_t<I>>;
+    };
+```
+Let `i` be an iterator of type `I`, and `s` a sentinel of type `S` such
+that \[`i`, `s`) denotes a range. Let N be the smallest number of
+applications of `++i` necessary to make `bool(i == s)` be `true`. `S`
+and `I` model `sized_sentinel_for<S, I>` only if
+- If N is representable by `iter_difference_t<I>`, then `s - i` is
+  well-defined and equals N.
+- If -N is representable by `iter_difference_t<I>`, then `i - s` is
+  well-defined and equals -N.
+``` cpp
+template<class S, class I>
+  inline constexpr bool disable_sized_sentinel_for = false;
+```
+*Remarks:* Pursuant to [[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. Such
+specializations shall be usable in constant expressions [[expr.const]]
+and have type `const bool`.
+[*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`. — *end note*]
+[*Example 1*: The `sized_sentinel_for` concept is modeled by pairs of
+`random_access_iterator`s [[iterator.concept.random.access]] and by
+counted iterators and their
+sentinels [[counted.iterator]]. — *end example*]
+#### Concept  <a id="iterator.concept.input">[[iterator.concept.input]]</a>
+The `input_iterator` concept defines requirements for a type whose
+referenced values can be read (from the requirement for
+`indirectly_readable` [[iterator.concept.readable]]) and which can be
+both pre- and post-incremented.
+[*Note 1*: Unlike the *Cpp17InputIterator* requirements
+[[input.iterators]], the `input_iterator` concept does not need equality
+comparison since iterators are typically compared to
+sentinels. — *end note*]
+``` cpp
+template<class I>
+  concept input_iterator =
+    input_or_output_iterator<I> &&
+    indirectly_readable<I> &&
+    requires { typename ITER_CONCEPT(I); } &&
+    derived_from<ITER_CONCEPT(I), input_iterator_tag>;
+```
+#### Concept  <a id="iterator.concept.output">[[iterator.concept.output]]</a>
+The `output_iterator` concept defines requirements for a type that can
+be used to write values (from the requirement for `indirectly_writable`
+[[iterator.concept.writable]]) and which can be both pre- and
+post-incremented.
+[*Note 1*: Output iterators are not required to model
+`equality_comparable`. — *end note*]
+``` cpp
+template<class I, class T>
+  concept output_iterator =
+    input_or_output_iterator<I> &&
+    indirectly_writable<I, T> &&
+    requires(I i, T&& t) {
+      *i++ = std::forward<T>(t);        // not required to be equality-preserving
+    };
+```
+Let `E` be an expression such that `decltype((E))` is `T`, and let `i`
+be a dereferenceable object of type `I`. `I` and `T` model
+`output_iterator<I, T>` only if `*i++ = E;` has effects equivalent to:
+``` cpp
+*i = E;
+++i;
+```
+[*Note 2*: Algorithms on output iterators should never attempt to pass
+through the same iterator twice. They should be single-pass
+algorithms. — *end note*]
+#### Concept  <a id="iterator.concept.forward">[[iterator.concept.forward]]</a>
+The `forward_iterator` concept adds copyability, equality comparison,
+and the multi-pass guarantee, specified below.
+``` cpp
+template<class I>
+  concept forward_iterator =
+    input_iterator<I> &&
+    derived_from<ITER_CONCEPT(I), forward_iterator_tag> &&
+    incrementable<I> &&
+    sentinel_for<I, I>;
+```
+The domain of `==` for forward iterators is that of iterators over the
+same underlying sequence. However, value-initialized iterators of the
+same type may be compared and shall compare equal to other
+value-initialized iterators of the same type.
+[*Note 1*: Value-initialized iterators behave as if they refer past the
+end of the same empty sequence. — *end note*]
+Pointers and references obtained from a forward iterator into a range
+\[`i`, `s`) shall remain valid while \[`i`, `s`) continues to denote a
+range.
+Two dereferenceable iterators `a` and `b` of type `X` offer the
+*multi-pass guarantee* if:
+- `a == b` implies `++a == ++b` and
+- The expression `((void)[](X x){++x;}(a), *a)` is equivalent to the
+  expression `*a`.
+[*Note 2*: The requirement that `a == 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. — *end note*]
+#### Concept  <a id="iterator.concept.bidir">[[iterator.concept.bidir]]</a>
+The `bidirectional_iterator` concept adds the ability to move an
+iterator backward as well as forward.
+``` cpp
+template<class I>
+  concept bidirectional_iterator =
+    forward_iterator<I> &&
+    derived_from<ITER_CONCEPT(I), bidirectional_iterator_tag> &&
+    requires(I i) {
+      { --i } -> same_as<I&>;
+      { i-- } -> same_as<I>;
+    };
+```
+A bidirectional iterator `r` is decrementable if and only if there
+exists some `q` such that `++q == r`. Decrementable iterators `r` shall
+be in the domain of the expressions `--r` and `r--`.
+Let `a` and `b` be equal objects of type `I`. `I` models
+`bidirectional_iterator` only if:
+- If `a` and `b` are decrementable, then all of the following are
+  `true`:
+  - `addressof(--a) == addressof(a)`
+  - `bool(a-- == b)`
+  - after evaluating both `a--` and `--b`, `bool(a == b)` is still
+    `true`
+  - `bool(++(--a) == b)`
+- If `a` and `b` are incrementable, then `bool(--(++a) == b)`.
+#### Concept  <a id="iterator.concept.random.access">[[iterator.concept.random.access]]</a>
+The `random_access_iterator` concept adds support for constant-time
+advancement with `+=`, `+`, `-=`, and `-`, as well as the computation of
+distance in constant time with `-`. Random access iterators also support
+array notation via subscripting.
+``` cpp
+template<class I>
+  concept random_access_iterator =
+    bidirectional_iterator<I> &&
+    derived_from<ITER_CONCEPT(I), random_access_iterator_tag> &&
+    totally_ordered<I> &&
+    sized_sentinel_for<I, I> &&
+    requires(I i, const I j, const iter_difference_t<I> n) {
+      { i += n } -> same_as<I&>;
+      { j +  n } -> same_as<I>;
+      { n +  j } -> same_as<I>;
+      { i -= n } -> same_as<I&>;
+      { j -  n } -> same_as<I>;
+      {  j[n]  } -> same_as<iter_reference_t<I>>;
+    };
+```
+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`. `I`
+models `random_access_iterator` only if
+- `(a += n)` is equal to `b`.
+- `addressof(a += n)` is equal to `addressof(a)`.
+- `(a + n)` is equal to `(a += n)`.
+- 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)`.
+- `(a + D(0))` is equal to `a`.
+- If `(a + D(n - 1))` is valid, then `(a + n)` is equal to
+  `[](I c){ return ++c; }(a + D(n - 1))`.
+- `(b += D(-n))` is equal to `a`.
+- `(b -= n)` is equal to `a`.
+- `addressof(b -= n)` is equal to `addressof(b)`.
+- `(b - n)` is equal to `(b -= n)`.
+- If `b` is dereferenceable, then `a[n]` is valid and is equal to `*b`.
+- `bool(a <= b)` is `true`.
+#### Concept  <a id="iterator.concept.contiguous">[[iterator.concept.contiguous]]</a>
+The `contiguous_iterator` concept provides a guarantee that the denoted
+elements are stored contiguously in memory.
+``` cpp
+template<class I>
+  concept contiguous_iterator =
+    random_access_iterator<I> &&
+    derived_from<ITER_CONCEPT(I), contiguous_iterator_tag> &&
+    is_lvalue_reference_v<iter_reference_t<I>> &&
+    same_as<iter_value_t<I>, remove_cvref_t<iter_reference_t<I>>> &&
+    requires(const I& i) {
+      { to_address(i) } -> same_as<add_pointer_t<iter_reference_t<I>>>;
+    };
+```
+Let `a` and `b` be dereferenceable iterators and `c` be a
+non-dereferenceable iterator of type `I` such that `b` is reachable from
+`a` and `c` is reachable from `b`, and let `D` be
+`iter_difference_t<I>`. The type `I` models `contiguous_iterator` only
+if
+- `to_address(a) == addressof(*a)`,
+- `to_address(b) == to_address(a) + D(b - a)`, and
+- `to_address(c) == to_address(a) + D(c - a)`.
+### C++17 iterator requirements <a id="iterator.cpp17">[[iterator.cpp17]]</a>
 In the following sections, `a` and `b` denote values of type `X` or
 `const X`, `difference_type` and `reference` refer to the types
 `iterator_traits<X>::difference_type` and
 `iterator_traits<X>::reference`, respectively, `n` denotes a value of
 `difference_type`, `u`, `tmp`, and `m` denote identifiers, `r` denotes a
 value of `X&`, `t` denotes a value of value type `T`, `o` denotes a
 value of some type that is writable to the output iterator.
+[*Note 1*: For an iterator type `X` there must be an instantiation of
+`iterator_traits<X>` [[iterator.traits]]. — *end note*]
+#### *Cpp17Iterator* <a id="iterator.iterators">[[iterator.iterators]]</a>
+The *Cpp17Iterator* requirements form the basis of the iterator
+taxonomy; every iterator meets the *Cpp17Iterator* requirements. This
+set of requirements specifies operations for dereferencing and
+incrementing an iterator. Most algorithms will require additional
+operations to read [[input.iterators]] or write [[output.iterators]]
+values, or to provide a richer set of iterator movements (
+[[forward.iterators]], [[bidirectional.iterators]],
+[[random.access.iterators]]).
+A type `X` meets the *Cpp17Iterator* requirements if:
+- `X` meets the *Cpp17CopyConstructible*, *Cpp17CopyAssignable*, and
+ *Cpp17Destructible* requirements [[utility.arg.requirements]] and
+  lvalues of type `X` are swappable [[swappable.requirements]], and
+- `iterator_traits<X>::difference_type` is a signed integer type or
+ `void`, and
+- the expressions in [[iterator]] are valid and have the indicated
   semantics.
+#### Input iterators <a id="input.iterators">[[input.iterators]]</a>
+A class or pointer type `X` meets the requirements of an input iterator
+for the value type `T` if `X` meets the *Cpp17Iterator*
+[[iterator.iterators]] and *Cpp17EqualityComparable* (
+[[cpp17.equalitycomparable]]) requirements and the expressions in
+[[inputiterator]] are valid and have the indicated semantics.
+In [[inputiterator]], the term *the domain of `==`* is used in the
+ordinary mathematical sense to denote the set of values over which `==`
+is (required to be) defined. This set can change over time. Each
+algorithm places additional requirements on the domain of `==` for the
+iterator values it uses. These requirements can be inferred from the
+uses that algorithm makes of `==` and `!=`.
 [*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*). — *end example*]
 [*Note 1*: For input iterators, `a == b` does not imply `++a == ++b`.
 (Equality does not guarantee the substitution property or referential
 transparency.) Algorithms on input iterators should never attempt to
 pass through the same iterator twice. They should be *single pass*
+algorithms. Value type `T` is not required to be a *Cpp17CopyAssignable*
+type ([[cpp17.copyassignable]]). These algorithms can be used with
 istreams as the source of the input data through the `istream_iterator`
 class template. — *end note*]
+#### Output iterators <a id="output.iterators">[[output.iterators]]</a>
+A class or pointer type `X` meets the requirements of an output iterator
+if `X` meets the *Cpp17Iterator* requirements [[iterator.iterators]] and
+the expressions in [[outputiterator]] are valid and have the indicated
 semantics.
 [*Note 1*: The only valid use of an `operator*` is on the left side of
+the assignment statement. Assignment through the same value of the
+iterator happens only once. Algorithms on output iterators should never
+attempt to pass through the same iterator twice. They should be
+single-pass algorithms. Equality and inequality might not be
+defined. — *end note*]
+#### Forward iterators <a id="forward.iterators">[[forward.iterators]]</a>
+A class or pointer type `X` meets the requirements of a forward iterator
+if
+- `X` meets the *Cpp17InputIterator* requirements [[input.iterators]],
+- `X` meets the *Cpp17DefaultConstructible* requirements
+  [[utility.arg.requirements]],
 - 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`,
+- the expressions in [[forwarditerator]] are valid and have the
+  indicated semantics, and
 - objects of type `X` offer the multi-pass guarantee, described below.
 The domain of `==` for forward iterators is that of iterators over the
 same underlying sequence. However, value-initialized iterators may be
 compared and shall compare equal to other value-initialized iterators of
 dereferenceable or else neither is dereferenceable.
 If `a` and `b` are both dereferenceable, then `a == b` if and only if
 `*a` and `*b` are bound to the same object.
+#### Bidirectional iterators <a id="bidirectional.iterators">[[bidirectional.iterators]]</a>
+A class or pointer type `X` meets the requirements of a bidirectional
+iterator if, in addition to meeting the *Cpp17ForwardIterator*
+requirements, the following expressions are valid as shown in
+[[bidirectionaliterator]].
 [*Note 1*: Bidirectional iterators allow algorithms to move iterators
 backward as well as forward. — *end note*]
+#### Random access iterators <a id="random.access.iterators">[[random.access.iterators]]</a>
+A class or pointer type `X` meets the requirements of a random access
+iterator if, in addition to meeting the *Cpp17BidirectionalIterator*
+requirements, the following expressions are valid as shown in
+[[randomaccessiterator]].
+### Indirect callable requirements <a id="indirectcallable">[[indirectcallable]]</a>
+#### General <a id="indirectcallable.general">[[indirectcallable.general]]</a>
+There are several concepts that group requirements of algorithms that
+take callable objects ([[func.def]]) as arguments.
+#### Indirect callables <a id="indirectcallable.indirectinvocable">[[indirectcallable.indirectinvocable]]</a>
+The indirect callable concepts are used to constrain those algorithms
+that accept callable objects ([[func.def]]) as arguments.
+``` cpp
+namespace std {
+  template<class F, class I>
+    concept indirectly_unary_invocable =
+      indirectly_readable<I> &&
+      copy_constructible<F> &&
+      invocable<F&, iter_value_t<I>&> &&
+      invocable<F&, iter_reference_t<I>> &&
+      invocable<F&, iter_common_reference_t<I>> &&
+      common_reference_with<
+        invoke_result_t<F&, iter_value_t<I>&>,
+        invoke_result_t<F&, iter_reference_t<I>>>;
+  template<class F, class I>
+    concept indirectly_regular_unary_invocable =
+      indirectly_readable<I> &&
+      copy_constructible<F> &&
+      regular_invocable<F&, iter_value_t<I>&> &&
+      regular_invocable<F&, iter_reference_t<I>> &&
+      regular_invocable<F&, iter_common_reference_t<I>> &&
+      common_reference_with<
+        invoke_result_t<F&, iter_value_t<I>&>,
+        invoke_result_t<F&, iter_reference_t<I>>>;
+  template<class F, class I>
+    concept indirect_unary_predicate =
+      indirectly_readable<I> &&
+      copy_constructible<F> &&
+      predicate<F&, iter_value_t<I>&> &&
+      predicate<F&, iter_reference_t<I>> &&
+      predicate<F&, iter_common_reference_t<I>>;
+  template<class F, class I1, class I2>
+    concept indirect_binary_predicate =
+      indirectly_readable<I1> && indirectly_readable<I2> &&
+      copy_constructible<F> &&
+      predicate<F&, iter_value_t<I1>&, iter_value_t<I2>&> &&
+      predicate<F&, iter_value_t<I1>&, iter_reference_t<I2>> &&
+      predicate<F&, iter_reference_t<I1>, iter_value_t<I2>&> &&
+      predicate<F&, iter_reference_t<I1>, iter_reference_t<I2>> &&
+      predicate<F&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>;
+  template<class F, class I1, class I2 = I1>
+    concept indirect_equivalence_relation =
+      indirectly_readable<I1> && indirectly_readable<I2> &&
+      copy_constructible<F> &&
+      equivalence_relation<F&, iter_value_t<I1>&, iter_value_t<I2>&> &&
+      equivalence_relation<F&, iter_value_t<I1>&, iter_reference_t<I2>> &&
+      equivalence_relation<F&, iter_reference_t<I1>, iter_value_t<I2>&> &&
+      equivalence_relation<F&, iter_reference_t<I1>, iter_reference_t<I2>> &&
+      equivalence_relation<F&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>;
+  template<class F, class I1, class I2 = I1>
+    concept indirect_strict_weak_order =
+      indirectly_readable<I1> && indirectly_readable<I2> &&
+      copy_constructible<F> &&
+      strict_weak_order<F&, iter_value_t<I1>&, iter_value_t<I2>&> &&
+      strict_weak_order<F&, iter_value_t<I1>&, iter_reference_t<I2>> &&
+      strict_weak_order<F&, iter_reference_t<I1>, iter_value_t<I2>&> &&
+      strict_weak_order<F&, iter_reference_t<I1>, iter_reference_t<I2>> &&
+      strict_weak_order<F&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>;
+}
+```
+#### Class template `projected` <a id="projected">[[projected]]</a>
+Class template `projected` is used to constrain algorithms that accept
+callable objects and projections [[defns.projection]]. It combines a
+`indirectly_readable` type `I` and a callable object type `Proj` into a
+new `indirectly_readable` type whose `reference` type is the result of
+applying `Proj` to the `iter_reference_t` of `I`.
+``` cpp
+namespace std {
+  template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj>
+  struct projected {
+    using value_type = remove_cvref_t<indirect_result_t<Proj&, I>>;
+    indirect_result_t<Proj&, I> operator*() const;              // not defined
+  };
+  template<weakly_incrementable I, class Proj>
+  struct incrementable_traits<projected<I, Proj>> {
+    using difference_type = iter_difference_t<I>;
+  };
+}
+```
+### Common algorithm requirements <a id="alg.req">[[alg.req]]</a>
+#### General <a id="alg.req.general">[[alg.req.general]]</a>
+There are several additional iterator concepts that are commonly applied
+to families of algorithms. These group together iterator requirements of
+algorithm families. There are three relational concepts that specify how
+element values are transferred between `indirectly_readable` and
+`indirectly_writable` types: `indirectly_movable`,
+`indirectly_copyable`, and `indirectly_swappable`. There are three
+relational concepts for rearrangements: `permutable`, `mergeable`, and
+`sortable`. There is one relational concept for comparing values from
+different sequences: `indirectly_comparable`.
+[*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]]. — *end note*]
+#### Concept  <a id="alg.req.ind.move">[[alg.req.ind.move]]</a>
+The `indirectly_movable` concept specifies the relationship between a
+`indirectly_readable` type and a `indirectly_writable` type between
+which values may be moved.
+``` cpp
+template<class In, class Out>
+  concept indirectly_movable =
+    indirectly_readable<In> &&
+    indirectly_writable<Out, iter_rvalue_reference_t<In>>;
+```
+The `indirectly_movable_storable` concept augments `indirectly_movable`
+with additional requirements enabling the transfer to be performed
+through an intermediate object of the `indirectly_readable` type’s value
+type.
+``` cpp
+template<class In, class Out>
+  concept indirectly_movable_storable =
+    indirectly_movable<In, Out> &&
+    indirectly_writable<Out, iter_value_t<In>> &&
+    movable<iter_value_t<In>> &&
+    constructible_from<iter_value_t<In>, iter_rvalue_reference_t<In>> &&
+    assignable_from<iter_value_t<In>&, iter_rvalue_reference_t<In>>;
+```
+Let `i` be a dereferenceable value of type `In`. `In` and `Out` model
+`indirectly_movable_storable<In, Out>` only if after the initialization
+of the object `obj` in
+``` cpp
+iter_value_t<In> obj(ranges::iter_move(i));
+```
+`obj` is equal to the value previously denoted by `*i`. If
+`iter_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]].
+#### Concept  <a id="alg.req.ind.copy">[[alg.req.ind.copy]]</a>
+The `indirectly_copyable` concept specifies the relationship between a
+`indirectly_readable` type and a `indirectly_writable` type between
+which values may be copied.
+``` cpp
+template<class In, class Out>
+  concept indirectly_copyable =
+    indirectly_readable<In> &&
+    indirectly_writable<Out, iter_reference_t<In>>;
+```
+The `indirectly_copyable_storable` concept augments
+`indirectly_copyable` with additional requirements enabling the transfer
+to be performed through an intermediate object of the
+`indirectly_readable` type’s value type. It also requires the capability
+to make copies of values.
+``` cpp
+template<class In, class Out>
+  concept indirectly_copyable_storable =
+    indirectly_copyable<In, Out> &&
+    indirectly_writable<Out, iter_value_t<In>&> &&
+    indirectly_writable<Out, const iter_value_t<In>&> &&
+    indirectly_writable<Out, iter_value_t<In>&&> &&
+    indirectly_writable<Out, const iter_value_t<In>&&> &&
+    copyable<iter_value_t<In>> &&
+    constructible_from<iter_value_t<In>, iter_reference_t<In>> &&
+    assignable_from<iter_value_t<In>&, iter_reference_t<In>>;
+```
+Let `i` be a dereferenceable value of type `In`. `In` and `Out` model
+`indirectly_copyable_storable<In, Out>` only if after the initialization
+of the object `obj` in
+``` cpp
+iter_value_t<In> obj(*i);
+```
+`obj` is equal to the value previously denoted by `*i`. If
+`iter_reference_t<In>` is an rvalue reference type, the resulting state
+of the value denoted by `*i` is valid but unspecified
+[[lib.types.movedfrom]].
+#### Concept  <a id="alg.req.ind.swap">[[alg.req.ind.swap]]</a>
+The `indirectly_swappable` concept specifies a swappable relationship
+between the values referenced by two `indirectly_readable` types.
+``` cpp
+template<class I1, class I2 = I1>
+  concept indirectly_swappable =
+    indirectly_readable<I1> && indirectly_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);
+    };
+```
+#### Concept  <a id="alg.req.ind.cmp">[[alg.req.ind.cmp]]</a>
+The `indirectly_comparable` concept specifies the common requirements of
+algorithms that compare values from two different sequences.
+``` cpp
+template<class I1, class I2, class R, class P1 = identity,
+         class P2 = identity>
+  concept indirectly_comparable =
+    indirect_binary_predicate<R, projected<I1, P1>, projected<I2, P2>>;
+```
+#### Concept  <a id="alg.req.permutable">[[alg.req.permutable]]</a>
+The `permutable` concept specifies the common requirements of algorithms
+that reorder elements in place by moving or swapping them.
+``` cpp
+template<class I>
+  concept permutable =
+    forward_iterator<I> &&
+    indirectly_movable_storable<I, I> &&
+    indirectly_swappable<I, I>;
+```
+#### Concept  <a id="alg.req.mergeable">[[alg.req.mergeable]]</a>
+The `mergeable` concept specifies the requirements of algorithms that
+merge sorted sequences into an output sequence by copying elements.
+``` cpp
+template<class I1, class I2, class Out, class R = ranges::less,
+         class P1 = identity, class P2 = identity>
+  concept mergeable =
+    input_iterator<I1> &&
+    input_iterator<I2> &&
+    weakly_incrementable<Out> &&
+    indirectly_copyable<I1, Out> &&
+    indirectly_copyable<I2, Out> &&
+    indirect_strict_weak_order<R, projected<I1, P1>, projected<I2, P2>>;
+```
+#### Concept  <a id="alg.req.sortable">[[alg.req.sortable]]</a>
+The `sortable` concept specifies the common requirements of algorithms
+that permute sequences into ordered sequences (e.g., `sort`).
+``` cpp
+template<class I, class R = ranges::less, class P = identity>
+  concept sortable =
+    permutable<I> &&
+    indirect_strict_weak_order<R, projected<I, P>>;
+```

Diff to HTML by rtfpessoa