1[section:concepts Iterator Concepts] 2 3[section:access Access] 4 5[section:readable Readable Iterator Concept] 6 7A class or built-in type `X` models the *Readable Iterator* concept 8for value type `T` if, in addition to `X` being Assignable and 9Copy Constructible, the following expressions are valid and respect 10the stated semantics. `U` is the type of any specified member of 11type `T`. 12 13[table Readable Iterator Requirements (in addition to Assignable and Copy Constructible) 14 [ 15 [Expression] 16 [Return Type] 17 [Note/Precondition] 18 ] 19 [ 20 [`iterator_traits<X>::value_type`] 21 [`T`] 22 [Any non-reference, non cv-qualified type] 23 ] 24 [ 25 [`*a`] 26 [ Convertible to `T`] 27 [pre: `a` is dereferenceable. If `a == b` then `*a` is equivalent to `*b`.] 28 ] 29 [ 30 [`a->m`] 31 [`U&`] 32 [pre: `(*a).m` is well-defined. Equivalent to `(*a).m`.] 33 ] 34] 35 36[endsect] 37 38[section:writable Writable Iterator Concept] 39 40A class or built-in type `X` models the *Writable Iterator* concept 41if, in addition to `X` being Copy Constructible, the following 42expressions are valid and respect the stated semantics. Writable 43Iterators have an associated *set of value types*. 44 45[table Writable Iterator Requirements (in addition to Copy Constructible) 46 [ 47 [Expression] 48 [Return Type] 49 [Precondition] 50 ] 51 [ 52 [`*a = o` ] 53 [] 54 [pre: The type of `o` is in the set of value types of `X`] 55 ] 56] 57 58[endsect] 59 60[section:swappable Swappable Iterator Concept] 61 62A class or built-in type `X` models the *Swappable Iterator* concept 63if, in addition to `X` being Copy Constructible, the following 64expressions are valid and respect the stated semantics. 65 66[table Swappable Iterator Requirements (in addition to Copy Constructible) 67 [ 68 [Expression] 69 [Return Type] 70 [Postcondition] 71 ] 72 [ 73 [`iter_swap(a, b)`] 74 [`void`] 75 [the pointed to values are exchanged] 76 ] 77] 78 79[blurb *Note:* An iterator that is a model of the *Readable* and *Writable Iterator* concepts 80 is also a model of *Swappable Iterator*. *--end note*] 81 82[endsect] 83 84[section:lvalue Lvalue Iterator Concept] 85 86The *Lvalue Iterator* concept adds the requirement that the return 87type of `operator*` type be a reference to the value type of the 88iterator. 89 90[table Lvalue Iterator Requirements 91 [ 92 [Expression] 93 [Return Type] 94 [Note/Assertion] 95 ] 96 [ 97 [`*a` ] 98 [`T&` ] 99 [ 100 `T` is *cv* `iterator_traits<X>::value_type` where *cv* is an optional cv-qualification. 101 pre: `a` is dereferenceable. If `a == b` then `*a` is equivalent to `*b`. 102 ] 103 ] 104] 105 106[endsect] 107 108[endsect] 109 110[section:traversal Traversal] 111 112[section:incrementable Incrementable Iterator Concept] 113 114A class or built-in type `X` models the *Incrementable Iterator* 115concept if, in addition to `X` being Assignable and Copy 116Constructible, the following expressions are valid and respect the 117stated semantics. 118 119[table Incrementable Iterator Requirements (in addition to Assignable, Copy Constructible) 120 [ 121 [Expression ] 122 [Return Type] 123 [Assertion/Semantics ] 124 ] 125 [ 126 [`++r` ] 127 [`X&` ] 128 [`&r == &++r`] 129 ] 130 [ 131 [`r++` ] 132 [`X` ] 133 [`` 134 { 135 X tmp = r; 136 ++r; 137 return tmp; 138 } 139 ``] 140 ] 141 [ 142 [`iterator_traversal<X>::type`] 143 [Convertible to `incrementable_traversal_tag`] 144 [] 145 ] 146] 147 148[endsect] 149 150[section:single_pass Single Pass Iterator Concept] 151 152A class or built-in type `X` models the *Single Pass Iterator* 153concept if the following expressions are valid and respect the stated 154semantics. 155 156[table Single Pass Iterator Requirements (in addition to Incrementable Iterator and Equality Comparable) 157 [ 158 [Expression] 159 [Return Type] 160 [Assertion/Semantics / Pre-/Post-condition] 161 ] 162 [ 163 [`++r`] 164 [`X&`] 165 [pre:[br]`r` is dereferenceable;[br]post:[br]`r` is dereferenceable or[br]`r` is past-the-end] 166 ] 167 [ 168 [`a == b`] 169 [convertible to `bool`] 170 [`==` is an equivalence relation over its domain] 171 ] 172 [ 173 [`a != b`] 174 [convertible to `bool`] 175 [`!(a == b)`] 176 ] 177 [ 178 [`iterator_traits<X>::difference_type`] 179 [A signed integral type representing the distance between iterators] 180 [] 181 ] 182 [ 183 [`iterator_traversal<X>::type`] 184 [Convertible to`single_pass_traversal_tag`] 185 [] 186 ] 187] 188 189[endsect] 190 191[section:forward Forward Traversal Concept] 192 193A class or built-in type `X` models the *Forward Traversal* 194concept if, in addition to `X` meeting the requirements of Default 195Constructible and Single Pass Iterator, the following expressions are 196valid and respect the stated semantics. 197 198[table Forward Traversal Iterator Requirements (in addition to Default Constructible and Single Pass Iterator) 199 [ 200 [Expression] 201 [Return Type] 202 [Assertion/Note] 203 ] 204 [ 205 [`X u;`] 206 [`X&`] 207 [note: `u` may have a singular value.] 208 ] 209 [ 210 [`++r`] 211 [`X&`] 212 [`r == s` and `r` is dereferenceable implies `++r == ++s.`] 213 ] 214 [ 215 [`iterator_traversal<X>::type`] 216 [Convertible to `forward_traversal_tag`] 217 [] 218 ] 219] 220 221[endsect] 222 223[section:bidirectional Bidirectional Traversal Concept] 224 225A class or built-in type `X` models the *Bidirectional Traversal* 226concept if, in addition to `X` meeting the requirements of Forward 227Traversal Iterator, the following expressions are valid and respect 228the stated semantics. 229 230[table Bidirectional Traversal Iterator Requirements (in addition to Forward Traversal Iterator) 231 [ 232 [Expression] 233 [Return Type] 234 [Assertion/Semantics/Pre-/Post-condition] 235 ] 236 [ 237 [`--r`] 238 [`X&`] 239 [pre: there exists `s` such that `r == ++s`.[br] post: `s` is dereferenceable. `--(++r) == r`. `--r == --s` implies `r == s`. `&r == &--r`.] 240 ] 241 [ 242 [`r--`] 243 [convertible to `const X&`] 244 [`` 245 { 246 X tmp = r; 247 --r; 248 return tmp; 249 } 250 ``] 251 ] 252 [ 253 [`iterator_traversal<X>::type`] 254 [Convertible to `bidirectional_traversal_tag`] 255 [] 256 ] 257] 258 259[endsect] 260 261[section:random_access Random Access Traversal Concept] 262 263A class or built-in type `X` models the *Random Access Traversal* 264concept if the following expressions are valid and respect the stated 265semantics. In the table below, `Distance` is 266`iterator_traits<X>::difference_type` and `n` represents a 267constant object of type `Distance`. 268 269[table Random Access Traversal Iterator Requirements (in addition to Bidirectional Traversal) 270 [ 271 [Expression] 272 [Return Type] 273 [Operational Semantics] 274 [Assertion/Precondition] 275 ] 276 [ 277 [`r += n`] 278 [ `X&`] 279 [`` 280 { 281 Distance m = n; 282 if (m >= 0) 283 while (m--) 284 ++r; 285 else 286 while (m++) 287 --r; 288 return r; 289 } 290 ``] 291 [ ] 292 ] 293 [ 294 [`a + n`, `n + a`] 295 [`X`] 296 [`` 297 { 298 X tmp = a; 299 return tmp+= n; 300 } 301 ``] 302 [] 303 ] 304 [ 305 [`r -= n`] 306 [`X&`] 307 [`return r += -n`] 308 [] 309 ] 310 [ 311 [`a - n`] 312 [`X`] 313 [`` 314 { 315 X tmp = a; 316 return tmp-= n; 317 } 318 ``] 319 [] 320 ] 321 [ 322 [`b - a`] 323 [`Distance`] 324 [`a < b ? distance(a,b) : -distance(b,a)`] 325 [pre: there exists a value `n` of `Distance` such that `a + n == b`. `b == a + (b - a)`.] 326 ] 327 [ 328 [`a[n]`] 329 [convertible to T] 330 [`*(a + n)`] 331 [pre: a is a *Readable Iterator*] 332 ] 333 [ 334 [`a[n] = v`] 335 [convertible to T] 336 [`*(a + n) = v`] 337 [pre: a is a *Writable iterator*] 338 ] 339 [ 340 [`a < b`] 341 [convertible to `bool`] 342 [`b - a > 0`] 343 [`<` is a total ordering relation] 344 ] 345 [ 346 [`a > b`] 347 [convertible to `bool`] 348 [`b < a`] 349 [`>` is a total ordering relation] 350 ] 351 [ 352 [`a >= b`] 353 [convertible to `bool`] 354 [`!(a < b)`] 355 [] 356 ] 357 [ 358 [`a <= b`] 359 [convertible to `bool`] 360 [`!(a > b)`] 361 [] 362 ] 363 [ 364 [`iterator_traversal<X>::type`] 365 [convertible to `random_access_traversal_tag`] 366 [] 367 [] 368 ] 369] 370 371[endsect] 372 373[endsect] 374 375[endsect] 376