[ceph.git] / ceph / src / boost / libs / mpl / doc / src / refmanual / ForwardIterator.rst

.. Iterators/Concepts//Forward Iterator |10

Forward Iterator
================

Description
-----------

A |Forward Iterator| ``i`` is a type that represents a positional reference
to an element of a |Forward Sequence|. It allows to access the element through 
a dereference operation, and provides a way to obtain an iterator to 
the next element in a sequence. 

.. A [Forward Iterator] guarantees a linear traversal over 
   the sequence.


Definitions
-----------

* An iterator can be `dereferenceable`, meaning that ``deref<i>::type``
  is a well-defined expression. 

* An iterator is `past-the-end` if it points beyond the last element of a 
  sequence; past-the-end iterators are non-dereferenceable.

* An iterator ``i`` is `incrementable` if there is a "next" iterator, that 
  is, if ``next<i>::type`` expression is well-defined; past-the-end iterators are 
  not incrementable.

* Two iterators into the same sequence are `equivalent` if they have the same
  type.

* An iterator ``j`` is `reachable` from an iterator ``i`` if , after recursive 
  application of ``next`` metafunction to ``i`` a finite number of times, ``i`` 
  is equivalent to ``j``.

* The notation [``i``,\ ``j``) refers to a `range` of iterators beginning with 
  ``i`` and up to but not including ``j``.

* The range [``i``,\ ``j``) is a `valid range` if ``j`` is reachable from ``i``. 


Expression requirements
-----------------------

+-----------------------+-------------------------------------------+---------------------------+
| Expression            | Type                                      | Complexity                |
+=======================+===========================================+===========================+
| ``deref<i>::type``    | Any type                                  | Amortized constant time   |
+-----------------------+-------------------------------------------+---------------------------+
| ``next<i>::type``     | |Forward Iterator|                        | Amortized constant time   |
+-----------------------+-------------------------------------------+---------------------------+
| ``i::category``       | |Integral Constant|, convertible          | Constant time             |
|                       | to ``forward_iterator_tag``               |                           |
+-----------------------+-------------------------------------------+---------------------------+


Expression semantics
--------------------


.. parsed-literal::

    typedef deref<i>::type j;

:Precondition:
    ``i`` is dereferenceable 

:Semantics:
    ``j`` is identical to the type of the pointed element  


.. ..........................................................................

.. parsed-literal::

    typedef next<i>::type j;

:Precondition:
    ``i`` is incrementable 

:Semantics:
    ``j`` is the next iterator in a sequence 

:Postcondition:
    ``j`` is dereferenceable or past-the-end  


.. ..........................................................................

.. parsed-literal::

    typedef i::category c;

:Semantics:
    ``c`` is identical to the iterator's category tag


Invariants
----------

For any forward iterators ``i`` and ``j`` the following invariants always hold: 

* ``i`` and ``j`` are equivalent if and only if they are pointing to the same 
  element.

* If ``i`` is dereferenceable, and ``j`` is equivalent to ``i``, then ``j`` is 
  dereferenceable as well.

* If ``i`` and ``j`` are equivalent and dereferenceable, then ``deref<i>::type`` 
  and ``deref<j>::type`` are identical. 

* If ``i`` is incrementable, and ``j`` is equivalent to ``i``, then ``j`` is 
  incrementable as well.

* If ``i`` and ``j`` are equivalent and incrementable, then ``next<i>::type`` 
  and ``next<j>::type`` are equivalent. 


See also
--------

