]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | .. Sequences/Concepts//Forward Sequence |10 |
2 | ||
3 | Forward Sequence | |
4 | ================ | |
5 | ||
6 | Description | |
7 | ----------- | |
8 | ||
9 | A |Forward Sequence| is an MPL concept representing a compile-time sequence of | |
10 | elements. Sequence elements are | |
11 | types, and are accessible through |iterators|. The |begin| and |end| metafunctions | |
12 | provide iterators delimiting the range of the sequence | |
13 | elements. A sequence guarantees that its elements are arranged in a definite, | |
14 | but possibly unspecified, order. Every MPL sequence is a |Forward Sequence|. | |
15 | ||
16 | Definitions | |
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 | ||
25 | Expression requirements | |
26 | ----------------------- | |
27 | ||
28 | For 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 | ||
45 | Expression 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 | ||
63 | Invariants | |
64 | ---------- | |
65 | ||
66 | For 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 | ||
78 | Models | |
79 | ------ | |
80 | ||
81 | * |vector| | |
82 | * |map| | |
83 | * |range_c| | |
84 | * |iterator_range| | |
85 | * |filter_view| | |
86 | ||
87 | See also | |
88 | -------- | |
89 | ||
90 | |Sequences|, |Bidirectional Sequence|, |Forward Iterator|, |begin| / |end|, |size|, |empty|, |front| | |
91 | ||
92 | ||
93 |