123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637 |
- [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://www.open-std.org/JTC1/SC22/WG21/docs/papers/2003/n1550.htm
- .. _`issue 299`: http://www.open-std.org/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, reference, value_type)
- 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:]
- [pre
- 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:]
- [pre
- 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:]
- [pre
- 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:]
- [pre
- 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:]
- [pre
- 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:]
- [pre
- 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:]
- [pre
- 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:]
- [pre
- 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]
|