|Iterators|, |Bidirectional Iterator|, |Forward Sequence|, |deref|, |next|
Commit	Line	Data
7c673cae FG	1	.. Iterators/Concepts//Forward Iterator \|10
	2
	3	Forward Iterator
	4	================
	5
	6	Description
	7	-----------
	8
	9	A \|Forward Iterator\| ``i`` is a type that represents a positional reference
	10	to an element of a \|Forward Sequence\|. It allows to access the element through
	11	a dereference operation, and provides a way to obtain an iterator to
	12	the next element in a sequence.
	13
	14	.. A [Forward Iterator] guarantees a linear traversal over
	15	the sequence.
	16
	17
	18	Definitions
	19	-----------
	20
	21	* An iterator can be `dereferenceable`, meaning that ``deref<i>::type``
	22	is a well-defined expression.
	23
	24	* An iterator is `past-the-end` if it points beyond the last element of a
	25	sequence; past-the-end iterators are non-dereferenceable.
	26
	27	* An iterator ``i`` is `incrementable` if there is a "next" iterator, that
	28	is, if ``next<i>::type`` expression is well-defined; past-the-end iterators are
	29	not incrementable.
	30
	31	* Two iterators into the same sequence are `equivalent` if they have the same
	32	type.
	33
	34	* An iterator ``j`` is `reachable` from an iterator ``i`` if , after recursive
	35	application of ``next`` metafunction to ``i`` a finite number of times, ``i``
	36	is equivalent to ``j``.
	37
	38	* The notation [``i``,\ ``j``) refers to a `range` of iterators beginning with
	39	``i`` and up to but not including ``j``.
	40
	41	* The range [``i``,\ ``j``) is a `valid range` if ``j`` is reachable from ``i``.
	42
	43
	44	Expression requirements
	45	-----------------------
	46
	47	+-----------------------+-------------------------------------------+---------------------------+
	48	\| Expression \| Type \| Complexity \|
	49	+=======================+===========================================+===========================+
	50	\| ``deref<i>::type`` \| Any type \| Amortized constant time \|
	51	+-----------------------+-------------------------------------------+---------------------------+
	52	\| ``next<i>::type`` \| \|Forward Iterator\| \| Amortized constant time \|
	53	+-----------------------+-------------------------------------------+---------------------------+
	54	\| ``i::category`` \| \|Integral Constant\|, convertible \| Constant time \|
	55	\| \| to ``forward_iterator_tag`` \| \|
	56	+-----------------------+-------------------------------------------+---------------------------+
	57
	58
	59	Expression semantics
	60	--------------------
	61
	62
	63	.. parsed-literal::
	64
65	typedef deref<i>::type j;
66
67	:Precondition:
68	``i`` is dereferenceable
69
70	:Semantics:
71	``j`` is identical to the type of the pointed element
72
73
74	.. ..........................................................................
75
76	.. parsed-literal::
77
78	typedef next<i>::type j;
79
80	:Precondition:
81	``i`` is incrementable
82
83	:Semantics:
84	``j`` is the next iterator in a sequence
85
86	:Postcondition:
87	``j`` is dereferenceable or past-the-end
88
89
90	.. ..........................................................................
91
92	.. parsed-literal::
93
94	typedef i::category c;
95
96	:Semantics:
97	``c`` is identical to the iterator's category tag
98
99
100	Invariants
101	----------
102
103	For any forward iterators ``i`` and ``j`` the following invariants always hold:
104
105	* ``i`` and ``j`` are equivalent if and only if they are pointing to the same
106	element.
107
108	* If ``i`` is dereferenceable, and ``j`` is equivalent to ``i``, then ``j`` is
109	dereferenceable as well.
110
111	* If ``i`` and ``j`` are equivalent and dereferenceable, then ``deref<i>::type``
112	and ``deref<j>::type`` are identical.
113
114	* If ``i`` is incrementable, and ``j`` is equivalent to ``i``, then ``j`` is
115	incrementable as well.
116
117	* If ``i`` and ``j`` are equivalent and incrementable, then ``next<i>::type``
118	and ``next<j>::type`` are equivalent.
119
120
121	See also
122	--------
123
124	\|Iterators\|, \|Bidirectional Iterator\|, \|Forward Sequence\|, \|deref\|, \|next\|
125
126
127