ceph/src/boost/libs/iterator/doc/quickbook/facade.qbk

   1
   2 [section:facade Iterator Facade]
   3
   4 While the iterator interface is rich, there is a core subset of the
   5 interface that is necessary for all the functionality.  We have
   6 identified the following core behaviors for iterators:
   7
   8 * dereferencing
   9 * incrementing
  10 * decrementing
  11 * equality comparison
  12 * random-access motion
  13 * distance measurement
  14
  15 In addition to the behaviors listed above, the core interface elements
  16 include the associated types exposed through iterator traits:
  17 `value_type`, `reference`, `difference_type`, and
  18 `iterator_category`.
  19
  20 Iterator facade uses the Curiously Recurring Template
  21 Pattern (CRTP) [Cop95]_ so that the user can specify the behavior
  22 of `iterator_facade` in a derived class.  Former designs used
  23 policy objects to specify the behavior, but that approach was
  24 discarded for several reasons:
  25
  26 1. the creation and eventual copying of the policy object may create
  27    overhead that can be avoided with the current approach.
  28
  29 2. 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
  34 3. 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
  46 The user of `iterator_facade` derives his iterator class from a
  47 specialization of `iterator_facade` and passes the derived
  48 iterator class as `iterator_facade`\ 's first template parameter.
  49 The order of the other template parameters have been carefully
  50 chosen to take advantage of useful defaults.  For example, when
  51 defining a constant lvalue iterator, the user can pass a
  52 const-qualified version of the iterator's `value_type` as
  53 `iterator_facade`\ 's `Value` parameter and omit the
  54 `Reference` parameter which follows.
  55
  56 The derived iterator class must define member functions implementing
  57 the iterator's core behaviors.  The following table describes
  58 expressions which are required to be valid depending on the category
  59 of the derived iterator type.  These member functions are described
  60 briefly below and in more detail in the iterator facade
  61 requirements.
  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
  96 In addition to implementing the core interface functions, an iterator
  97 derived from `iterator_facade` typically defines several
  98 constructors. To model any of the standard iterator concepts, the
  99 iterator must at least have a copy constructor. Also, if the iterator
 100 type `X` is meant to be automatically interoperate with another
 101 iterator type `Y` (as with constant and mutable iterators) then
 102 there must be an implicit conversion from `X` to `Y` or from `Y`
 103 to `X` (but not both), typically implemented as a conversion
 104 constructor. Finally, if the iterator is to model Forward Traversal
 105 Iterator or a more-refined iterator concept, a default constructor is
 106 required.
 107
 108 [h2 Iterator Core Access]
 109
 110 `iterator_facade` and the operator implementations need to be able
 111 to access the core member functions in the derived class.  Making the
 112 core member functions public would expose an implementation detail to
 113 the user.  The design used here ensures that implementation details do
 114 not appear in the public interface of the derived iterator type.
 115
 116 Preventing direct access to the core member functions has two
 117 advantages.  First, there is no possibility for the user to accidently
 118 use a member function of the iterator when a member of the value_type
 119 was intended.  This has been an issue with smart pointer
 120 implementations in the past.  The second and main advantage is that
 121 library implementers can freely exchange a hand-rolled iterator
 122 implementation for one based on `iterator_facade` without fear of
 123 breaking code that was accessing the public core member functions
 124 directly.
 125
 126 In a naive implementation, keeping the derived class' core member
 127 functions private would require it to grant friendship to
 128 `iterator_facade` and each of the seven operators.  In order to
 129 reduce the burden of limiting access, `iterator_core_access` is
 130 provided, a class that acts as a gateway to the core member functions
 131 in the derived iterator class.  The author of the derived class only
 132 needs to grant friendship to `iterator_core_access` to make his core
 133 member functions available to the library.
 134
 135
 136 `iterator_core_access` will be typically implemented as an empty
 137 class containing only private static member functions which invoke the
 138 iterator core member functions. There is, however, no need to
 139 standardize the gateway protocol.  Note that even if
 140 `iterator_core_access` used public member functions it would not
 141 open a safety loophole, as every core member function preserves the
 142 invariants of the iterator.
 143
 144 [h2 `operator\[\]`]
 145
 146 The indexing operator for a generalized iterator presents special
 147 challenges.  A random access iterator's `operator[]` is only
 148 required to return something convertible to its `value_type`.
 149 Requiring that it return an lvalue would rule out currently-legal
 150 random-access iterators which hold the referenced value in a data
 151 member (e.g. |counting|_), because `*(p+n)` is a reference
 152 into the temporary iterator `p+n`, which is destroyed when
 153 `operator[]` returns.
 154
 155 .. |counting| replace:: `counting_iterator`
 156
 157 Writable iterators built with `iterator_facade` implement the
 158 semantics required by the preferred resolution to `issue 299`_ and
 159 adopted by proposal n1550_: the result of `p[n]` is an object
 160 convertible to the iterator's `value_type`, and `p[n] = x` is
 161 equivalent to `*(p + n) = x` (Note: This result object may be
 162 implemented as a proxy containing a copy of `p+n`).  This approach
 163 will work properly for any random-access iterator regardless of the
 164 other details of its implementation.  A user who knows more about
 165 the implementation of her iterator is free to implement an
 166 `operator[]` that returns an lvalue in the derived iterator
 167 class; it will hide the one supplied by `iterator_facade` from
 168 clients 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
 178 The `reference` type of a readable iterator (and today's input
 179 iterator) need not in fact be a reference, so long as it is
 180 convertible to the iterator's `value_type`.  When the `value_type`
 181 is a class, however, it must still be possible to access members
 182 through `operator->`.  Therefore, an iterator whose `reference`
 183 type is not in fact a reference must return a proxy containing a copy
 184 of the referenced value from its `operator->`.
 185
 186 The return types for `iterator_facade`\ 's `operator->` and
 187 `operator[]` are not explicitly specified. Instead, those types
 188 are described in terms of a set of requirements, which must be
 189 satisfied 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
 288 The `iterator_category` member of `iterator_facade` is
 289
 290 .. parsed-literal::
 291
 292   *iterator-category*\ (CategoryOrTraversal, value_type, reference)
 293
 294 where *iterator-category* is defined as follows:
 295
 296 .. include:: facade_iterator_category.rst
 297
 298 The `enable_if_interoperable` template used above is for exposition
 299 purposes.  The member operators should only be in an overload set
 300 provided the derived types `Dr1` and `Dr2` are interoperable,
 301 meaning that at least one of the types is convertible to the other.  The
 302 `enable_if_interoperable` approach uses SFINAE to take the operators
 303 out of the overload set when the types are not interoperable.
 304 The operators should behave *as-if* `enable_if_interoperable`
 305 were 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
 324 The following table describes the typical valid expressions on
 325 `iterator_facade`\ 's `Derived` parameter, depending on the
 326 iterator concept(s) it will model.  The operations in the first
 327 column 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
 331 In the table below, `F` is `iterator_facade<X,V,C,R,D>`, `a` is an
 332 object 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
 334 object of a single pass iterator type interoperable with `X`, and `z`
 335 is a constant object of a random access traversal iterator type
 336 interoperable 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
 389 The operations in this section are described in terms of operations on
 390 the core interface of `Derived` which may be inaccessible
 391 (i.e. private).  The implementation should access these operations
 392 through 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()`
 403 Otherwise returns an object of unspecified type such that,
 404 `(*static_cast<Derived const*>(this))->m` is equivalent to `(w = **static_cast<Derived const*>(this),
 405 w.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]