Skip to content

Commit 6dd32c2

Browse files
TylerMSFTTylerMSFT
TylerMSFT
authored and
TylerMSFT
committed
draft
1 parent d528729 commit 6dd32c2

4 files changed

Lines changed: 104 additions & 52 deletions

File tree

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

Lines changed: 89 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
---
22
description: "Learn more about iterator concepts."
33
title: "Iterator concepts"
4-
ms.date: 12/05/2022
4+
ms.date: 12/15/2022
55
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"]
66
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
---
@@ -52,28 +52,26 @@ 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 iterators. They are directly related to the categories of ranges listed in [`<ranges>`](ranges.md#kinds-of-ranges).
55+
There are six categories of iterators. They are directly related to the categories of ranges listed under [Range concepts](ranges.md#range-concepts).
5656

57-
The following iterator concepts are listed in order of increasing capability. `input_or_output_iterator` is at the low end of the capability hierarchy, and `contiguous_iterator` is at the high end. Iterators higher in the hierarchy can generally be used in place of those that are lower, but not vice-versa. For example, a `random_access_iterator` iterator can be used in place of a `forward_iterator`, but not the other way around. An exception to the rule that iterators higher in the hierarchy can generally be used in place of those that are lower is `input_iterator`, which can't be used in place of `output_iterator` because it can't write.
57+
The following iterator concepts are listed in order of increasing capability. `input_or_output_iterator` is at the low end of the capability hierarchy, and `contiguous_iterator` is at the high end. Iterators higher in the hierarchy can generally be used in place of those that are lower, but not vice-versa. For example, a `random_access_iterator` iterator can be used in place of a `forward_iterator`, but not the other way around. An exception is `input_iterator`, which can't be used in place of `output_iterator` because it can't write.
5858

5959
| Iterator concept | Description | Direction | Read/write | Multi-pass | Example types that use this iterator |
6060
|--|--|--|--|--|--|
61-
| [`input_or_output_iterator`](#input_or_output_iterator)<sup>C++20</sup> | The basis of the iterator concept taxonomy. | Forward | Read or write | Single-pass | `std::istream_iterator`, `std::ostream_iterator` |
62-
| [`output_iterator`](#output_iterator)<sup>C++20</sup> | Test for an iterator that you can write to. | Forward | Write | Single-pass | `ostream`, `inserter` |
63-
| [`input_iterator`](#input_iterator)<sup>C++20</sup> | Test for an iterator that you can read from at least once. | Forward | Read | Single-pass | `istream`, `istreambuf_iterator` |
64-
| [`forward_iterator`](#forward_iterator)<sup>C++20</sup> | Test for an iterator that can read (and possibly write) multiple times. | Forward | Read/write | Multi-pass | `vector::iterator`, `list::iterator` |
65-
| [`bidirectional_iterator`](#bidirectional_iterator)<sup>C++20</sup> | Test for an iterator that can read and write both forwards and backwards. | Forward/Backward | Read/write | Multi-pass | `list`, `set`, `multiset`, `map`, and `multimap`. |
66-
| [`random_access_iterator`](#random_access_iterator)<sup>C++20</sup> | Test for an iterator that can read and write by index. | Read/write | Multi-pass | `vector::iterator`, `array::iterator` |
67-
| [`contiguous_iterator`](#contiguous_iterator)<sup>C++20</sup> | Test for an iterator whose elements are sequential in memory and can be accessed using pointer arithmetic. | Read/write | Multi-pass | `array`, `vector` |
68-
69-
An iterator that meets the requirements of a concept generally meets the requirements of the concepts in the rows that precede it in the previous table. For example, a `random_access_iterator` has the capability of a `bidirectional_iterator`, `forward_iterator`, `input_iterator`, and `output_iterator`. An exception is `input_iterator` which doesn't have the capability of an `output_iterator` because it can't be written to.
61+
| [`input_or_output_iterator`](#input_or_output_iterator)<sup>C++20</sup> | The basis of the iterator concept taxonomy. | Forward | Read or write | no | `std::istream_iterator`, `std::ostream_iterator` |
62+
| [`output_iterator`](#output_iterator)<sup>C++20</sup> | Test for an iterator that you can write to. | Forward | Write | no | `ostream`, `inserter` |
63+
| [`input_iterator`](#input_iterator)<sup>C++20</sup> | Test for an iterator that you can read from at least once. | Forward | Read | no | `istream`, `istreambuf_iterator` |
64+
| [`forward_iterator`](#forward_iterator)<sup>C++20</sup> | Test for an iterator that can read (and possibly write) multiple times. | Forward | Read/write | yes | `vector::iterator`, `list::iterator` |
65+
| [`bidirectional_iterator`](#bidirectional_iterator)<sup>C++20</sup> | Test for an iterator that can read and write both forwards and backwards. | Forward/backward | Read/write | yes | `list`, `set`, `multiset`, `map`, and `multimap`. |
66+
| [`random_access_iterator`](#random_access_iterator)<sup>C++20</sup> | Test for an iterator that can read and write by index. | Forward/Backward | Read/write | yes | `vector::iterator`, `array::iterator`, `deque::iterator` |
67+
| [`contiguous_iterator`](#contiguous_iterator)<sup>C++20</sup> | Test for an iterator whose elements are sequential in memory and can be accessed using pointer arithmetic. | Forward/backward | Read/write | yes | `array`, `vector` `string`.|
7068

7169
Other iterator concepts include:
7270

7371
| Iterator concept | Description |
7472
|--|--|
75-
DONE | [`sentinel_for`](#sentinel_for)<sup>C++20</sup> | Test that a type is a sentinel for an iterator type. |
76-
DONE | [`sized_sentinel_for`](#sized_sentinel_for)<sup>C++20</sup> | Specifies that an iterator and its sentinel can be subtracted (using `-`) to find their difference in constant time. |
73+
| [`sentinel_for`](#sentinel_for)<sup>C++20</sup> | Test that a type is a sentinel for an iterator type. |
74+
| [`sized_sentinel_for`](#sized_sentinel_for)<sup>C++20</sup> | Specifies that an iterator and its sentinel can be subtracted (using `-`) to find their difference in constant time. |
7775

7876
## `bidirectional_iterator`
7977

@@ -103,7 +101,7 @@ Some examples of containers that can be used with a `bidirectional_iterator` are
103101
104102
### Example: `bidirectional_iterator`
105103
106-
The following example shows that a `vector` of `int` has a `bidirectional_iterator`:
104+
The following example uses the `bidirectional_iterator` concept to show that `vector<int>` has a `bidirectional_iterator`:
107105
108106
```cpp
109107
// requires /std:c++20 or later
@@ -113,6 +111,10 @@ The following example shows that a `vector` of `int` has a `bidirectional_iterat
113111
int main()
114112
{
115113
std::cout << std::boolalpha << std::bidirectional_iterator<std::vector<int>::iterator> << '\n'; // outputs "true"
114+
115+
// another way to test
116+
std::vector<int> v = {0,1,2};
117+
std::cout << std::boolalpha << std::contiguous_iterator<decltype(v)::iterator>; // outputs true
116118
}
117119
```
118120

@@ -137,7 +139,7 @@ template<class I>
137139
*`I`*\
138140
The type to test to see if it's a `contiguous_iterator`.
139141
140-
The elements of a `contiguous_iterator` are stored sequentially in memory and can be accessed using pointer arithmetic. For example, an array iterator is a `contiguous_iterator`.
142+
The elements of a `contiguous_iterator` are stored sequentially in memory and can be accessed using pointer arithmetic. A `std::array` has a `contiguous_iterator`.
141143
142144
### Remarks
143145
@@ -147,7 +149,7 @@ Some examples of a `contiguous_iterator` are `std::array`, `std::vector`, and `s
147149
148150
### Example: `contiguous_iterator`
149151
150-
The following example shows that a vector is a `contiguous_iterator`:
152+
The following example uses the `contiguous_iterator` concept to show that a `vector<int>` has a `contiguous_iterator`:
151153
152154
```cpp
153155
// requires /std:c++20 or later
@@ -156,8 +158,11 @@ The following example shows that a vector is a `contiguous_iterator`:
156158
157159
int main()
158160
{
159-
// Show that vector has a contiguous_iterator
160-
std::vector<int> v = {0,1,2,3,4,5};
161+
// Show that vector<int> has a contiguous_iterator
162+
std::cout << std::boolalpha << std::contiguous_iterator<std::vector<int>::iterator> << '\n'; // outputs "true"
163+
164+
// another way to test
165+
std::vector<int> v = {0,1,2};
161166
std::cout << std::boolalpha << std::contiguous_iterator<decltype(v)::iterator>; // outputs true
162167
}
163168
```
@@ -188,7 +193,7 @@ Some examples of containers that can be used with a `forward_iterator` are `std:
188193

189194
### Example: `forward_iterator`
190195

191-
The following example shows that an `unordered_set` has a `forward_iterator`:
196+
The following example uses the `forward_iterator` concept to show that a `vector<int>` has a `forward_iterator`:
192197

193198
```cpp
194199
// requires /std:c++20 or later
@@ -198,7 +203,10 @@ The following example shows that an `unordered_set` has a `forward_iterator`:
198203
int main()
199204
{
200205
// Show that vector has a forward_iterator
201-
std::vector<int> v = {0,1,2,3,4,5};
206+
std::cout << std::boolalpha << std::forward_iterator<std::vector<int>::iterator> << '\n'; // outputs "true"
207+
208+
// another way to test
209+
std::vector<int> v = {0,1,2};
202210
std::cout << std::boolalpha << std::forward_iterator<decltype(v)::iterator>; // outputs true
203211
}
204212
```
@@ -229,23 +237,23 @@ When a type meets the requirements of `input_iterator`:
229237
230238
### Example: `input_iterator`
231239
232-
The following example shows that an `istream_iterator` is an `input_iterator`:
240+
The following example uses the `input_iterator` concept to show that an `istream_iterator` has an `input_iterator`:
233241
234242
```cpp
235243
// requires /std:c++20 or later
236244
#include <iostream>
237-
#include <vector>
238245
239246
int main()
240247
{
248+
// Show that a istream_iterator has an input_iterator
241249
std::cout << std::boolalpha << std::input_iterator<std::istream_iterator<int>>; // outputs true
242250
}
243251
```
244252

245253
## `input_or_output_iterator`
246254

247-
An `input_or_output_iterator` is the basis of the iterator concept taxonomy and supports dereferencing and incrementing
248-
an iterator. Every iterator models `input_or_output_iterator`, at a minimum.
255+
An `input_or_output_iterator` is the basis of the iterator concept taxonomy. It supports dereferencing and incrementing
256+
an iterator. Every iterator models `input_or_output_iterator`.
249257

250258
```cpp
251259
template<class I>
@@ -259,12 +267,31 @@ concept input_or_output_iterator =
259267
### Parameters
260268
261269
*`I`*\
262-
The type to test to see if it's an `input_iterator`.
270+
The type to test to see if it's an `input_or_output_iterator`.
263271
264272
### Remarks
265273
266274
The concept `can-reference` means that the type `I` is a reference, a pointer, or a type that can be implicitly converted to a reference.
267275
276+
### Example: `input_or_output_iterator`
277+
278+
The following example uses the `input_or_output_iterator` concept to show that `vector<int>` has an `input_or_output_iterator`:
279+
280+
```cpp
281+
// requires /std:c++20 or later
282+
#include <iostream>
283+
284+
int main()
285+
{
286+
// Show that a vector has an input_or_output_iterator
287+
std::cout << std::boolalpha << std::input_or_output_iterator<std::vector<int>::iterator> << '\n'; // outputs true
288+
289+
// another way to test
290+
std::vector<int> v = {0,1,2};
291+
std::cout << std::boolalpha << std::input_or_output_iterator<decltype(v)::iterator>; // outputs true
292+
}
293+
```
294+
268295
## `output_iterator`
269296

270297
An `output_iterator` is a type that you can write to.
@@ -291,6 +318,25 @@ The type of the values to write.
291318
292319
An `output_iterator` is single pass. That is, it can only write to the same element once.
293320
321+
### Example: `output_iterator`
322+
323+
The following example uses the `output_iterator` concept to show that `vector<int>` has an `output_iterator`:
324+
325+
```cpp
326+
// requires /std:c++20 or later
327+
#include <iostream>
328+
#include <vector>
329+
330+
int main()
331+
{
332+
// Show that vector<int> has an output_iterator
333+
std::cout << std::boolalpha << std::output_iterator<std::vector<int>::iterator, int> << "\n"; // outputs "true"
334+
335+
// another way to test
336+
std::vector<int> v = { 0,1,2,3,4,5 };
337+
std::cout << std::boolalpha << std::output_iterator<decltype(v)::iterator, int>; // outputs true
338+
}
339+
294340
## `random_access_iterator`
295341
296342
A `random_access_iterator` can read or write by index.
@@ -319,13 +365,13 @@ The type to test to see if it's a `random_access_iterator`.
319365

320366
### Remarks
321367

322-
A `random_access_iterator` is the most flexible iterator. It has the capabilities of an `input_iterator`, `output_iterator`, `forward_iterator`, and `bidirectional_iterator`.
368+
A `random_access_iterator` has the capabilities of an `input_iterator`, `output_iterator`, `forward_iterator`, and `bidirectional_iterator`.
323369

324370
Some examples of a `random_access_iterator` are `std::vector`, `std::array`, and `std::deque`.
325371

326372
### Example: `random_access_iterator`
327373

328-
The following example shows that a `vector` of `int` is a `random_access_iterator`:
374+
The following example shows that a `vector<int>` has a `random_access_iterator`:
329375

330376
```cpp
331377
// requires /std:c++20 or later
@@ -334,7 +380,12 @@ The following example shows that a `vector` of `int` is a `random_access_iterato
334380

335381
int main()
336382
{
383+
// Show that vector<int> has a random_access_iterator
337384
std::cout << std::boolalpha << std::random_access_iterator<std::vector<int>::iterator> << '\n'; // outputs "true"
385+
386+
// another way to test
387+
std::vector<int> v = {0,1,2};
388+
std::cout << std::boolalpha << std::random_access_iterator<decltype(v)::iterator>; // outputs true
338389
}
339390
```
340391

@@ -356,15 +407,15 @@ concept sentinel_for =
356407
The iterator type.
357408
358409
*`S`*\
359-
The sentinel type to test to see if it's a sentinel for `I`.
410+
The type to test to see if it's a sentinel for `I`.
360411
361412
### Remarks
362413
363414
A sentinel is a type that can be compared to an iterator to determine if the iterator has reached the end. This concept determines if a type is a sentinel for one of the `input_or_output_iterator` types which includes `input_iterator`, `output_iterator`, `forward_iterator`, `bidirectional_iterator`, `random_access_iterator`, and `contiguous_iterator`.
364415
365416
### Example: `sentinel_for`
366417
367-
The following example shows that a `vector` of `int` is a `random_access_iterator`:
418+
The following example uses the `sentinel_for` concept to show that `std::vector<int>::iterator` is a sentinel for `vector<int>`:
368419
369420
```cpp
370421
// requires /std:c++20 or later
@@ -373,16 +424,16 @@ The following example shows that a `vector` of `int` is a `random_access_iterato
373424
374425
int main()
375426
{
376-
std::vector<int> v = { 1, 2, 3, 4, 5 };
427+
std::vector<int> v = {0, 1, 2};
377428
std::vector<int>::iterator i = v.begin();
378-
// test if std::vector<int>::iterator is a sentinel for i
429+
// show that vector<int>::iterator is a sentinel for vector<int>
379430
std::cout << std::boolalpha << std::sentinel_for<std::vector<int>::iterator, decltype(i)>; // outputs true
380431
}
381432
```
382433

383434
## `sized_sentinel_for`
384435

385-
Test that an iterator and its sentinel can be subtracted (using `-`) to find their difference in constant time.
436+
Test that an iterator and its sentinel can be subtracted (using `-`) to find the difference in constant time.
386437

387438
```cpp
388439
template<class S, class I>
@@ -407,7 +458,7 @@ The sentinel type to test.
407458
408459
### Example: `sized_sentinel_for`
409460
410-
The following example shows that a the sentinel for a `vector` can be subtracted from a vector iterator in constant time:
461+
The following example uses the `sized_sentinel_for` concept to verify that the sentinel for a `vector<int>` can be subtracted from the vectors iterator in constant time:
411462
412463
```cpp
413464
// requires /std:c++20 or later
@@ -416,12 +467,12 @@ The following example shows that a the sentinel for a `vector` can be subtracted
416467
417468
int main()
418469
{
419-
std::vector<int> v = { 1, 2, 3, 4, 5 };
470+
std::vector<int> v = { 1, 2, 3 };
420471
std::vector<int>::iterator i = v.begin();
421472
std::vector<int>::iterator end = v.end();
422-
// test if i can be subtracted from end in constant time
423-
std::cout << std::boolalpha << std::sized_sentinel_for<decltype(end), decltype(i)>; << "\n"; // outputs true
424-
std::cout << end - i; // output 5
473+
// use the sized_sentinel_for concept to verify that i can be subtracted from end in constant time
474+
std::cout << std::boolalpha << std::sized_sentinel_for<decltype(end), decltype(i)> << "\n"; // outputs true
475+
std::cout << end - i; // outputs 3
425476
}
426477
```
427478

0 commit comments

Comments
 (0)