From Jason Turner

[iterator.requirements]

C++23 → Trunk 19.1 KB 148 lines
Current Draft | LaTeX Source
Archived: C++23
Markdown: C++23 | Trunk
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpraq3fg3z/{from.md → to.md} +69 -57
tmp/tmpraq3fg3z/{from.md → to.md} RENAMED
@@ -1,22 +1,22 @@
1
  ## Iterator requirements <a id="iterator.requirements">[[iterator.requirements]]</a>
2
 
3
- ### In general <a id="iterator.requirements.general">[[iterator.requirements.general]]</a>
4
 
5
  Iterators are a generalization of pointers that allow a C++ program to
6
  work with different data structures (for example, containers and ranges)
7
  in a uniform manner. To be able to construct template algorithms that
8
  work correctly and efficiently on different types of data structures,
9
  the library formalizes not just the interfaces but also the semantics
10
  and complexity assumptions of iterators. An input iterator `i` supports
11
  the expression `*i`, resulting in a value of some object type `T`,
12
  called the *value type* of the iterator. An output iterator `i` has a
13
- non-empty set of types that are `indirectly_writable` to the iterator;
14
- for each such type `T`, the expression `*i = o` is valid where `o` is a
15
- value of type `T`. For every iterator type `X`, there is a corresponding
16
- signed integer-like type [[iterator.concept.winc]] called the
17
- *difference type* of the iterator.
18
 
19
  Since iterators are an abstraction of pointers, their semantics are a
20
  generalization of most of the semantics of pointers in C++. This ensures
21
  that every function template that takes iterators works as well with
22
  regular pointers. This document defines six categories of iterators,
@@ -113,25 +113,41 @@ A counted range `i`+\[0, `n`) is *valid* if and only if `n == 0`; or `n`
113
  is positive, `i` is dereferenceable, and `++i`+\[0, `–n`) is valid.
114
 
115
  The result of the application of library functions to invalid ranges is
116
  undefined.
117
 
 
 
 
 
 
 
 
 
 
 
 
 
 
118
  All the categories of iterators require only those functions that are
119
  realizable for a given category in constant time (amortized). Therefore,
120
  requirement tables and concept definitions for the iterators do not
121
  specify complexity.
122
 
123
- Destruction of a non-forward iterator may invalidate pointers and
124
- references previously obtained from that iterator.
 
 
125
 
126
  An *invalid iterator* is an iterator that may be singular.[^2]
127
 
128
- Iterators are called *constexpr iterators* if all operations provided to
129
- meet iterator category requirements are constexpr functions.
130
 
131
- [*Note 3*: For example, the types “pointer to `int`” and
132
- `reverse_iterator<int*>` are constexpr iterators. — *end note*]
 
133
 
134
  ### Associated types <a id="iterator.assoc.types">[[iterator.assoc.types]]</a>
135
 
136
  #### Incrementable traits <a id="incrementable.traits">[[incrementable.traits]]</a>
137
 
