| |
| [section:facade Iterator Facade] |
| |
| While the iterator interface is rich, there is a core subset of the |
| interface that is necessary for all the functionality. We have |
| identified the following core behaviors for iterators: |
| |
| * dereferencing |
| * incrementing |
| * decrementing |
| * equality comparison |
| * random-access motion |
| * distance measurement |
| |
| In addition to the behaviors listed above, the core interface elements |
| include the associated types exposed through iterator traits: |
| `value_type`, `reference`, `difference_type`, and |
| `iterator_category`. |
| |
| Iterator facade uses the Curiously Recurring Template |
| Pattern (CRTP) [Cop95]_ so that the user can specify the behavior |
| of `iterator_facade` in a derived class. Former designs used |
| policy objects to specify the behavior, but that approach was |
| discarded for several reasons: |
| |
| 1. the creation and eventual copying of the policy object may create |
| overhead that can be avoided with the current approach. |
| |
| 2. The policy object approach does not allow for custom constructors |
| on the created iterator types, an essential feature if |
| `iterator_facade` should be used in other library |
| implementations. |
| |
| 3. Without the use of CRTP, the standard requirement that an |
| iterator's `operator++` returns the iterator type itself |
| would mean that all iterators built with the library would |
| have to be specializations of `iterator_facade<...>`, rather |
| than something more descriptive like |
| `indirect_iterator<T*>`. Cumbersome type generator |
| metafunctions would be needed to build new parameterized |
| iterators, and a separate `iterator_adaptor` layer would be |
| impossible. |
| |
| [h2 Usage] |
| |
| The user of `iterator_facade` derives his iterator class from a |
| specialization of `iterator_facade` and passes the derived |
| iterator class as `iterator_facade`\ 's first template parameter. |
| The order of the other template parameters have been carefully |
| chosen to take advantage of useful defaults. For example, when |
| defining a constant lvalue iterator, the user can pass a |
| const-qualified version of the iterator's `value_type` as |
| `iterator_facade`\ 's `Value` parameter and omit the |
| `Reference` parameter which follows. |
| |
| The derived iterator class must define member functions implementing |
| the iterator's core behaviors. The following table describes |
| expressions which are required to be valid depending on the category |
| of the derived iterator type. These member functions are described |
| briefly below and in more detail in the iterator facade |
| requirements. |
| |
| [table Core Interface |
| [ |
| [Expression] |
| [Effects] |
| ] |
| [ |
| [`i.dereference()`] |
| [Access the value referred to] |
| [ |
| [`i.equal(j)`] |
| [Compare for equality with `j`] |
| ] |
| [ |
| [`i.increment()`] |
| [Advance by one position] |
| ] |
| [ |
| [`i.decrement()`] |
| [Retreat by one position] |
| ] |
| [ |
| [`i.advance(n)`] |
| [Advance by `n` positions] |
| [ |
| [`i.distance_to(j)`] |
| [Measure the distance to `j`] |
| ] |
| ] |
| |
| [/ .. Should we add a comment that a zero overhead implementation of iterator_facade is possible with proper inlining?] |
| |
| In addition to implementing the core interface functions, an iterator |
| derived from `iterator_facade` typically defines several |
| constructors. To model any of the standard iterator concepts, the |
| iterator must at least have a copy constructor. Also, if the iterator |
| type `X` is meant to be automatically interoperate with another |
| iterator type `Y` (as with constant and mutable iterators) then |
| there must be an implicit conversion from `X` to `Y` or from `Y` |
| to `X` (but not both), typically implemented as a conversion |
| constructor. Finally, if the iterator is to model Forward Traversal |
| Iterator or a more-refined iterator concept, a default constructor is |
| required. |
| |
| [h2 Iterator Core Access] |
| |
| `iterator_facade` and the operator implementations need to be able |
| to access the core member functions in the derived class. Making the |
| core member functions public would expose an implementation detail to |
| the user. The design used here ensures that implementation details do |
| not appear in the public interface of the derived iterator type. |
| |
| Preventing direct access to the core member functions has two |
| advantages. First, there is no possibility for the user to accidently |
| use a member function of the iterator when a member of the value_type |
| was intended. This has been an issue with smart pointer |
| implementations in the past. The second and main advantage is that |
| library implementers can freely exchange a hand-rolled iterator |
| implementation for one based on `iterator_facade` without fear of |
| breaking code that was accessing the public core member functions |
| directly. |
| |
| In a naive implementation, keeping the derived class' core member |
| functions private would require it to grant friendship to |
| `iterator_facade` and each of the seven operators. In order to |
| reduce the burden of limiting access, `iterator_core_access` is |
| provided, a class that acts as a gateway to the core member functions |
| in the derived iterator class. The author of the derived class only |
| needs to grant friendship to `iterator_core_access` to make his core |
| member functions available to the library. |
| |
| |
| `iterator_core_access` will be typically implemented as an empty |
| class containing only private static member functions which invoke the |
| iterator core member functions. There is, however, no need to |
| standardize the gateway protocol. Note that even if |
| `iterator_core_access` used public member functions it would not |
| open a safety loophole, as every core member function preserves the |
| invariants of the iterator. |
| |
| [h2 `operator\[\]`] |
| |
| The indexing operator for a generalized iterator presents special |
| challenges. A random access iterator's `operator[]` is only |
| required to return something convertible to its `value_type`. |
| Requiring that it return an lvalue would rule out currently-legal |
| random-access iterators which hold the referenced value in a data |
| member (e.g. |counting|_), because `*(p+n)` is a reference |
| into the temporary iterator `p+n`, which is destroyed when |
| `operator[]` returns. |
| |
| .. |counting| replace:: `counting_iterator` |
| |
| Writable iterators built with `iterator_facade` implement the |
| semantics required by the preferred resolution to `issue 299`_ and |
| adopted by proposal n1550_: the result of `p[n]` is an object |
| convertible to the iterator's `value_type`, and `p[n] = x` is |
| equivalent to `*(p + n) = x` (Note: This result object may be |
| implemented as a proxy containing a copy of `p+n`). This approach |
| will work properly for any random-access iterator regardless of the |
| other details of its implementation. A user who knows more about |
| the implementation of her iterator is free to implement an |
| `operator[]` that returns an lvalue in the derived iterator |
| class; it will hide the one supplied by `iterator_facade` from |
| clients of her iterator. |
| |
| .. _n1550: http://anubis.dkuug.dk/JTC1/SC22/WG21/docs/papers/2003/n1550.html |
| |
| .. _`issue 299`: http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#299 |
| |
| .. _`operator arrow`: |
| |
| [h2 `operator->`] |
| |
| The `reference` type of a readable iterator (and today's input |
| iterator) need not in fact be a reference, so long as it is |
| convertible to the iterator's `value_type`. When the `value_type` |
| is a class, however, it must still be possible to access members |
| through `operator->`. Therefore, an iterator whose `reference` |
| type is not in fact a reference must return a proxy containing a copy |
| of the referenced value from its `operator->`. |
| |
| The return types for `iterator_facade`\ 's `operator->` and |
| `operator[]` are not explicitly specified. Instead, those types |
| are described in terms of a set of requirements, which must be |
| satisfied by the `iterator_facade` implementation. |
| |
| .. [Cop95] [Coplien, 1995] Coplien, J., Curiously Recurring Template |
| Patterns, C++ Report, February 1995, pp. 24-27. |
| |
| [section:facade_reference Reference] |
| |
| template < |
| class Derived |
| , class Value |
| , class CategoryOrTraversal |
| , class Reference = Value& |
| , class Difference = ptrdiff_t |
| > |
| class iterator_facade { |
| public: |
| typedef remove_const<Value>::type value_type; |
| typedef Reference reference; |
| typedef Value\* pointer; |
| typedef Difference difference_type; |
| typedef /* see below__ \*/ iterator_category; |
| |
| reference operator\*() const; |
| /* see below__ \*/ operator->() const; |
| /* see below__ \*/ operator[](difference_type n) const; |
| Derived& operator++(); |
| Derived operator++(int); |
| Derived& operator--(); |
| Derived operator--(int); |
| Derived& operator+=(difference_type n); |
| Derived& operator-=(difference_type n); |
| Derived operator-(difference_type n) const; |
| protected: |
| typedef iterator_facade iterator_facade\_; |
| }; |
| |
| // Comparison operators |
| template <class Dr1, class V1, class TC1, class R1, class D1, |
| class Dr2, class V2, class TC2, class R2, class D2> |
| typename enable_if_interoperable<Dr1,Dr2,bool>::type // exposition |
| operator ==(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, |
| iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); |
| |
| template <class Dr1, class V1, class TC1, class R1, class D1, |
| class Dr2, class V2, class TC2, class R2, class D2> |
| typename enable_if_interoperable<Dr1,Dr2,bool>::type |
| operator !=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, |
| iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); |
| |
| template <class Dr1, class V1, class TC1, class R1, class D1, |
| class Dr2, class V2, class TC2, class R2, class D2> |
| typename enable_if_interoperable<Dr1,Dr2,bool>::type |
| operator <(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, |
| iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); |
| |
| template <class Dr1, class V1, class TC1, class R1, class D1, |
| class Dr2, class V2, class TC2, class R2, class D2> |
| typename enable_if_interoperable<Dr1,Dr2,bool>::type |
| operator <=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, |
| iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); |
| |
| template <class Dr1, class V1, class TC1, class R1, class D1, |
| class Dr2, class V2, class TC2, class R2, class D2> |
| typename enable_if_interoperable<Dr1,Dr2,bool>::type |
| operator >(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, |
| iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); |
| |
| template <class Dr1, class V1, class TC1, class R1, class D1, |
| class Dr2, class V2, class TC2, class R2, class D2> |
| typename enable_if_interoperable<Dr1,Dr2,bool>::type |
| operator >=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, |
| iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); |
| |
| // Iterator difference |
| template <class Dr1, class V1, class TC1, class R1, class D1, |
| class Dr2, class V2, class TC2, class R2, class D2> |
| /* see below__ \*/ |
| operator-(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, |
| iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); |
| |
| // Iterator addition |
| template <class Dr, class V, class TC, class R, class D> |
| Derived operator+ (iterator_facade<Dr,V,TC,R,D> const&, |
| typename Derived::difference_type n); |
| |
| template <class Dr, class V, class TC, class R, class D> |
| Derived operator+ (typename Derived::difference_type n, |
| iterator_facade<Dr,V,TC,R,D> const&); |
| |
| __ `iterator category`_ |
| |
| __ `operator arrow`_ |
| |
| __ brackets_ |
| |
| __ minus_ |
| |
| .. _`iterator category`: |
| |
| The `iterator_category` member of `iterator_facade` is |
| |
| .. parsed-literal:: |
| |
| *iterator-category*\ (CategoryOrTraversal, value_type, reference) |
| |
| where *iterator-category* is defined as follows: |
| |
| .. include:: facade_iterator_category.rst |
| |
| The `enable_if_interoperable` template used above is for exposition |
| purposes. The member operators should only be in an overload set |
| provided the derived types `Dr1` and `Dr2` are interoperable, |
| meaning that at least one of the types is convertible to the other. The |
| `enable_if_interoperable` approach uses SFINAE to take the operators |
| out of the overload set when the types are not interoperable. |
| The operators should behave *as-if* `enable_if_interoperable` |
| were defined to be: |
| |
| template <bool, typename> enable_if_interoperable_impl |
| {}; |
| |
| template <typename T> enable_if_interoperable_impl<true,T> |
| { typedef T type; }; |
| |
| template<typename Dr1, typename Dr2, typename T> |
| struct enable_if_interoperable |
| : enable_if_interoperable_impl< |
| is_convertible<Dr1,Dr2>::value || is_convertible<Dr2,Dr1>::value |
| , T |
| > |
| {}; |
| |
| |
| [h2 Requirements] |
| |
| The following table describes the typical valid expressions on |
| `iterator_facade`\ 's `Derived` parameter, depending on the |
| iterator concept(s) it will model. The operations in the first |
| column must be made accessible to member functions of class |
| `iterator_core_access`. In addition, |
| `static_cast<Derived*>(iterator_facade*)` shall be well-formed. |
| |
| In the table below, `F` is `iterator_facade<X,V,C,R,D>`, `a` is an |
| object of type `X`, `b` and `c` are objects of type `const X`, |
| `n` is an object of `F::difference_type`, `y` is a constant |
| object of a single pass iterator type interoperable with `X`, and `z` |
| is a constant object of a random access traversal iterator type |
| interoperable with `X`. |
| |
| .. _`core operations`: |
| |
| .. topic:: `iterator_facade` Core Operations |
| |
| [table Core Operations |
| [ |
| [Expression] |
| [Return Type] |
| [Assertion/Note] |
| [Used to implement Iterator Concept(s)] |
| ] |
| [ |
| [`c.dereference()`] |
| [`F::reference`] |
| [] |
| [Readable Iterator, Writable Iterator] |
| ] |
| [ |
| [`c.equal(y)`] |
| [convertible to bool] |
| [true iff `c` and `y` refer to the same position] |
| [Single Pass Iterator] |
| ] |
| [ |
| [`a.increment()`] |
| [unused] |
| [] |
| [Incrementable Iterator] |
| ] |
| [ |
| [`a.decrement()`] |
| [unused] |
| [] |
| [Bidirectional Traversal Iterator] |
| ] |
| [ |
| [`a.advance(n)`] |
| [unused] |
| [] |
| [Random Access Traversal Iterator] |
| ] |
| [ |
| [`c.distance_to(z)`] |
| [convertible to `F::difference_type`] |
| [equivalent to `distance(c, X(z))`.] |
| [Random Access Traversal Iterator] |
| ] |
| ] |
| |
| [h2 Operations] |
| |
| The operations in this section are described in terms of operations on |
| the core interface of `Derived` which may be inaccessible |
| (i.e. private). The implementation should access these operations |
| through member functions of class `iterator_core_access`. |
| |
| reference operator*() const; |
| |
| [*Returns:] `static_cast<Derived const*>(this)->dereference()` |
| |
| operator->() const; (see below__) |
| |
| __ `operator arrow`_ |
| |
| [*Returns:] If `reference` is a reference type, an object of type `pointer` equal to: `&static_cast<Derived const*>(this)->dereference()` |
| Otherwise returns an object of unspecified type such that, |
| `(*static_cast<Derived const*>(this))->m` is equivalent to `(w = **static_cast<Derived const*>(this), |
| w.m)` for some temporary object `w` of type `value_type`. |
| |
| .. _brackets: |
| |
| *unspecified* operator[](difference_type n) const; |
| |
| [*Returns:] an object convertible to `value_type`. For constant |
| objects `v` of type `value_type`, and `n` of type |
| `difference_type`, `(*this)[n] = v` is equivalent to |
| `*(*this + n) = v`, and `static_cast<value_type |
| const&>((*this)[n])` is equivalent to |
| `static_cast<value_type const&>(*(*this + n))` |
| |
| Derived& operator++(); |
| |
| [*Effects:] |
| |
| static_cast<Derived*>(this)->increment(); |
| return *static_cast<Derived*>(this); |
| |
| Derived operator++(int); |
| |
| [*Effects:] |
| |
| Derived tmp(static_cast<Derived const*>(this)); |
| ++*this; |
| return tmp; |
| |
| Derived& operator--(); |
| |
| [*Effects:] |
| |
| static_cast<Derived*>(this)->decrement(); |
| return *static_cast<Derived*>(this); |
| |
| Derived operator--(int); |
| |
| [*Effects:] |
| |
| Derived tmp(static_cast<Derived const*>(this)); |
| --*this; |
| return tmp; |
| |
| |
| Derived& operator+=(difference_type n); |
| |
| [*Effects:] |
| |
| static_cast<Derived*>(this)->advance(n); |
| return *static_cast<Derived*>(this); |
| |
| |
| Derived& operator-=(difference_type n); |
| |
| [*Effects:] |
| |
| static_cast<Derived*>(this)->advance(-n); |
| return *static_cast<Derived*>(this); |
| |
| |
| Derived operator-(difference_type n) const; |
| |
| [*Effects:] |
| |
| Derived tmp(static_cast<Derived const*>(this)); |
| return tmp -= n; |
| |
| template <class Dr, class V, class TC, class R, class D> |
| Derived operator+ (iterator_facade<Dr,V,TC,R,D> const&, |
| typename Derived::difference_type n); |
| |
| template <class Dr, class V, class TC, class R, class D> |
| Derived operator+ (typename Derived::difference_type n, |
| iterator_facade<Dr,V,TC,R,D> const&); |
| |
| [*Effects:] |
| |
| Derived tmp(static_cast<Derived const*>(this)); |
| return tmp += n; |
| |
| template <class Dr1, class V1, class TC1, class R1, class D1, |
| class Dr2, class V2, class TC2, class R2, class D2> |
| typename enable_if_interoperable<Dr1,Dr2,bool>::type |
| operator ==(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, |
| iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); |
| |
| [*Returns:] |
| |
| if `is_convertible<Dr2,Dr1>::value` |
| |
| then |
| `((Dr1 const&)lhs).equal((Dr2 const&)rhs)`. |
| |
| Otherwise, |
| `((Dr2 const&)rhs).equal((Dr1 const&)lhs)`. |
| |
| |
| template <class Dr1, class V1, class TC1, class R1, class D1, |
| class Dr2, class V2, class TC2, class R2, class D2> |
| typename enable_if_interoperable<Dr1,Dr2,bool>::type |
| operator !=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, |
| iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); |
| |
| [*Returns:] |
| |
| if `is_convertible<Dr2,Dr1>::value` |
| |
| then |
| `!((Dr1 const&)lhs).equal((Dr2 const&)rhs)`. |
| |
| Otherwise, |
| `!((Dr2 const&)rhs).equal((Dr1 const&)lhs)`. |
| |
| |
| template <class Dr1, class V1, class TC1, class R1, class D1, |
| class Dr2, class V2, class TC2, class R2, class D2> |
| typename enable_if_interoperable<Dr1,Dr2,bool>::type |
| operator <(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, |
| iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); |
| |
| [*Returns:] |
| |
| if `is_convertible<Dr2,Dr1>::value` |
| |
| then |
| `((Dr1 const&)lhs).distance_to((Dr2 const&)rhs) < 0`. |
| |
| Otherwise, |
| `((Dr2 const&)rhs).distance_to((Dr1 const&)lhs) > 0`. |
| |
| |
| template <class Dr1, class V1, class TC1, class R1, class D1, |
| class Dr2, class V2, class TC2, class R2, class D2> |
| typename enable_if_interoperable<Dr1,Dr2,bool>::type |
| operator <=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, |
| iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); |
| |
| [*Returns:] |
| |
| if `is_convertible<Dr2,Dr1>::value` |
| |
| then |
| `((Dr1 const&)lhs).distance_to((Dr2 const&)rhs) <= 0`. |
| |
| Otherwise, |
| `((Dr2 const&)rhs).distance_to((Dr1 const&)lhs) >= 0`. |
| |
| |
| template <class Dr1, class V1, class TC1, class R1, class D1, |
| class Dr2, class V2, class TC2, class R2, class D2> |
| typename enable_if_interoperable<Dr1,Dr2,bool>::type |
| operator >(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, |
| iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); |
| |
| [*Returns:] |
| |
| if `is_convertible<Dr2,Dr1>::value` |
| |
| then |
| `((Dr1 const&)lhs).distance_to((Dr2 const&)rhs) > 0`. |
| |
| Otherwise, |
| `((Dr2 const&)rhs).distance_to((Dr1 const&)lhs) < 0`. |
| |
| |
| template <class Dr1, class V1, class TC1, class R1, class D1, |
| class Dr2, class V2, class TC2, class R2, class D2> |
| typename enable_if_interoperable<Dr1,Dr2,bool>::type |
| operator >=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, |
| iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); |
| |
| [*Returns:] |
| |
| if `is_convertible<Dr2,Dr1>::value` |
| |
| then |
| `((Dr1 const&)lhs).distance_to((Dr2 const&)rhs) >= 0`. |
| |
| Otherwise, |
| `((Dr2 const&)rhs).distance_to((Dr1 const&)lhs) <= 0`. |
| |
| .. _minus: |
| |
| |
| template <class Dr1, class V1, class TC1, class R1, class D1, |
| class Dr2, class V2, class TC2, class R2, class D2> |
| typename enable_if_interoperable<Dr1,Dr2,difference>::type |
| operator -(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, |
| iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); |
| |
| [*Return Type:] |
| |
| if `is_convertible<Dr2,Dr1>::value` |
| |
| then |
| `difference` shall be |
| `iterator_traits<Dr1>::difference_type`. |
| |
| Otherwise |
| `difference` shall be `iterator_traits<Dr2>::difference_type` |
| |
| [*Returns:] |
| |
| if `is_convertible<Dr2,Dr1>::value` |
| |
| then |
| `-((Dr1 const&)lhs).distance_to((Dr2 const&)rhs)`. |
| |
| Otherwise, |
| `((Dr2 const&)rhs).distance_to((Dr1 const&)lhs)`. |
| |
| |
| [endsect] |
| |
| [include facade_tutorial.qbk] |
| |
| [endsect] |