Skip to content

Commit 1b9f5d9

Browse files
TylerMSFTTylerMSFT
TylerMSFT
authored and
TylerMSFT
committed
draft
1 parent ed23f24 commit 1b9f5d9

2 files changed

Lines changed: 97 additions & 126 deletions

File tree

‎docs/standard-library/iterator-concepts.md‎

Lines changed: 96 additions & 123 deletions
Original file line numberDiff line numberDiff line change
@@ -2,8 +2,8 @@
22
description: "Learn more about iterator concepts."
33
title: "<iterator> concepts"
44
ms.date: 12/05/2022
5-
f1_keywords: ["ranges/std::ranges::range", "ranges/std::ranges::bidirectional_range", "ranges/std::ranges::borrowed_range", "ranges/std::ranges::common_range", "ranges/std::ranges::contiguous_range", "ranges/std::ranges::forward_range", "ranges/std::ranges::input_range", "ranges/std::ranges::output_range", "ranges/std::ranges::random_access_range", "ranges/std::ranges::simple_view", "ranges/std::ranges::sized_range", "ranges/std::ranges::view", "ranges/std::ranges::viewable_range"]
6-
helpviewer_keywords: ["std::ranges [C++], ranges::range", "std::ranges [C++], ranges::bidirectional_range", "std::ranges [C++], ranges::borrowed_range", "std::ranges [C++], ranges::common_range", "std::ranges [C++], ranges::contiguous_range", "std::ranges [C++], ranges::forward_range", "std::ranges [C++], ranges::input_range", "std::ranges [C++], ranges::output_range", "std::ranges [C++], ranges::random_access_range", "std::ranges [C++], ranges::simple_view", "std::ranges [C++], ranges::sized_range", "std::ranges [C++], ranges::view", "std::ranges [C++], ranges::viewable_range"]
5+
f1_keywords: ["ranges/std::ranges::range", "ranges/std::ranges::bidirectional_iterator", "ranges/std::ranges::borrowed_iterator", "ranges/std::ranges::common_iterator", "ranges/std::ranges::contiguous_iterator", "ranges/std::ranges::forward_iterator", "ranges/std::ranges::input_iterator", "ranges/std::ranges::output_iterator", "ranges/std::ranges::random_access_iterator", "ranges/std::ranges::simple_view", "ranges/std::ranges::sized_iterator", "ranges/std::ranges::view", "ranges/std::ranges::viewable_iterator"]
6+
helpviewer_keywords: ["std::ranges [C++], ranges::range", "std::ranges [C++], ranges::bidirectional_iterator", "std::ranges [C++], ranges::borrowed_iterator", "std::ranges [C++], ranges::common_iterator", "std::ranges [C++], ranges::contiguous_iterator", "std::ranges [C++], ranges::forward_iterator", "std::ranges [C++], ranges::input_iterator", "std::ranges [C++], ranges::output_iterator", "std::ranges [C++], ranges::random_access_iterator", "std::ranges [C++], ranges::simple_view", "std::ranges [C++], ranges::sized_iterator", "std::ranges [C++], ranges::view", "std::ranges [C++], ranges::viewable_iterator"]
77
---
88
# `<iterator>` concepts
99

@@ -52,118 +52,87 @@ When you pass the compiler switch `/diagnostics:caret` to Visual Studio 2022 ver
5252

5353
Iterator concepts are defined in the `std` namespace as declared in the `<iterator>` header file. They're used in the declarations of [range adaptors](range-adaptors.md), [views](view-classes.md), and so on.
5454