@@ -162,11 +178,11 @@ namespace std {
162
  : incrementable_traits<I> { };
163
 
164
  template<class T>
165
  requires requires { typename T::difference_type; }
166
  struct incrementable_traits<T> {
167
- using difference_type = typename T::difference_type;
168
  };
169
 
170
  template<class T>
171
  requires (!requires { typename T::difference_type; } &&
172
  requires(const T& a, const T& b) { { a - b } -> integral; })
@@ -367,27 +383,27 @@ The members of a specialization `iterator_traits<I>` generated from the
367
 
368
  - If `I` has valid [[temp.deduct]] member types `difference_type`,
369
  `value_type`, `reference`, and `iterator_category`, then
370
  `iterator_traits<I>` has the following publicly accessible members:
371
  ``` cpp
372
- using iterator_category = typename I::iterator_category;
373
- using value_type = typename I::value_type;
374
- using difference_type = typename I::difference_type;
375
  using pointer = see below;
376
- using reference = typename I::reference;
377
  ```
378
 
379
  If the *qualified-id* `I::pointer` is valid and denotes a type, then
380
  `iterator_traits<I>::pointer` names that type; otherwise, it names
381
  `void`.
382
  - Otherwise, if `I` satisfies the exposition-only concept
383
  `cpp17-input-iterator`, `iterator_traits<I>` has the following
384
  publicly accessible members:
385
  ``` cpp
386
  using iterator_category = see below;
387
- using value_type = typename indirectly_readable_traits<I>::value_type;
388
- using difference_type = typename incrementable_traits<I>::difference_type;
389
  using pointer = see below;
390
  using reference = see below;
391
  ```
392
 
393
  - If the *qualified-id* `I::pointer` is valid and denotes a type,
@@ -457,16 +473,14 @@ To implement a generic `reverse` function, a C++ program can do the
457
  following:
458
 
459
  ``` cpp
460
  template<class BI>
461
  void reverse(BI first, BI last) {
462
- typename iterator_traits<BI>::difference_type n =
463
- distance(first, last);
464
  --n;
465
  while (n > 0) {
466
- typename iterator_traits<BI>::value_type
467
- tmp = *first;
468
  *first++ = *--last;
469
  *last = tmp;
470
  n -= 2;
471
  }
472
  }
@@ -501,11 +515,11 @@ ill-formed, no diagnostic required.
501
 
502
  The name `ranges::iter_swap` denotes a customization point object
503
  [[customization.point.object]] that exchanges the values
504
  [[concept.swappable]] denoted by its arguments.
505
 
506
- Let *`iter-exchange-move`* be the exposition-only function:
507
 
508
  ``` cpp
509
  template<class X, class Y>
510
  constexpr iter_value_t<X> iter-exchange-move(X&& x, Y&& y)
511
  noexcept(noexcept(iter_value_t<X>(iter_move(x))) &&
@@ -601,11 +615,11 @@ Types that are indirectly readable by applying `operator*` model the
601
  `indirectly_readable` concept, including pointers, smart pointers, and
602
  iterators.
603
 
604
  ``` cpp
605
  template<class In>
606
- concept indirectly-readable-impl =
607
  requires(const In in) {
608
  typename iter_value_t<In>;
609
  typename iter_reference_t<In>;
610
  typename iter_rvalue_reference_t<In>;
611
  { *in } -> same_as<iter_reference_t<In>>;
@@ -643,11 +657,11 @@ template<class Out, class T>
643
  };
644
  ```
645
 
646
  Let `E` be an expression such that `decltype((E))` is `T`, and let `o`
647
  be a dereferenceable object of type `Out`. `Out` and `T` model
648
- `indirectly_writable<Out, T>` only if
649
 
650
  - If `Out` and `T` model
651
  `indirectly_readable<Out> && same_as<iter_value_t<Out>, decay_t<T>>`,
652
  then `*o` after any above assignment is equal to the value of `E`
653
  before the assignment.
@@ -796,19 +810,19 @@ a signed-integer-like type.
796
  type. `is-signed-integer-like<I>` is `true` if and only if `I` is a
797
  signed-integer-like type.
798
 
799
  Let `i` be an object of type `I`. When `i` is in the domain of both pre-
800
  and post-increment, `i` is said to be *incrementable*. `I` models
801
- `weakly_incrementable<I>` only if
802
 
803
  - The expressions `++i` and `i++` have the same domain.
804
  - If `i` is incrementable, then both `++i` and `i++` advance `i` to the
805
  next element.
806
  - If `i` is incrementable, then `addressof(++i)` is equal to
807
  `addressof(i)`.
808
 
809
- *Recommended practice:* The implementaton of an algorithm on a weakly
810
  incrementable type should never attempt to pass through the same
811
  incrementable value twice; such an algorithm should be a single-pass
812
  algorithm.
813
 
814
  [*Note 3*: For `weakly_incrementable` types, `a` equals `b` does not
@@ -822,12 +836,13 @@ be used with istreams as the source of the input data through the
822
  The `incrementable` concept specifies requirements on types that can be
823
  incremented with the pre- and post-increment operators. The increment
824
  operations are required to be equality-preserving, and the type is
825
  required to be `equality_comparable`.
826
 
827
- [*Note 1*: This supersedes the annotations on the increment expressions
828
- in the definition of `weakly_incrementable`. — *end note*]
 
829
 
830
  ``` cpp
831
  template<class I>
832
  concept incrementable =
833
  regular<I> &&
@@ -836,11 +851,11 @@ template<class I>
836
  { i++ } -> same_as<I>;
837
  };
838
  ```
839
 
840
  Let `a` and `b` be incrementable objects of type `I`. `I` models
841
- `incrementable` only if
842
 
843
  - If `bool(a == b)` then `bool(a++ == b)`.
844
  - If `bool(a == b)` then `bool(((void)a++, a) == ++b)`.
845
 
846
  [*Note 2*: The requirement that `a` equals `b` implies `++a` equals
@@ -885,11 +900,11 @@ template<class S, class I>
885
  input_or_output_iterator<I> &&
886
  weakly-equality-comparable-with<S, I>; // see [concept.equalitycomparable]
887
  ```
888
 
889
  Let `s` and `i` be values of type `S` and `I` such that \[`i`, `s`)
890
- denotes a range. Types `S` and `I` model `sentinel_for<S, I>` only if
891
 
892
  - `i == s` is well-defined.
893
  - If `bool(i != s)` then `i` is dereferenceable and \[`++i`, `s`)
894
  denotes a range.
895
  - `assignable_from<I&, S>` is either modeled or not satisfied.
@@ -919,11 +934,11 @@ template<class S, class I>
919
  ```
920
 
921
  Let `i` be an iterator of type `I`, and `s` a sentinel of type `S` such
922
  that \[`i`, `s`) denotes a range. Let N be the smallest number of
923
  applications of `++i` necessary to make `bool(i == s)` be `true`. `S`
924
- and `I` model `sized_sentinel_for<S, I>` only if
925
 
926
  - If N is representable by `iter_difference_t<I>`, then `s - i` is
927
  well-defined and equals N.
928
  - If -N is representable by `iter_difference_t<I>`, then `i - s` is
929
  well-defined and equals -N.
@@ -1027,11 +1042,11 @@ end of the same empty sequence. — *end note*]
1027
  Pointers and references obtained from a forward iterator into a range
1028
  \[`i`, `s`) shall remain valid while \[`i`, `s`) continues to denote a
1029
  range.
1030
 
1031
  Two dereferenceable iterators `a` and `b` of type `X` offer the
1032
- *multi-pass guarantee* if:
1033
 
1034
  - `a == b` implies `++a == ++b` and
1035
  - the expression `((void)[](X x){++x;}(a), *a)` is equivalent to the
1036
  expression `*a`.
1037
 
@@ -1098,11 +1113,11 @@ template<class I>
1098
  ```
1099
 
1100
  Let `a` and `b` be valid iterators of type `I` such that `b` is
1101
  reachable from `a` after `n` applications of `++a`, let `D` be
1102
  `iter_difference_t<I>`, and let `n` denote a value of type `D`. `I`
1103
- models `random_access_iterator` only if
1104
 
1105
  - `(a += n)` is equal to `b`.
1106
  - `addressof(a += n)` is equal to `addressof(a)`.
1107
  - `(a + n)` is equal to `(a += n)`.
1108
  - For any two positive values `x` and `y` of type `D`, if
@@ -1142,10 +1157,11 @@ non-dereferenceable iterator of type `I` such that `b` is reachable from
1142
  if
1143
 
1144
  - `to_address(a) == addressof(*a)`,
1145
  - `to_address(b) == to_address(a) + D(b - a)`,
1146
  - `to_address(c) == to_address(a) + D(c - a)`,
 
1147
  - `ranges::iter_move(a)` has the same type, value category, and effects
1148
  as `std::move(*a)`, and
1149
  - if `ranges::iter_swap(a, b)` is well-formed, it has effects equivalent
1150
  to `ranges::swap(*a, *b)`.
1151
 
@@ -1172,11 +1188,11 @@ set of requirements specifies operations for dereferencing and
1172
  incrementing an iterator. Most algorithms will require additional
1173
  operations to read [[input.iterators]] or write [[output.iterators]]
1174
  values, or to provide a richer set of iterator movements
1175
  [[forward.iterators]], [[bidirectional.iterators]], [[random.access.iterators]].
1176
 
1177
- A type `X` meets the requirements if:
1178
 
1179
  - `X` meets the *Cpp17CopyConstructible*, *Cpp17CopyAssignable*,
1180
  *Cpp17Swappable*, and *Cpp17Destructible* requirements
1181
  [[utility.arg.requirements]], [[swappable.requirements]], and
1182
  - `iterator_traits<X>::difference_type` is a signed integer type or
@@ -1231,12 +1247,12 @@ the assignment statement. Assignment through the same value of the
1231
  iterator happens only once. Equality and inequality are not necessarily
1232
  defined. — *end note*]
1233
 
1234
  #### Forward iterators <a id="forward.iterators">[[forward.iterators]]</a>
1235
 
1236
- A class or pointer type `X` meets the requirements of a forward iterator
1237
- if
1238
 
1239
  - `X` meets the *Cpp17InputIterator* requirements [[input.iterators]],
1240
  - `X` meets the *Cpp17DefaultConstructible* requirements
1241
  [[utility.arg.requirements]],
1242
  - if `X` is a mutable iterator, `reference` is a reference to `T`; if
@@ -1252,11 +1268,11 @@ the same type.
1252
 
1253
  [*Note 1*: Value-initialized iterators behave as if they refer past the
1254
  end of the same empty sequence. — *end note*]
1255
 
1256
  Two dereferenceable iterators `a` and `b` of type `X` offer the
1257
- *multi-pass guarantee* if:
1258
 
1259
  - `a == b` implies `++a == ++b` and
1260
  - `X` is a pointer type or the expression `(void)++X(a), *a` is
1261
  equivalent to the expression `*a`.
1262
 
@@ -1317,86 +1333,82 @@ namespace std {
1317
  concept indirectly_unary_invocable =
1318
  indirectly_readable<I> &&
1319
  copy_constructible<F> &&
1320
  invocable<F&, indirect-value-t<I>> &&
1321
  invocable<F&, iter_reference_t<I>> &&
1322
- invocable<F&, iter_common_reference_t<I>> &&
1323
  common_reference_with<
1324
  invoke_result_t<F&, indirect-value-t<I>>,
1325
  invoke_result_t<F&, iter_reference_t<I>>>;
1326
 
1327
  template<class F, class I>
1328
  concept indirectly_regular_unary_invocable =
1329
  indirectly_readable<I> &&
1330
  copy_constructible<F> &&
1331
  regular_invocable<F&, indirect-value-t<I>> &&
1332
  regular_invocable<F&, iter_reference_t<I>> &&
1333
- regular_invocable<F&, iter_common_reference_t<I>> &&
1334
  common_reference_with<
1335
  invoke_result_t<F&, indirect-value-t<I>>,
1336
  invoke_result_t<F&, iter_reference_t<I>>>;
1337
 
1338
  template<class F, class I>
1339
  concept indirect_unary_predicate =
1340
  indirectly_readable<I> &&
1341
  copy_constructible<F> &&
1342
  predicate<F&, indirect-value-t<I>> &&
1343
- predicate<F&, iter_reference_t<I>> &&
1344
- predicate<F&, iter_common_reference_t<I>>;
1345
 
1346
  template<class F, class I1, class I2>
1347
  concept indirect_binary_predicate =
1348
  indirectly_readable<I1> && indirectly_readable<I2> &&
1349
  copy_constructible<F> &&
1350
  predicate<F&, indirect-value-t<I1>, indirect-value-t<I2>> &&
1351
  predicate<F&, indirect-value-t<I1>, iter_reference_t<I2>> &&
1352
  predicate<F&, iter_reference_t<I1>, indirect-value-t<I2>> &&
1353
- predicate<F&, iter_reference_t<I1>, iter_reference_t<I2>> &&
1354
- predicate<F&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>;
1355
 
1356
  template<class F, class I1, class I2 = I1>
1357
  concept indirect_equivalence_relation =
1358
  indirectly_readable<I1> && indirectly_readable<I2> &&
1359
  copy_constructible<F> &&
1360
  equivalence_relation<F&, indirect-value-t<I1>, indirect-value-t<I2>> &&
1361
  equivalence_relation<F&, indirect-value-t<I1>, iter_reference_t<I2>> &&
1362
  equivalence_relation<F&, iter_reference_t<I1>, indirect-value-t<I2>> &&
1363
- equivalence_relation<F&, iter_reference_t<I1>, iter_reference_t<I2>> &&
1364
- equivalence_relation<F&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>;
1365
 
1366
  template<class F, class I1, class I2 = I1>
1367
  concept indirect_strict_weak_order =
1368
  indirectly_readable<I1> && indirectly_readable<I2> &&
1369
  copy_constructible<F> &&
1370
  strict_weak_order<F&, indirect-value-t<I1>, indirect-value-t<I2>> &&
1371
  strict_weak_order<F&, indirect-value-t<I1>, iter_reference_t<I2>> &&
1372
  strict_weak_order<F&, iter_reference_t<I1>, indirect-value-t<I2>> &&
1373
- strict_weak_order<F&, iter_reference_t<I1>, iter_reference_t<I2>> &&
1374
- strict_weak_order<F&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>;
1375
  }
1376
  ```
1377
 
1378
- #### Class template `projected` <a id="projected">[[projected]]</a>
1379
 
1380
- Class template `projected` is used to constrain algorithms that accept
1381
  callable objects and projections [[defns.projection]]. It combines an
1382
  `indirectly_readable` type `I` and a callable object type `Proj` into a
1383
  new `indirectly_readable` type whose `reference` type is the result of
1384
  applying `Proj` to the `iter_reference_t` of `I`.
1385
 
1386
  ``` cpp
1387
  namespace std {
1388
- template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj>
1389
- struct projected {
 
1390
  using value_type = remove_cvref_t<indirect_result_t<Proj&, I>>;
 
 
1391
  indirect_result_t<Proj&, I> operator*() const; // not defined
1392
  };
1393
-
1394
- template<weakly_incrementable I, class Proj>
1395
- struct incrementable_traits<projected<I, Proj>> {
1396
- using difference_type = iter_difference_t<I>;
1397
  };
 
 
 
1398
  }
1399
  ```
1400
 
1401
  ### Common algorithm requirements <a id="alg.req">[[alg.req]]</a>
1402
 
 
1
  ## Iterator requirements <a id="iterator.requirements">[[iterator.requirements]]</a>
2
 
3
+ ### General <a id="iterator.requirements.general">[[iterator.requirements.general]]</a>
4
 
5
  Iterators are a generalization of pointers that allow a C++ program to
6
  work with different data structures (for example, containers and ranges)
7
  in a uniform manner. To be able to construct template algorithms that
8
  work correctly and efficiently on different types of data structures,
9
  the library formalizes not just the interfaces but also the semantics
10
  and complexity assumptions of iterators. An input iterator `i` supports
11
  the expression `*i`, resulting in a value of some object type `T`,
12
  called the *value type* of the iterator. An output iterator `i` has a
13
+ non-empty set of types that are *writable* to the iterator; for each
14
+ such type `T`, the expression `*i = o` is valid where `o` is a value of
15
+ type `T`. For every iterator type `X`, there is a corresponding signed
16
+ integer-like type [[iterator.concept.winc]] called the *difference type*
17
+ of the iterator.
18
 
19
  Since iterators are an abstraction of pointers, their semantics are a
20
  generalization of most of the semantics of pointers in C++. This ensures
21
  that every function template that takes iterators works as well with
22
  regular pointers. This document defines six categories of iterators,
 
113
  is positive, `i` is dereferenceable, and `++i`+\[0, `–n`) is valid.
114
 
115
  The result of the application of library functions to invalid ranges is
116
  undefined.
117
 
118
+ For an iterator `i` of a type that models `contiguous_iterator`
119
+ [[iterator.concept.contiguous]], library functions are permitted to
120
+ replace \[`i`, `s`) with \[`to_address(i)`,
121
+ `to_address(i + ranges::distance(i, s))`), and to replace `i`+\[0, `n`)
122
+ with \[`to_address(i)`, `to_address(i + n)`).
123
+
124
+ [*Note 3*: This means a program cannot rely on any side effects of
125
+ dereferencing a contiguous iterator `i`, because library functions might
126
+ operate on pointers obtained by `to_address(i)` instead of operating on
127
+ `i`. Similarly, a program cannot rely on any side effects of individual
128
+ increments on a contiguous iterator `i`, because library functions might
129
+ advance `i` only once. — *end note*]
130
+
131
  All the categories of iterators require only those functions that are
132
  realizable for a given category in constant time (amortized). Therefore,
133
  requirement tables and concept definitions for the iterators do not
134
  specify complexity.
135
 
136
+ Destruction of an iterator may invalidate pointers and references
137
+ previously obtained from that iterator if its type does not meet the
138
+ *Cpp17ForwardIterator* requirements and does not model
139
+ `forward_iterator`.
140
 
141
  An *invalid iterator* is an iterator that may be singular.[^2]
142
 
143
+ Iterators meet the *constexpr iterator* requirements if all operations
144
+ provided to meet iterator category requirements are constexpr functions.
145
 
146
+ [*Note 4*: For example, the types “pointer to `int`” and
147
+ `reverse_iterator<int*>` meet the constexpr iterator
148
+ requirements. — *end note*]
149
 
150
  ### Associated types <a id="iterator.assoc.types">[[iterator.assoc.types]]</a>
151
 
152
  #### Incrementable traits <a id="incrementable.traits">[[incrementable.traits]]</a>
153
 
 
178
  : incrementable_traits<I> { };
179
 
180
  template<class T>
181
  requires requires { typename T::difference_type; }
182
  struct incrementable_traits<T> {
183
+ using difference_type = T::difference_type;
184
  };
185
 
186
  template<class T>
187
  requires (!requires { typename T::difference_type; } &&
188
  requires(const T& a, const T& b) { { a - b } -> integral; })
 
383
 
384
  - If `I` has valid [[temp.deduct]] member types `difference_type`,
385
  `value_type`, `reference`, and `iterator_category`, then
386
  `iterator_traits<I>` has the following publicly accessible members:
387
  ``` cpp
388
+ using iterator_category = I::iterator_category;
389
+ using value_type = I::value_type;
390
+ using difference_type = I::difference_type;
391
  using pointer = see below;
392
+ using reference = I::reference;
393
  ```
394
 
395
  If the *qualified-id* `I::pointer` is valid and denotes a type, then
396
  `iterator_traits<I>::pointer` names that type; otherwise, it names
397
  `void`.
398
  - Otherwise, if `I` satisfies the exposition-only concept
399
  `cpp17-input-iterator`, `iterator_traits<I>` has the following
400
  publicly accessible members:
401
  ``` cpp
402
  using iterator_category = see below;
403
+ using value_type = indirectly_readable_traits<I>::value_type;
404
+ using difference_type = incrementable_traits<I>::difference_type;
405
  using pointer = see below;
406
  using reference = see below;
407
  ```
408
 
409
  - If the *qualified-id* `I::pointer` is valid and denotes a type,
 
473
  following:
474
 
475
  ``` cpp
476
  template<class BI>
477
  void reverse(BI first, BI last) {
478
+ typename iterator_traits<BI>::difference_type n = distance(first, last);
 
479
  --n;
480
  while (n > 0) {
481
+ typename iterator_traits<BI>::value_type tmp = *first;
 
482
  *first++ = *--last;
483
  *last = tmp;
484
  n -= 2;
485
  }
486
  }
 
515
 
516
  The name `ranges::iter_swap` denotes a customization point object
517
  [[customization.point.object]] that exchanges the values
518
  [[concept.swappable]] denoted by its arguments.
519
 
520
+ Let *`iter-exchange-move`* be the exposition-only function template:
521
 
522
  ``` cpp
523
  template<class X, class Y>
524
  constexpr iter_value_t<X> iter-exchange-move(X&& x, Y&& y)
525
  noexcept(noexcept(iter_value_t<X>(iter_move(x))) &&
 
615
  `indirectly_readable` concept, including pointers, smart pointers, and
616
  iterators.
617
 
618
  ``` cpp
619
  template<class In>
620
+ concept indirectly-readable-impl = // exposition only
621
  requires(const In in) {
622
  typename iter_value_t<In>;
623
  typename iter_reference_t<In>;
624
  typename iter_rvalue_reference_t<In>;
625
  { *in } -> same_as<iter_reference_t<In>>;
 
657
  };
658
  ```
659
 
660
  Let `E` be an expression such that `decltype((E))` is `T`, and let `o`
661
  be a dereferenceable object of type `Out`. `Out` and `T` model
662
+ `indirectly_writable<Out, T>` only if:
663
 
664
  - If `Out` and `T` model
665
  `indirectly_readable<Out> && same_as<iter_value_t<Out>, decay_t<T>>`,
666
  then `*o` after any above assignment is equal to the value of `E`
667
  before the assignment.
 
810
  type. `is-signed-integer-like<I>` is `true` if and only if `I` is a
811
  signed-integer-like type.
812
 
813
  Let `i` be an object of type `I`. When `i` is in the domain of both pre-
814
  and post-increment, `i` is said to be *incrementable*. `I` models
815
+ `weakly_incrementable<I>` only if:
816
 
817
  - The expressions `++i` and `i++` have the same domain.
818
  - If `i` is incrementable, then both `++i` and `i++` advance `i` to the
819
  next element.
820
  - If `i` is incrementable, then `addressof(++i)` is equal to
821
  `addressof(i)`.
822
 
823
+ *Recommended practice:* The implementation of an algorithm on a weakly
824
  incrementable type should never attempt to pass through the same
825
  incrementable value twice; such an algorithm should be a single-pass
826
  algorithm.
827
 
828
  [*Note 3*: For `weakly_incrementable` types, `a` equals `b` does not
 
836
  The `incrementable` concept specifies requirements on types that can be
837
  incremented with the pre- and post-increment operators. The increment
838
  operations are required to be equality-preserving, and the type is
839
  required to be `equality_comparable`.
840
 
841
+ [*Note 1*: This supersedes the “not required to be equality-preserving”
842
+ comments on the increment expressions in the definition of
843
+ `weakly_incrementable`. — *end note*]
844
 
845
  ``` cpp
846
  template<class I>
847
  concept incrementable =
848
  regular<I> &&
 
851
  { i++ } -> same_as<I>;
852
  };
853
  ```
854
 
855
  Let `a` and `b` be incrementable objects of type `I`. `I` models
856
+ `incrementable` only if:
857
 
858
  - If `bool(a == b)` then `bool(a++ == b)`.
859
  - If `bool(a == b)` then `bool(((void)a++, a) == ++b)`.
860
 
861
  [*Note 2*: The requirement that `a` equals `b` implies `++a` equals
 
900
  input_or_output_iterator<I> &&
901
  weakly-equality-comparable-with<S, I>; // see [concept.equalitycomparable]
902
  ```
903
 
904
  Let `s` and `i` be values of type `S` and `I` such that \[`i`, `s`)
905
+ denotes a range. Types `S` and `I` model `sentinel_for<S, I>` only if:
906
 
907
  - `i == s` is well-defined.
908
  - If `bool(i != s)` then `i` is dereferenceable and \[`++i`, `s`)
909
  denotes a range.
910
  - `assignable_from<I&, S>` is either modeled or not satisfied.
 
934
  ```
935
 
936
  Let `i` be an iterator of type `I`, and `s` a sentinel of type `S` such
937
  that \[`i`, `s`) denotes a range. Let N be the smallest number of
938
  applications of `++i` necessary to make `bool(i == s)` be `true`. `S`
939
+ and `I` model `sized_sentinel_for<S, I>` only if:
940
 
941
  - If N is representable by `iter_difference_t<I>`, then `s - i` is
942
  well-defined and equals N.
943
  - If -N is representable by `iter_difference_t<I>`, then `i - s` is
944
  well-defined and equals -N.
 
1042
  Pointers and references obtained from a forward iterator into a range
1043
  \[`i`, `s`) shall remain valid while \[`i`, `s`) continues to denote a
1044
  range.
1045
 
1046
  Two dereferenceable iterators `a` and `b` of type `X` offer the
1047
+ *multi-pass guarantee* if
1048
 
1049
  - `a == b` implies `++a == ++b` and
1050
  - the expression `((void)[](X x){++x;}(a), *a)` is equivalent to the
1051
  expression `*a`.
1052
 
 
1113
  ```
1114
 
1115
  Let `a` and `b` be valid iterators of type `I` such that `b` is
1116
  reachable from `a` after `n` applications of `++a`, let `D` be
1117
  `iter_difference_t<I>`, and let `n` denote a value of type `D`. `I`
1118
+ models `random_access_iterator` only if:
1119
 
1120
  - `(a += n)` is equal to `b`.
1121
  - `addressof(a += n)` is equal to `addressof(a)`.
1122
  - `(a + n)` is equal to `(a += n)`.
1123
  - For any two positive values `x` and `y` of type `D`, if
 
1157
  if
1158
 
1159
  - `to_address(a) == addressof(*a)`,
1160
  - `to_address(b) == to_address(a) + D(b - a)`,
1161
  - `to_address(c) == to_address(a) + D(c - a)`,
1162
+ - `to_address(I{})` is well-defined,
1163
  - `ranges::iter_move(a)` has the same type, value category, and effects
1164
  as `std::move(*a)`, and
1165
  - if `ranges::iter_swap(a, b)` is well-formed, it has effects equivalent
1166
  to `ranges::swap(*a, *b)`.
1167
 
 
1188
  incrementing an iterator. Most algorithms will require additional
1189
  operations to read [[input.iterators]] or write [[output.iterators]]
1190
  values, or to provide a richer set of iterator movements
1191
  [[forward.iterators]], [[bidirectional.iterators]], [[random.access.iterators]].
1192
 
1193
+ A type `X` meets the requirements if
1194
 
1195
  - `X` meets the *Cpp17CopyConstructible*, *Cpp17CopyAssignable*,
1196
  *Cpp17Swappable*, and *Cpp17Destructible* requirements
1197
  [[utility.arg.requirements]], [[swappable.requirements]], and
1198
  - `iterator_traits<X>::difference_type` is a signed integer type or
 
1247
  iterator happens only once. Equality and inequality are not necessarily
1248
  defined. — *end note*]
1249
 
1250
  #### Forward iterators <a id="forward.iterators">[[forward.iterators]]</a>
1251
 
1252
+ A class or pointer type `X` meets the *Cpp17ForwardIterator*
1253
+ requirements if
1254
 
1255
  - `X` meets the *Cpp17InputIterator* requirements [[input.iterators]],
1256
  - `X` meets the *Cpp17DefaultConstructible* requirements
1257
  [[utility.arg.requirements]],
1258
  - if `X` is a mutable iterator, `reference` is a reference to `T`; if
 
1268
 
1269
  [*Note 1*: Value-initialized iterators behave as if they refer past the
1270
  end of the same empty sequence. — *end note*]
1271
 
1272
  Two dereferenceable iterators `a` and `b` of type `X` offer the
1273
+ *multi-pass guarantee* if
1274
 
1275
  - `a == b` implies `++a == ++b` and
1276
  - `X` is a pointer type or the expression `(void)++X(a), *a` is
1277
  equivalent to the expression `*a`.
1278
 
 
1333
  concept indirectly_unary_invocable =
1334
  indirectly_readable<I> &&
1335
  copy_constructible<F> &&
1336
  invocable<F&, indirect-value-t<I>> &&
1337
  invocable<F&, iter_reference_t<I>> &&
 
1338
  common_reference_with<
1339
  invoke_result_t<F&, indirect-value-t<I>>,
1340
  invoke_result_t<F&, iter_reference_t<I>>>;
1341
 
1342
  template<class F, class I>
1343
  concept indirectly_regular_unary_invocable =
1344
  indirectly_readable<I> &&
1345
  copy_constructible<F> &&
1346
  regular_invocable<F&, indirect-value-t<I>> &&
1347
  regular_invocable<F&, iter_reference_t<I>> &&
 
1348
  common_reference_with<
1349
  invoke_result_t<F&, indirect-value-t<I>>,
1350
  invoke_result_t<F&, iter_reference_t<I>>>;
1351
 
1352
  template<class F, class I>
1353
  concept indirect_unary_predicate =
1354
  indirectly_readable<I> &&
1355
  copy_constructible<F> &&
1356
  predicate<F&, indirect-value-t<I>> &&
1357
+ predicate<F&, iter_reference_t<I>>;
 
1358
 
1359
  template<class F, class I1, class I2>
1360
  concept indirect_binary_predicate =
1361
  indirectly_readable<I1> && indirectly_readable<I2> &&
1362
  copy_constructible<F> &&
1363
  predicate<F&, indirect-value-t<I1>, indirect-value-t<I2>> &&
1364
  predicate<F&, indirect-value-t<I1>, iter_reference_t<I2>> &&
1365
  predicate<F&, iter_reference_t<I1>, indirect-value-t<I2>> &&
1366
+ predicate<F&, iter_reference_t<I1>, iter_reference_t<I2>>;
 
1367
 
1368
  template<class F, class I1, class I2 = I1>
1369
  concept indirect_equivalence_relation =
1370
  indirectly_readable<I1> && indirectly_readable<I2> &&
1371
  copy_constructible<F> &&
1372
  equivalence_relation<F&, indirect-value-t<I1>, indirect-value-t<I2>> &&
1373
  equivalence_relation<F&, indirect-value-t<I1>, iter_reference_t<I2>> &&
1374
  equivalence_relation<F&, iter_reference_t<I1>, indirect-value-t<I2>> &&
1375
+ equivalence_relation<F&, iter_reference_t<I1>, iter_reference_t<I2>>;
 
1376
 
1377
  template<class F, class I1, class I2 = I1>
1378
  concept indirect_strict_weak_order =
1379
  indirectly_readable<I1> && indirectly_readable<I2> &&
1380
  copy_constructible<F> &&
1381
  strict_weak_order<F&, indirect-value-t<I1>, indirect-value-t<I2>> &&
1382
  strict_weak_order<F&, indirect-value-t<I1>, iter_reference_t<I2>> &&
1383
  strict_weak_order<F&, iter_reference_t<I1>, indirect-value-t<I2>> &&
1384
+ strict_weak_order<F&, iter_reference_t<I1>, iter_reference_t<I2>>;
 
1385
  }
1386
  ```
1387
 
1388
+ #### Alias template `projected` <a id="projected">[[projected]]</a>
1389
 
1390
+ Alias template `projected` is used to constrain algorithms that accept
1391
  callable objects and projections [[defns.projection]]. It combines an
1392
  `indirectly_readable` type `I` and a callable object type `Proj` into a
1393
  new `indirectly_readable` type whose `reference` type is the result of
1394
  applying `Proj` to the `iter_reference_t` of `I`.
1395
 
1396
  ``` cpp
1397
  namespace std {
1398
+ template<class I, class Proj>
1399
+ struct projected-impl { // exposition only
1400
+ struct type { // exposition only
1401
  using value_type = remove_cvref_t<indirect_result_t<Proj&, I>>;
1402
+ using difference_type = iter_difference_t<I>; // present only if I
1403
+ // models weakly_incrementable
1404
  indirect_result_t<Proj&, I> operator*() const; // not defined
1405
  };
 
 
 
 
1406
  };
1407
+
1408
+ template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj>
1409
+ using projected = projected-impl<I, Proj>::type;
1410
  }
1411
  ```
1412
 
1413
  ### Common algorithm requirements <a id="alg.req">[[alg.req]]</a>
1414