1.. Sequences/Concepts//Forward Sequence |10
2
3Forward Sequence
4================
5
6Description
7-----------
8
9A |Forward Sequence| is an MPL concept representing a compile-time sequence of
10elements. Sequence elements are
11types, and are accessible through |iterators|. The |begin| and |end| metafunctions
12provide iterators delimiting the range of the sequence
13elements.  A sequence guarantees that its elements are arranged in a definite,
14but possibly unspecified, order. Every MPL sequence is a |Forward Sequence|.
15
16Definitions
17-----------
18
19* The *size* of a sequence is the number of elements it contains. The size is a
20  nonnegative number.
21
22* A sequence is *empty* if its size is zero.
23
24
25Expression requirements
26-----------------------
27
28For any |Forward Sequence| ``s`` the following expressions must be valid:
29
30+---------------------------+-----------------------------------+---------------------------+
31| Expression                | Type                              | Complexity                |
32+===========================+===================================+===========================+
33| ``begin<s>::type``        | |Forward Iterator|                | Amortized constant time   |
34+---------------------------+-----------------------------------+---------------------------+
35| ``end<s>::type``          | |Forward Iterator|                | Amortized constant time   |
36+---------------------------+-----------------------------------+---------------------------+
37| ``size<s>::type``         | |Integral Constant|               | Unspecified               |
38+---------------------------+-----------------------------------+---------------------------+
39| ``empty<s>::type``        | Boolean |Integral Constant|       | Constant time             |
40+---------------------------+-----------------------------------+---------------------------+
41| ``front<s>::type``        | Any type                          | Amortized constant time   |
42+---------------------------+-----------------------------------+---------------------------+
43
44
45Expression semantics
46--------------------
47
48+---------------------------+-----------------------------------------------------------------------+
49| Expression                | Semantics                                                             |
50+===========================+=======================================================================+
51| ``begin<s>::type``        | An iterator to the first element of the sequence; see |begin|.        |
52+---------------------------+-----------------------------------------------------------------------+
53| ``end<s>::type``          | A past-the-end iterator to the sequence; see |end|.                   |
54+---------------------------+-----------------------------------------------------------------------+
55| ``size<s>::type``         | The size of the sequence; see |size|.                                 |
56+---------------------------+-----------------------------------------------------------------------+
57| ``empty<s>::type``        | |true if and only if| the sequence is empty; see |empty|.             |
58+---------------------------+-----------------------------------------------------------------------+
59| ``front<s>::type``        | The first element in the sequence; see |front|.                       |
60+---------------------------+-----------------------------------------------------------------------+
61
62
63Invariants
64----------
65
66For any |Forward Sequence| ``s`` the following invariants always hold:
67
68* [``begin<s>::type``, ``end<s>::type``) is always a valid range.
69
70* An algorithm that iterates through the range [``begin<s>::type``, ``end<s>::type``)
71  will pass through every element of ``s`` exactly once.
72
73* ``begin<s>::type`` is identical to ``end<s>::type`` if and only if ``s`` is empty.
74
75* Two different iterations through ``s`` will access its elements in the same order.
76
77
78Models
79------
80
81* |vector|
82* |map|
83* |range_c|
84* |iterator_range|
85* |filter_view|
86
87See also
88--------
89
90|Sequences|, |Bidirectional Sequence|, |Forward Iterator|, |begin| / |end|, |size|, |empty|, |front|
91
92
93.. copyright:: Copyright �  2001-2009 Aleksey Gurtovoy and David Abrahams
94   Distributed under the Boost Software License, Version 1.0. (See accompanying
95   file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
96