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