55-
There are six categories of ranges. They are directly related to the categories of ranges listed in [`<iterator>](iterator.md#remarks).
55+
There are six categories of iterators. They are directly related to the categories of ranges listed in [`<ranges>](ranges.md#remarks).
5656

5757
In order of increasing power, the categories are:
5858

59-
| Range concept | Description |
59+
| Iterator concept | Description |
6060
|--|--|
61-
| [`output_range`](#output_range) | Specifies a range that you can write to. JTW It supports [output_iterator](iterators.md# JTW) Repeat this pattern for the entries below. |
62-
| [`input_range`](#input_range) | Specifies a range that you can read from at least once. |
63-
| [`forward_range`](#forward_range) | Specifies a range that can read (and possibly write) multiple times. |
64-
| [`bidirectional_range`](#bidirectional_range) | Specifies a range that can read and write both forwards and backwards. |
65-
| [`random_access_range`](#random_access_range) | Specifies a range that can read and write by index. |
66-
| [`contiguous_range`](#contiguous_range) | Specifies a range whose elements are sequential in memory and can be accessed using pointer arithmetic. |
61+
| [`input_or_output_iterator`](#input_or_output_iterator) | The basis of the iterator concept taxonomy. |
62+
| [`output_iterator`](#output_iterator) | Specifies an iterator that you can write to. JTW It supports [output_iterator](iterators.md# JTW) Repeat this pattern for the entries below. |
63+
| [`input_iterator`](#input_iterator) | Specifies an iterator that you can read from at least once. |
64+
DONE | [`forward_iterator`](#forward_iterator) | Specifies an iterator that can read (and possibly write) multiple times. |
65+
DONE | [`bidirectional_iterator`](#bidirectional_iterator) | Specifies an iterator that can read and write both forwards and backwards. |
66+
| [`random_access_iterator`](#random_access_iterator) | Specifies an iterator that can read and write by index. |
67+
DONE| [`contiguous_iterator`](#contiguous_iterator) | Specifies an iterator whose elements are sequential in memory and can be accessed using pointer arithmetic. |
6768

68-
In the preceding table, concepts are listed in order of increasing capability. A range that meets the requirements of a concept for a category generally meets the requirements of all concepts in the categories that precede it. For example, a `random_access_range` has the capability of a `bidirectional_range`, `forward_range`, `input_range`, and `output_range`. However, an exception is `input_range` which doesn't have the capability of an `output_range` because it can't be written to.
69+
In the preceding table, concepts are listed in order of increasing capability. An iterator that meets the requirements of a concept for a category generally meets the requirements of the concepts in the rows that precede it. For example, a `random_access_iterator` has the capability of a `bidirectional_iterator`, `forward_iterator`, `input_iterator`, and `output_iterator`. However, an exception is `input_iterator` which doesn't have the capability of an `output_iterator` because it can't be written to.
6970

70-
Other range concepts include:
71+
Other iterator concepts include:
7172

7273
| Range concept | Description |
7374
|--|--|
74-
| [`range`](#range)<sup>C++20</sup> | Specifies a type that provides an iterator and a sentinel. |
75-
| [`borrowed_range`](#borrowed_range)<sup>C++20</sup> | Specifies that the lifetime of the range's iterators aren't tied to the range's lifetime. |
76-
| [`common_range`](#common_range)<sup>C++20</sup> | Specifies that the type of the range's iterator and the type of the range's sentinel are the same. |
77-
| [`Simple_View`](#simple_view)<sup>C++20</sup> | Not an official concept defined as part of the standard library, but used as a helper concept on some interfaces. |
78-
| [`sized_range`](#sized_range)<sup>C++20</sup> | Specifies a range that can provide the number of elements in a range efficiently. |
79-
| [`view`](#view)<sup>C++20</sup> | Specifies a type that has efficient (constant time) move construction, assignment, and destruction. |
80-
| [`viewable_range`](#viewable_range)<sup>C++20</sup> | Specifies a type that either is a view or can be converted to one. |
81-
82-
For a list of JTW
75+
| [`sentinel_for`](#sentinel_for)<sup>C++20</sup> | JTW |
76+
| [``sized_sentinel_for``](#sized_sentinel_for)<sup>C++20</sup> | JTW |
8377

84-
## `bidirectional_range`
78+
## `bidirectional_iterator`
8579

86-
A `bidirectional_range` supports reading and writing the range forwards and backwards.
80+
A `bidirectional_iterator` supports reading and writing forwards and backwards.
8781

8882
```cpp
89-
template<class T>
90-
concept bidirectional_range =
91-
forward_range<T> && bidirectional_iterator<iterator_t<T>>;
83+
template<class I>
84+
concept bidirectional_iterator =
85+
forward_iterator<I> &&
86+
derived_from<ITER_CONCEPT(I), bidirectional_iterator_tag> &&
87+
requires(I i) {
88+
{--i} -> same_as<I&>;
89+
{i--} -> same_as<I>;
90+
};
9291
```
9392
9493
### Parameters
9594
96-
*`T`*\
97-
The type to test to see if it's a `bidirectional_range`.
95+
*`I`*\
96+
The iterator to test to see if it's a `bidirectional_iterator`.
9897
9998
### Remarks
10099
101100
A `bidirectional_iterator` has the capabilities of a `forward_iterator`, but can also iterate backwards.
102101
103-
Some examples of a `bidirectional_range` are `std::set`, `std::vector`, and `std::list`.
102+
Some examples of containers that can be used with a `bidirectional_iterator` are `std::set`, `std::vector`, and `std::list`.
104103
105-
## `borrowed_range`
104+
## `contiguous_iterator`
106105
107-
A type models `borrowed_range` if the validity of iterators you get from the object can outlive the lifetime of the object. That is, the iterators for a range can be used even when the range no longer exists.
106+
Specifies an iterator whose elements are sequential in memory and can be accessed using pointer arithmetic.
108107
109108
```cpp
110-
template<class T>
111-
concept borrowed_range =
112-
range<T> &&
113-
(is_lvalue_reference_v<T> || enable_borrowed_range<remove_cvref_t<T>>);
109+
template<class I>
110+
concept contiguous_iterator =
111+
random_access_iterator<I> &&
112+
derived_from<ITER_CONCEPT(I), contiguous_iterator_tag> &&
113+
is_lvalue_reference_v<iter_reference_t<I>> &&
114+
same_as<iter_value_t<I>, remove_cvref_t<iter_reference_t<I>>> &&
115+
requires(const I& i) {
116+
{ to_address(i) } -> same_as<add_pointer_t<iter_reference_t<I>>>;
117+
};
114118
```
115119

116120
### Parameters
117121

118-
*`T`*\
119-
The type to test to see if it's a `borrowed_range`.
120-
121-
## `common_range`
122+
*`I`*\
123+
The type to test to see if it's a `contiguous_iterator`.
122124

123-
The type of the iterator for a `common_range` is the same as the type of the sentinel. That is, `begin()` and `end()` return the same type.
124-
125-
```cpp
126-
template<class T>
127-
concept common_range =
128-
ranges::range<T> && std::same_as<ranges::iterator_t<T>, ranges::sentinel_t<T>>;
129-
```
130-
131-
### Parameters
132-
133-
*`T`*\
134-
The type to test to see if it's a `common_range`.
125+
The elements of a `contiguous_iterator` are stored sequentially in memory and can be accessed using pointer arithmetic. For example, an array can be traversed using a `contiguous_iterator`.
135126

136127
### Remarks
137128

138-
Getting the type from `std::ranges::begin()` and `std::ranges::end()` is important for algorithms that calculate the distance between two iterators, and for algorithms that accept ranges denoted by iterator pairs.
129+
A `contiguous_iterator` can be accessed by pointer arithmetic because the elements are laid out sequentially in memory and are the same size.
139130

140-
The standard containers (for example, `vector`) meet the requirements of `common_range`.
131+
Some examples of a `contiguous_iterator` are `std::array`, `std::vector`, and `std::string`.
141132

142-
## `contiguous_range`
133+
### Example: `contiguous_iterator`
143134

144-
The elements of a `contiguous_range` are stored sequentially in memory and can be accessed using pointer arithmetic. For example, an array is a `contiguous_range`.
145-
146-
```cpp
147-
template<class T>
148-
concept contiguous_range =
149-
random_access_range<T> && contiguous_iterator<iterator_t<T>> &&
150-
requires(T& t) {{ ranges::data(t) } -> same_as<add_pointer_t<range_reference_t<T>>>;};
151-
```
152-
153-
### Parameters
154-
155-
*`T`*\
156-
The type to test to see if it's a `contiguous_range`.
157-
158-
### Remarks
159-
160-
A `contiguous_range` can be accessed by pointer arithmetic because the elements are laid out sequentially in memory and are the same size.
161-
162-
Some examples of a `contiguous_range` are `std::array`, `std::vector`, and `std::string`.
163-
164-
### Example: `contiguous_range`
165-
166-
The following example shows using pointer arithmetic to access a `contiguous_range`:
135+
The following example shows using pointer arithmetic to access a `contiguous_iterator`:
167136

168137
```cpp
169138
// requires /std:c++20 or later
@@ -173,11 +142,11 @@ The following example shows using pointer arithmetic to access a `contiguous_ran
173142

174143
int main()
175144
{
176-
// Show that vector is a contiguous_range
145+
// Show that vector is a contiguous_iterator
177146
std::vector<int> v = {0,1,2,3,4,5};
178-
std::cout << std::boolalpha << std::ranges::contiguous_range<decltype(v)> << '\n'; // outputs true
147+
std::cout << std::boolalpha << std::ranges::contiguous_iterator<decltype(v)> << '\n'; // outputs true
179148

180-
// Show that pointer arithmetic can be used to access the elements of a contiguous_range
149+
// Show that pointer arithmetic can be used to access the elements of a contiguous_iterator
181150
auto ptr = v.data();
182151
ptr += 2;
183152
std::cout << *ptr << '\n'; // outputs 2
@@ -189,54 +158,58 @@ true
189158
2
190159
```
191160

192-
## `forward_range`
161+
## `forward_iterator`
193162

194-
A `forward_range` supports reading (and possibly writing) the range multiple times.
163+
Has the capabilities of an `input_iterator` and an `output_iterator`, but can read and write the same element multiple times.
195164

196165
```cpp
197-
template<class T>
198-
concept forward_range = input_range<T> && forward_iterator<iterator_t<T>>;
166+
template<class I>
167+
concept forward_iterator =
168+
input_iterator<I> &&
169+
derived_from<ITER_CONCEPT(I), forward_iterator_tag> &&
170+
incrementable<I> &&
171+
sentinel_for<I, I>;
199172
```
200173

201174
### Parameters
202175

203-
*`T`*\
204-
The type to test to see if it's a `forward_range`.
176+
*`I`*\
177+
The iterator to test to see if it's a `forward_iterator`.
205178

206-
### Remarks
179+
## `input_iterator`
207180

208-
A `forward_iterator` can iterate over a range multiple times.
209-
210-
## `input_range`
211-
212-
An `input_range` is a range that can be read from at least once.
181+
An `input_iterator` is an iterator that can be read from at least once.
213182

214183
```cpp
215-
template<class T>
216-
concept input_range = range<T> && input_iterator<iterator_t<T>>;
184+
template<class I>
185+
concept input_iterator =
186+
input_or_output_iterator<I> &&
187+
indirectly_readable<I> &&
188+
requires { typename ITER_CONCEPT(I); } &&
189+
derived_from<ITER_CONCEPT(I), input_iterator_tag>;
217190
```
218191
219192
### Parameters
220193
221-
*`T`*\
222-
The type to test to see if it's an `input_range`.
194+
*`I`*\
195+
The type to test to see if it's an `input_iterator`.
223196
224197
### Remarks
225198
226-
When a type meets the requirements of `input_range`:
199+
When a type meets the requirements of `input_iterator`:
227200
228-
- The `ranges::begin()` function returns an `input_iterator`. Calling `begin()` more than once on an `input_range` results in undefined behavior.
229-
- You can dereference an `input_iterator` repeatedly, which yields the same value each time. An `input_range` isn't multi-pass. Incrementing an iterator invalidates any copies.
201+
- Calling `begin()` more than once on an `input_iterator` results in undefined behavior.
202+
- You can dereference an `input_iterator` repeatedly, which yields the same value each time. An `input_iterator` isn't multi-pass. Incrementing an iterator invalidates any copies.
230203
- It can be used with `ranges::for_each`.
231-
- It *at least* has an `input_iterator`. It may have a more capable iterator type.
204+
- It *at least* has an `input_iterator`. It may be a more capable iterator type.
232205
233-
## `output_range`
206+
## `output_iterator`
234207
235-
An `output_range` is a range that you can write to.
208+
An `output_iterator` is a range that you can write to.
236209
237210
```cpp
238211
template<class R, class T>
239-
concept output_range = range<R> && output_iterator<iterator_t<R>, T>;
212+
concept output_iterator = range<R> && output_iterator<iterator_t<R>, T>;
240213
```
241214

242215
### Parameters
@@ -251,26 +224,26 @@ The type of the data to write to the range.
251224

252225
The meaning of `output_iterator<iterator_t<R>, T>` is that the type provides an iterator that can write values of type `T` to a range of type `R`.
253226

254-
## `random_access_range`
227+
## `random_access_iterator`
255228

256-
A `random_access_range` can read or write a range by index.
229+
A `random_access_iterator` can read or write a range by index.
257230

258231
```cpp
259232
template<class T>
260-
concept random_access_range =
261-
bidirectional_range<T> && random_access_iterator<iterator_t<T>>;
233+
concept random_access_iterator =
234+
bidirectional_iterator<T> && random_access_iterator<iterator_t<T>>;
262235
```
263236

264237
### Parameters
265238

266239
*`T`*\
267-
The type to test to see if it's a `sized_range`.
240+
The type to test to see if it's a `sized_iterator`.
268241

269242
### Remarks
270243

271-
A `random_access_range` is the most flexible iterator. It has the capabilities of an `input_range`, `output_range`, `forward_range`, and `bidirectional_range`. A `random_access_range` is also sortable.
244+
A `random_access_iterator` is the most flexible iterator. It has the capabilities of an `input_iterator`, `output_iterator`, `forward_iterator`, and `bidirectional_iterator`. A `random_access_iterator` is also sortable.
272245

273-
Some examples of a `random_access_range` are `std::vector`, `std::array`, and `std::deque`.
246+
Some examples of a `random_access_iterator` are `std::vector`, `std::array`, and `std::deque`.
274247

275248
## `range`
276249

@@ -321,33 +294,33 @@ A view `V` is a [`Simple_View`](#simple_view) if all of the following are true:
321294
- `const V` is a range
322295
- Both `v` and `const V` have the same iterator and sentinel types.
323296

324-
## `sized_range`
297+
## `sized_iterator`
325298

326-
A `sized_range` provides the number of elements in the range in amortized constant time.
299+
A `sized_iterator` provides the number of elements in the range in amortized constant time.
327300

328301
```cpp
329302
template<class T>
330-
concept sized_range = range<T> &&
303+
concept sized_iterator = range<T> &&
331304
requires(T& t) { ranges::size(t); };
332305
```
333306
334307
### Parameters
335308
336309
*`T`*\
337-
The type to test to see if it's a `sized_range`.
310+
The type to test to see if it's a `sized_iterator`.
338311
339312
### Remarks
340313
341-
The requirements of a `sized_range` are that calling `ranges::size` on it:
314+
The requirements of a `sized_iterator` are that calling `ranges::size` on it:
342315
343316
- Doesn't modify the range.
344317
- Returns the number of elements in amortized constant time. Amortized constant time doesn't mean O(1), but that the average cost over a series of calls, even in the worst case, is O(n) rather than O(n^2) or worse.
345318
346-
Some examples of a `sized_range` are `std::list` and `std::vector`.
319+
Some examples of a `sized_iterator` are `std::list` and `std::vector`.
347320
348-
### Example: `sized_range`
321+
### Example: `sized_iterator`
349322
350-
The following example shows that a `vector` of `int` is a `sized_range`:
323+
The following example shows that a `vector` of `int` is a `sized_iterator`:
351324
352325
```cpp
353326
// requires /std:c++20 or later
@@ -357,7 +330,7 @@ The following example shows that a `vector` of `int` is a `sized_range`:
357330
358331
int main()
359332
{
360-
std::cout << std::boolalpha << std::ranges::sized_range<std::vector<int>> << '\n'; // outputs "true"
333+
std::cout << std::boolalpha << std::ranges::sized_iterator<std::vector<int>> << '\n'; // outputs "true"
361334
}
362335
```
363336

@@ -392,14 +365,14 @@ Failing that, option 2 is a little simpler than option 3.
392365

393366
The advantage of option 3 is that it's possible without changing the definition of the type.
394367

395-
## `viewable_range`
368+
## `viewable_iterator`
396369

397-
A `viewable_range` is a type that either is a view or can be converted to one.
370+
A `viewable_iterator` is a type that either is a view or can be converted to one.
398371

399372
```cpp
400373
template<class T>
401-
concept viewable_range =
402-
range<T> && (borrowed_range<T> || view<remove_cvref_t<T>>);
374+
concept viewable_iterator =
375+
range<T> && (borrowed_iterator<T> || view<remove_cvref_t<T>>);
403376
```
404377

405378
### Parameters

0 commit comments

Comments
 (0)