Squashed 'third_party/boostorg/iterator/' content from commit b2adecb
Change-Id: I284a73816f9cc846742923879275b84c6e0c915c
git-subtree-dir: third_party/boostorg/iterator
git-subtree-split: b2adecb951af025698618f19a3c838bd314966dc
diff --git a/doc/quickbook/facade.qbk b/doc/quickbook/facade.qbk
new file mode 100644
index 0000000..7ca3809
--- /dev/null
+++ b/doc/quickbook/facade.qbk
@@ -0,0 +1,637 @@
+
+[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]