1 2[section:facade Iterator Facade] 3 4While the iterator interface is rich, there is a core subset of the 5interface that is necessary for all the functionality. We have 6identified the following core behaviors for iterators: 7 8* dereferencing 9* incrementing 10* decrementing 11* equality comparison 12* random-access motion 13* distance measurement 14 15In addition to the behaviors listed above, the core interface elements 16include the associated types exposed through iterator traits: 17`value_type`, `reference`, `difference_type`, and 18`iterator_category`. 19 20Iterator facade uses the Curiously Recurring Template 21Pattern (CRTP) [Cop95]_ so that the user can specify the behavior 22of `iterator_facade` in a derived class. Former designs used 23policy objects to specify the behavior, but that approach was 24discarded for several reasons: 25 261. the creation and eventual copying of the policy object may create 27 overhead that can be avoided with the current approach. 28 292. The policy object approach does not allow for custom constructors 30 on the created iterator types, an essential feature if 31 `iterator_facade` should be used in other library 32 implementations. 33 343. Without the use of CRTP, the standard requirement that an 35 iterator's `operator++` returns the iterator type itself 36 would mean that all iterators built with the library would 37 have to be specializations of `iterator_facade<...>`, rather 38 than something more descriptive like 39 `indirect_iterator<T*>`. Cumbersome type generator 40 metafunctions would be needed to build new parameterized 41 iterators, and a separate `iterator_adaptor` layer would be 42 impossible. 43 44[h2 Usage] 45 46The user of `iterator_facade` derives his iterator class from a 47specialization of `iterator_facade` and passes the derived 48iterator class as `iterator_facade`\ 's first template parameter. 49The order of the other template parameters have been carefully 50chosen to take advantage of useful defaults. For example, when 51defining a constant lvalue iterator, the user can pass a 52const-qualified version of the iterator's `value_type` as 53`iterator_facade`\ 's `Value` parameter and omit the 54`Reference` parameter which follows. 55 56The derived iterator class must define member functions implementing 57the iterator's core behaviors. The following table describes 58expressions which are required to be valid depending on the category 59of the derived iterator type. These member functions are described 60briefly below and in more detail in the iterator facade 61requirements. 62 63[table Core Interface 64 [ 65 [Expression] 66 [Effects] 67 ] 68 [ 69 [`i.dereference()`] 70 [Access the value referred to] 71 ] 72 [ 73 [`i.equal(j)`] 74 [Compare for equality with `j`] 75 ] 76 [ 77 [`i.increment()`] 78 [Advance by one position] 79 ] 80 [ 81 [`i.decrement()`] 82 [Retreat by one position] 83 ] 84 [ 85 [`i.advance(n)`] 86 [Advance by `n` positions] 87 ] 88 [ 89 [`i.distance_to(j)`] 90 [Measure the distance to `j`] 91 ] 92] 93 94[/ .. Should we add a comment that a zero overhead implementation of iterator_facade is possible with proper inlining?] 95 96In addition to implementing the core interface functions, an iterator 97derived from `iterator_facade` typically defines several 98constructors. To model any of the standard iterator concepts, the 99iterator must at least have a copy constructor. Also, if the iterator 100type `X` is meant to be automatically interoperate with another 101iterator type `Y` (as with constant and mutable iterators) then 102there must be an implicit conversion from `X` to `Y` or from `Y` 103to `X` (but not both), typically implemented as a conversion 104constructor. Finally, if the iterator is to model Forward Traversal 105Iterator or a more-refined iterator concept, a default constructor is 106required. 107 108[h2 Iterator Core Access] 109 110`iterator_facade` and the operator implementations need to be able 111to access the core member functions in the derived class. Making the 112core member functions public would expose an implementation detail to 113the user. The design used here ensures that implementation details do 114not appear in the public interface of the derived iterator type. 115 116Preventing direct access to the core member functions has two 117advantages. First, there is no possibility for the user to accidently 118use a member function of the iterator when a member of the value_type 119was intended. This has been an issue with smart pointer 120implementations in the past. The second and main advantage is that 121library implementers can freely exchange a hand-rolled iterator 122implementation for one based on `iterator_facade` without fear of 123breaking code that was accessing the public core member functions 124directly. 125 126In a naive implementation, keeping the derived class' core member 127functions private would require it to grant friendship to 128`iterator_facade` and each of the seven operators. In order to 129reduce the burden of limiting access, `iterator_core_access` is 130provided, a class that acts as a gateway to the core member functions 131in the derived iterator class. The author of the derived class only 132needs to grant friendship to `iterator_core_access` to make his core 133member functions available to the library. 134 135 136`iterator_core_access` will be typically implemented as an empty 137class containing only private static member functions which invoke the 138iterator core member functions. There is, however, no need to 139standardize the gateway protocol. Note that even if 140`iterator_core_access` used public member functions it would not 141open a safety loophole, as every core member function preserves the 142invariants of the iterator. 143 144[h2 `operator[]`] 145 146The indexing operator for a generalized iterator presents special 147challenges. A random access iterator's `operator[]` is only 148required to return something convertible to its `value_type`. 149Requiring that it return an lvalue would rule out currently-legal 150random-access iterators which hold the referenced value in a data 151member (e.g. |counting|_), because `*(p+n)` is a reference 152into the temporary iterator `p+n`, which is destroyed when 153`operator[]` returns. 154 155.. |counting| replace:: `counting_iterator` 156 157Writable iterators built with `iterator_facade` implement the 158semantics required by the preferred resolution to `issue 299`_ and 159adopted by proposal n1550_: the result of `p[n]` is an object 160convertible to the iterator's `value_type`, and `p[n] = x` is 161equivalent to `*(p + n) = x` (Note: This result object may be 162implemented as a proxy containing a copy of `p+n`). This approach 163will work properly for any random-access iterator regardless of the 164other details of its implementation. A user who knows more about 165the implementation of her iterator is free to implement an 166`operator[]` that returns an lvalue in the derived iterator 167class; it will hide the one supplied by `iterator_facade` from 168clients of her iterator. 169 170.. _n1550: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2003/n1550.htm 171 172.. _`issue 299`: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#299 173 174.. _`operator arrow`: 175 176[h2 `operator->`] 177 178The `reference` type of a readable iterator (and today's input 179iterator) need not in fact be a reference, so long as it is 180convertible to the iterator's `value_type`. When the `value_type` 181is a class, however, it must still be possible to access members 182through `operator->`. Therefore, an iterator whose `reference` 183type is not in fact a reference must return a proxy containing a copy 184of the referenced value from its `operator->`. 185 186The return types for `iterator_facade`\ 's `operator->` and 187`operator[]` are not explicitly specified. Instead, those types 188are described in terms of a set of requirements, which must be 189satisfied by the `iterator_facade` implementation. 190 191.. [Cop95] [Coplien, 1995] Coplien, J., Curiously Recurring Template 192 Patterns, C++ Report, February 1995, pp. 24-27. 193 194[section:facade_reference Reference] 195 196 template < 197 class Derived 198 , class Value 199 , class CategoryOrTraversal 200 , class Reference = Value& 201 , class Difference = ptrdiff_t 202 > 203 class iterator_facade { 204 public: 205 typedef remove_const<Value>::type value_type; 206 typedef Reference reference; 207 typedef Value\* pointer; 208 typedef Difference difference_type; 209 typedef /* see below__ \*/ iterator_category; 210 211 reference operator\*() const; 212 /* see below__ \*/ operator->() const; 213 /* see below__ \*/ operator[](difference_type n) const; 214 Derived& operator++(); 215 Derived operator++(int); 216 Derived& operator--(); 217 Derived operator--(int); 218 Derived& operator+=(difference_type n); 219 Derived& operator-=(difference_type n); 220 Derived operator-(difference_type n) const; 221 protected: 222 typedef iterator_facade iterator_facade\_; 223 }; 224 225 // Comparison operators 226 template <class Dr1, class V1, class TC1, class R1, class D1, 227 class Dr2, class V2, class TC2, class R2, class D2> 228 typename enable_if_interoperable<Dr1,Dr2,bool>::type // exposition 229 operator ==(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, 230 iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); 231 232 template <class Dr1, class V1, class TC1, class R1, class D1, 233 class Dr2, class V2, class TC2, class R2, class D2> 234 typename enable_if_interoperable<Dr1,Dr2,bool>::type 235 operator !=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, 236 iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); 237 238 template <class Dr1, class V1, class TC1, class R1, class D1, 239 class Dr2, class V2, class TC2, class R2, class D2> 240 typename enable_if_interoperable<Dr1,Dr2,bool>::type 241 operator <(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, 242 iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); 243 244 template <class Dr1, class V1, class TC1, class R1, class D1, 245 class Dr2, class V2, class TC2, class R2, class D2> 246 typename enable_if_interoperable<Dr1,Dr2,bool>::type 247 operator <=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, 248 iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); 249 250 template <class Dr1, class V1, class TC1, class R1, class D1, 251 class Dr2, class V2, class TC2, class R2, class D2> 252 typename enable_if_interoperable<Dr1,Dr2,bool>::type 253 operator >(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, 254 iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); 255 256 template <class Dr1, class V1, class TC1, class R1, class D1, 257 class Dr2, class V2, class TC2, class R2, class D2> 258 typename enable_if_interoperable<Dr1,Dr2,bool>::type 259 operator >=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, 260 iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); 261 262 // Iterator difference 263 template <class Dr1, class V1, class TC1, class R1, class D1, 264 class Dr2, class V2, class TC2, class R2, class D2> 265 /* see below__ \*/ 266 operator-(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, 267 iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); 268 269 // Iterator addition 270 template <class Dr, class V, class TC, class R, class D> 271 Derived operator+ (iterator_facade<Dr,V,TC,R,D> const&, 272 typename Derived::difference_type n); 273 274 template <class Dr, class V, class TC, class R, class D> 275 Derived operator+ (typename Derived::difference_type n, 276 iterator_facade<Dr,V,TC,R,D> const&); 277 278__ `iterator category`_ 279 280__ `operator arrow`_ 281 282__ brackets_ 283 284__ minus_ 285 286.. _`iterator category`: 287 288The `iterator_category` member of `iterator_facade` is 289 290.. parsed-literal:: 291 292 *iterator-category*\ (CategoryOrTraversal, reference, value_type) 293 294where *iterator-category* is defined as follows: 295 296.. include:: facade_iterator_category.rst 297 298The `enable_if_interoperable` template used above is for exposition 299purposes. The member operators should only be in an overload set 300provided the derived types `Dr1` and `Dr2` are interoperable, 301meaning that at least one of the types is convertible to the other. The 302`enable_if_interoperable` approach uses SFINAE to take the operators 303out of the overload set when the types are not interoperable. 304The operators should behave *as-if* `enable_if_interoperable` 305were defined to be: 306 307 template <bool, typename> enable_if_interoperable_impl 308 {}; 309 310 template <typename T> enable_if_interoperable_impl<true,T> 311 { typedef T type; }; 312 313 template<typename Dr1, typename Dr2, typename T> 314 struct enable_if_interoperable 315 : enable_if_interoperable_impl< 316 is_convertible<Dr1,Dr2>::value || is_convertible<Dr2,Dr1>::value 317 , T 318 > 319 {}; 320 321 322[h2 Requirements] 323 324The following table describes the typical valid expressions on 325`iterator_facade`\ 's `Derived` parameter, depending on the 326iterator concept(s) it will model. The operations in the first 327column must be made accessible to member functions of class 328`iterator_core_access`. In addition, 329`static_cast<Derived*>(iterator_facade*)` shall be well-formed. 330 331In the table below, `F` is `iterator_facade<X,V,C,R,D>`, `a` is an 332object of type `X`, `b` and `c` are objects of type `const X`, 333`n` is an object of `F::difference_type`, `y` is a constant 334object of a single pass iterator type interoperable with `X`, and `z` 335is a constant object of a random access traversal iterator type 336interoperable with `X`. 337 338.. _`core operations`: 339 340.. topic:: `iterator_facade` Core Operations 341 342[table Core Operations 343 [ 344 [Expression] 345 [Return Type] 346 [Assertion/Note] 347 [Used to implement Iterator Concept(s)] 348 ] 349 [ 350 [`c.dereference()`] 351 [`F::reference`] 352 [] 353 [Readable Iterator, Writable Iterator] 354 ] 355 [ 356 [`c.equal(y)`] 357 [convertible to bool] 358 [true iff `c` and `y` refer to the same position] 359 [Single Pass Iterator] 360 ] 361 [ 362 [`a.increment()`] 363 [unused] 364 [] 365 [Incrementable Iterator] 366 ] 367 [ 368 [`a.decrement()`] 369 [unused] 370 [] 371 [Bidirectional Traversal Iterator] 372 ] 373 [ 374 [`a.advance(n)`] 375 [unused] 376 [] 377 [Random Access Traversal Iterator] 378 ] 379 [ 380 [`c.distance_to(z)`] 381 [convertible to `F::difference_type`] 382 [equivalent to `distance(c, X(z))`.] 383 [Random Access Traversal Iterator] 384 ] 385] 386 387[h2 Operations] 388 389The operations in this section are described in terms of operations on 390the core interface of `Derived` which may be inaccessible 391(i.e. private). The implementation should access these operations 392through member functions of class `iterator_core_access`. 393 394 reference operator*() const; 395 396[*Returns:] `static_cast<Derived const*>(this)->dereference()` 397 398 operator->() const; (see below__) 399 400__ `operator arrow`_ 401 402[*Returns:] If `reference` is a reference type, an object of type `pointer` equal to: `&static_cast<Derived const*>(this)->dereference()` 403Otherwise returns an object of unspecified type such that, 404`(*static_cast<Derived const*>(this))->m` is equivalent to `(w = **static_cast<Derived const*>(this), 405w.m)` for some temporary object `w` of type `value_type`. 406 407.. _brackets: 408 409 *unspecified* operator[](difference_type n) const; 410 411[*Returns:] an object convertible to `value_type`. For constant 412 objects `v` of type `value_type`, and `n` of type 413 `difference_type`, `(*this)[n] = v` is equivalent to 414 `*(*this + n) = v`, and `static_cast<value_type 415 const&>((*this)[n])` is equivalent to 416 `static_cast<value_type const&>(*(*this + n))` 417 418 Derived& operator++(); 419 420[*Effects:] 421 422 static_cast<Derived*>(this)->increment(); 423 return *static_cast<Derived*>(this); 424 425 Derived operator++(int); 426 427[*Effects:] 428 429 Derived tmp(static_cast<Derived const*>(this)); 430 ++*this; 431 return tmp; 432 433 Derived& operator--(); 434 435[*Effects:] 436 437 static_cast<Derived*>(this)->decrement(); 438 return *static_cast<Derived*>(this); 439 440 Derived operator--(int); 441 442[*Effects:] 443 444 Derived tmp(static_cast<Derived const*>(this)); 445 --*this; 446 return tmp; 447 448 449 Derived& operator+=(difference_type n); 450 451[*Effects:] 452 453 static_cast<Derived*>(this)->advance(n); 454 return *static_cast<Derived*>(this); 455 456 457 Derived& operator-=(difference_type n); 458 459[*Effects:] 460 461 static_cast<Derived*>(this)->advance(-n); 462 return *static_cast<Derived*>(this); 463 464 465 Derived operator-(difference_type n) const; 466 467[*Effects:] 468 469 Derived tmp(static_cast<Derived const*>(this)); 470 return tmp -= n; 471 472 template <class Dr, class V, class TC, class R, class D> 473 Derived operator+ (iterator_facade<Dr,V,TC,R,D> const&, 474 typename Derived::difference_type n); 475 476 template <class Dr, class V, class TC, class R, class D> 477 Derived operator+ (typename Derived::difference_type n, 478 iterator_facade<Dr,V,TC,R,D> const&); 479 480[*Effects:] 481 482 Derived tmp(static_cast<Derived const*>(this)); 483 return tmp += n; 484 485 template <class Dr1, class V1, class TC1, class R1, class D1, 486 class Dr2, class V2, class TC2, class R2, class D2> 487 typename enable_if_interoperable<Dr1,Dr2,bool>::type 488 operator ==(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, 489 iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); 490 491[*Returns:] 492 493[pre 494 if `is_convertible<Dr2,Dr1>::value` 495 496 then 497 `((Dr1 const&)lhs).equal((Dr2 const&)rhs)`. 498 499 Otherwise, 500 `((Dr2 const&)rhs).equal((Dr1 const&)lhs)`. 501] 502 503 504 template <class Dr1, class V1, class TC1, class R1, class D1, 505 class Dr2, class V2, class TC2, class R2, class D2> 506 typename enable_if_interoperable<Dr1,Dr2,bool>::type 507 operator !=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, 508 iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); 509 510[*Returns:] 511 512[pre 513 if `is_convertible<Dr2,Dr1>::value` 514 515 then 516 `!((Dr1 const&)lhs).equal((Dr2 const&)rhs)`. 517 518 Otherwise, 519 `!((Dr2 const&)rhs).equal((Dr1 const&)lhs)`. 520] 521 522 523 template <class Dr1, class V1, class TC1, class R1, class D1, 524 class Dr2, class V2, class TC2, class R2, class D2> 525 typename enable_if_interoperable<Dr1,Dr2,bool>::type 526 operator <(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, 527 iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); 528 529[*Returns:] 530 531[pre 532 if `is_convertible<Dr2,Dr1>::value` 533 534 then 535 `((Dr1 const&)lhs).distance_to((Dr2 const&)rhs) < 0`. 536 537 Otherwise, 538 `((Dr2 const&)rhs).distance_to((Dr1 const&)lhs) > 0`. 539] 540 541 542 template <class Dr1, class V1, class TC1, class R1, class D1, 543 class Dr2, class V2, class TC2, class R2, class D2> 544 typename enable_if_interoperable<Dr1,Dr2,bool>::type 545 operator <=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, 546 iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); 547 548[*Returns:] 549 550[pre 551 if `is_convertible<Dr2,Dr1>::value` 552 553 then 554 `((Dr1 const&)lhs).distance_to((Dr2 const&)rhs) <= 0`. 555 556 Otherwise, 557 `((Dr2 const&)rhs).distance_to((Dr1 const&)lhs) >= 0`. 558] 559 560 561 template <class Dr1, class V1, class TC1, class R1, class D1, 562 class Dr2, class V2, class TC2, class R2, class D2> 563 typename enable_if_interoperable<Dr1,Dr2,bool>::type 564 operator >(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, 565 iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); 566 567[*Returns:] 568 569[pre 570 if `is_convertible<Dr2,Dr1>::value` 571 572 then 573 `((Dr1 const&)lhs).distance_to((Dr2 const&)rhs) > 0`. 574 575 Otherwise, 576 `((Dr2 const&)rhs).distance_to((Dr1 const&)lhs) < 0`. 577] 578 579 580 template <class Dr1, class V1, class TC1, class R1, class D1, 581 class Dr2, class V2, class TC2, class R2, class D2> 582 typename enable_if_interoperable<Dr1,Dr2,bool>::type 583 operator >=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, 584 iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); 585 586[*Returns:] 587 588[pre 589 if `is_convertible<Dr2,Dr1>::value` 590 591 then 592 `((Dr1 const&)lhs).distance_to((Dr2 const&)rhs) >= 0`. 593 594 Otherwise, 595 `((Dr2 const&)rhs).distance_to((Dr1 const&)lhs) <= 0`. 596] 597 598.. _minus: 599 600 601 template <class Dr1, class V1, class TC1, class R1, class D1, 602 class Dr2, class V2, class TC2, class R2, class D2> 603 typename enable_if_interoperable<Dr1,Dr2,difference>::type 604 operator -(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, 605 iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); 606 607[*Return Type:] 608 609[pre 610 if `is_convertible<Dr2,Dr1>::value` 611 612 then 613 `difference` shall be 614 `iterator_traits<Dr1>::difference_type`. 615 616 Otherwise 617 `difference` shall be `iterator_traits<Dr2>::difference_type` 618] 619 620[*Returns:] 621 622[pre 623 if `is_convertible<Dr2,Dr1>::value` 624 625 then 626 `-((Dr1 const&)lhs).distance_to((Dr2 const&)rhs)`. 627 628 Otherwise, 629 `((Dr2 const&)rhs).distance_to((Dr1 const&)lhs)`. 630] 631 632 633[endsect] 634 635[include facade_tutorial.qbk] 636 637[endsect] 638