sequence.qbk

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

[/==============================================================================
    Copyright (C) 2001-2007 Joel de Guzman, Dan Marsden, Tobias Schwinger

    Use, modification and distribution is subject to the Boost Software
    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
    http://www.boost.org/LICENSE_1_0.txt)
===============================================================================/]
[section Sequence]

Like __mpl__, the Sequence is a fundamental concept in Fusion. A Sequence
may or may not actually store or contain data. __containers__ are sequences
that hold data. __views__, on the other hand, are sequences that do not
store any data. Instead, they are proxies that impart an alternative
presentation over another sequence. All models of Sequence have an
associated __iterator__ type that can be used to iterate through the
Sequence's elements.

[heading Header]

    #include <boost/fusion/sequence.hpp>
    #include <boost/fusion/include/sequence.hpp>

[section Concepts]

Fusion Sequences are organized into a hierarchy of concepts.

[heading Traversal]

Fusion's sequence traversal related concepts parallel Fusion's
__iterator_concepts__. __forward_sequence__ is the most basic concept.
__bidirectional_sequence__ is a refinement of __forward_sequence__.
__random_access_sequence__ is a refinement of __bidirectional_sequence__.
These concepts pertain to sequence traversal.

[heading Associativity]

The __associative_sequence__ concept is orthogonal to traversal. An Associative
Sequence allows efficient retrieval of elements based on keys.

[section Forward Sequence]

[heading Description]

A Forward Sequence is a Sequence whose elements are arranged in a definite
order. The ordering is guaranteed not to change from iteration to
iteration. The requirement of a definite ordering allows the definition of
element-by-element equality (if the container's element type is Equality
Comparable) and of lexicographical ordering (if the container's element
type is LessThan Comparable).

[variablelist Notation
    [[`s`]       [A Forward Sequence]]
    [[`S`]       [A Forward Sequence type]]
    [[`o`]       [An arbitrary object]]
    [[`e`]       [A Sequence element]]
]

[heading Valid Expressions]

For any Forward Sequence the following expressions must be valid:

[table
    [[Expression]       [Return type]               [Type Requirements]     [Runtime Complexity]]
    [[`__begin__(s)`]       [__forward_iterator__]      []                      [Constant]]
    [[`__end__(s)`]         [__forward_iterator__]      []                      [Constant]]
    [[`__size__(s)`]        [__mpl_integral_constant__.
                        Convertible to int.]        []                      [Constant]]
    [[`__empty__(s)`]       [__mpl_boolean_constant__.
                        Convertible to bool.]       []                      [Constant]]
    [[`__front__(s)`]       [Any type]                  []                      [Constant]]
    [[`__front__(s) = o`]   [Any type]                  [`s` is mutable and
                                                    `e = o`, where `e`
                                                    is the first element
                                                    in the sequence, is
                                                    a valid expression.]    [Constant]]
]

[heading Result Type Expressions]

[table
    [[Expression]                   [Compile Time Complexity]]
    [[`__result_of_begin__<S>::type`]  [Amortized constant time]]
    [[`__result_of_end__<S>::type`]    [Amortized constant time]]
    [[`__result_of_size__<S>::type`]   [Unspecified]]
    [[`__result_of_empty__<S>::type`]  [Constant time]]
    [[`__result_of_front__<S>::type`]  [Amortized constant time]]
]

[heading Expression Semantics]

[table
    [[Expression]       [Semantics]]
    [[`__begin__(s)`]       [An iterator to the first element of the sequence; see __begin__.]]
    [[`__end__(s)`]         [A past-the-end iterator to the sequence; see __end__.]]
    [[`__size__(s)`]        [The size of the sequence; see __size__.]]
    [[`__empty__(s)`]       [A boolean Integral Constant `c` such that
                        `c::value == true` if and only if the sequence
                        is empty; see __empty__.]]
    [[`__front__(s)`]       [The first element in the sequence; see __front__.]]
]

[heading Invariants]

For any Forward Sequence s the following invariants always hold:

* `[__begin__(s), __end__(s))` is always a valid range.
* An __algorithm__ that iterates through the range `[__begin__(s), __end__(s))`
  will pass through every element of `s` exactly once.
* `__begin__(s)` is identical to `__end__(s))` if and only if `s` is empty.
* Two different iterations through `s` will access its elements in
  the same order.

[heading Models]

* __std_pair__
* __boost_array__
* __vector__
* __cons__
* __list__
* __set__
* __map__
* __single_view__
* __filter_view__
* __iterator_range__
* __joint_view__
* __transform_view__
* __reverse_view__
* __zip_view__

[endsect]

[section Bidirectional Sequence]

[heading Description]

A Bidirectional Sequence is a __forward_sequence__ whose iterators model
__bidirectional_iterator__.

[heading Refinement of]

__forward_sequence__

[variablelist Notation
    [[`s`]       [A Forward Sequence]]
    [[`S`]       [A Forward Sequence type]]
    [[`o`]       [An arbitrary object]]
    [[`e`]       [A Sequence element]]
]

[heading Valid Expressions]

In addition to the requirements defined in __forward_sequence__, for any
Bidirectional Sequence the following must be met:

[table
    [[Expression]       [Return type]                   [Type Requirements]     [Runtime Complexity]]
    [[`__begin__(s)`]       [__bidirectional_iterator__]    []                      [Constant]]
    [[`__end__(s)`]         [__bidirectional_iterator__]    []                      [Constant]]
    [[`__back__(s)`]        [Any type]                      []                      [Constant]]
    [[`__back__(s) = o`]    [Any type]                      [`s` is mutable and
                                                        `e = o`, where `e`
                                                        is the first element
                                                        in the sequence, is
                                                        a valid expression.]    [Constant]]
]

[heading Result Type Expressions]

[table
    [[Expression]                   [Compile Time Complexity]]
    [[`__result_of_begin__<S>::type`]  [Amortized constant time]]
    [[`__result_of_end__<S>::type`]    [Amortized constant time]]
    [[`__result_of_back__<S>::type`]   [Amortized constant time]]
]

[heading Expression Semantics]

The semantics of an expression are defined only where they differ from, or
are not defined in __forward_sequence__.

[table
    [[Expression]       [Semantics]]
    [[`__back__(s)`]        [The last element in the sequence; see __back__.]]
]

[heading Models]

* __std_pair__
* __boost_array__
* __vector__
* __reverse_view__
* __iterator_range__ (where adapted sequence is a Bidirectional Sequence)
* __transform_view__ (where adapted sequence is a Bidirectional Sequence)
* __zip_view__       (where adapted sequences are models Bidirectional Sequence)

[endsect]

[section Random Access Sequence]

[heading Description]

A Random Access Sequence is a __bidirectional_sequence__ whose iterators
model __random_access_iterator__. It guarantees constant time access to
arbitrary sequence elements.

[heading Refinement of]

__bidirectional_sequence__

[variablelist Notation
    [[`s`]       [A Random Access Sequence]]
    [[`S`]       [A Random Access Sequence type]]
    [[`N`]       [An __mpl_integral_constant__]]
    [[`o`]       [An arbitrary object]]
    [[`e`]       [A Sequence element]]
]

[heading Valid Expressions]

In addition to the requirements defined in __bidirectional_sequence__, for
any Random Access Sequence the following must be met:

[table
    [[Expression]       [Return type]                   [Type Requirements]     [Runtime Complexity]]
    [[`__begin__(s)`]       [__random_access_iterator__]    []                      [Constant]]
    [[`__end__(s)`]         [__random_access_iterator__]    []                      [Constant]]
    [[`__at__<N>(s)`]       [Any type]                      []                      [Constant]]
    [[`__at__<N>(s) = o`]   [Any type]                      [`s` is mutable and
                                                        `e = o`, where `e`
                                                        is the first element
                                                        in the sequence, is
                                                        a valid expression.]    [Constant]]
]

[heading Result Type Expressions]

[table
    [[Expression]                           [Compile Time Complexity]]
    [[`__result_of_begin__<S>::type`]          [Amortized constant time]]
    [[`__result_of_end__<S>::type`]            [Amortized constant time]]
    [[`__result_of_at__<S, N>::type`]          [Amortized constant time]]
    [[`__result_of_value_at__<S, N>::type`]    [Amortized constant time]]
]

[blurb __note__ `__result_of_at__<S, N>` returns the actual type returned by
`__at__<N>(s)`. In most cases, this is a reference. Hence, there is no way to
know the exact element type using `__result_of_at__<S, N>`.The element at `N`
may actually be a reference to begin with. For this purpose, you can use
`__result_of_value_at__<S, N>`.]

[heading Expression Semantics]

The semantics of an expression are defined only where they differ from, or
are not defined in __bidirectional_sequence__.

[table
    [[Expression]       [Semantics]]
    [[`__at__<N>(s)`]       [The Nth element from the beginning of the sequence; see __at__.]]
]

[heading Models]

* __std_pair__
* __boost_array__
* __vector__
* __reverse_view__
* __iterator_range__ (where adapted sequence is a Random Access Sequence)
* __transform_view__ (where adapted sequence is a Random Access Sequence)
* __zip_view__       (where adapted sequences are models Random Access Sequence)

[endsect]

[section Associative Sequence]

[heading Description]

An Associative Sequence allows efficient retrieval of elements based on keys.
Like associative sequences in __mpl__, and unlike associative containers in
__stl__, Fusion associative sequences have no implied ordering relation.
Instead, type identity is used to impose an equivalence relation on keys, and
the order in which sequence elements are traversed during iteration is left
unspecified. In addition, unlike __stl__, Associative Sequences have mutable
iterators. This is due to the fact that there is no associated ordering relation
and the runtime value of the keys themselves do not have any effect on the
associativity of the sequence.


[variablelist Notation
    [[`s`]       [An Associative Sequence]]
    [[`S`]       [An Associative Sequence type]]
    [[`K`]       [An arbitrary /key/ type]]
    [[`o`]       [An arbitrary object]]
    [[`e`]       [A Sequence element]]
]

[heading Valid Expressions]

For any Associative Sequence the following expressions must be valid:

[table
    [[Expression]           [Return type]               [Type Requirements]     [Runtime Complexity]]
    [[`__has_key__<K>(s)`]      [__mpl_boolean_constant__.
                            Convertible to bool.]       []                      [Constant]]
    [[`__at_key__<K>(s)`]       [Any type]                  []                      [Constant]]
    [[`__at_key__<K>(s) = o`]   [Any type]                  [`s` is mutable and
                                                        `e = o`, where `e`
                                                        is the first element
                                                        in the sequence, is
                                                        a valid expression.]    [Constant]]
]

[heading Result Type Expressions]

[table
    [[Expression]                               [Compile Time Complexity]]
    [[`__result_of_has_key__<S, K>::type`]         [Amortized constant time]]
    [[`__result_of_at_key__<S, K>::type`]          [Amortized constant time]]
    [[`__result_of_value_at_key__<S, K>::type`]    [Amortized constant time]]
]

[blurb __note__ `__result_of_at_key__<S, K>` returns the actual type returned
by `__at_key__<K>(s)`. In most cases, this is a reference. Hence, there is no
way to know the exact element type using `__result_of_at_key__<S, K>`.The
element at `K` may actually be a reference to begin with. For this purpose,
you can use `__result_of_value_at_key__<S, N>`.]

[heading Expression Semantics]

[table
    [[Expression]       [Semantics]]
    [[`__has_key__<K>(s)`]  [A boolean Integral Constant `c` such that
                        `c::value == true` if and only if there is
                        one or more elements with the key `k` in `s`;
                        see __has_key__.]]
    [[`__at_key__<K>(s)`]   [The element associated with the key
                        `K` in the sequence `s`; see __at__.]]
]

[heading Models]

* __set__
* __map__

[endsect]

[endsect]

[section Intrinsic]

Intrinsic form the essential interface of every Fusion __sequence__. __stl__
counterparts of these functions are usually implemented as member
functions. Intrinsic functions, unlike __algorithms__, are not generic
across the full __sequence__ repertoire. They need to be implemented for
each Fusion __sequence__[footnote In practice, many of intrinsic functions
have default implementations that will work in majority of cases].

[heading Header]

    #include <boost/fusion/sequence/intrinsic.hpp>
    #include <boost/fusion/include/intrinsic.hpp>

[section Functions]

[section begin]

[heading Description]

Returns an iterator pointing to the first element in the sequence.

[heading Synopsis]

    template <typename Sequence>
    typename __result_of_begin__<Sequence>::type
    begin(Sequence& seq);

    template <typename Sequence>
    typename __result_of_begin__<Sequence const>::type
    begin(Sequence const& seq);

[heading Parameters]

[table
    [[Parameter]    [Requirement]                   [Description]]
    [[`seq`]        [Model of __forward_sequence__] [The sequence we wish to get an iterator from.]]
]

[heading Expression Semantics]

    begin(seq);

[*Return type]: __forward_iterator__ if `seq` is a __forward_sequence__
else, __bidirectional_iterator__ if `seq` is a __bidirectional_sequence__
else, __random_access_iterator__ if `seq` is a __random_access_sequence__.

[*Semantics]: Returns an iterator pointing to the first element in the sequence.

[heading Header]

    #include <boost/fusion/sequence/intrinsic/begin.hpp>
    #include <boost/fusion/include/begin.hpp>

[heading Example]

    __vector__<int, int, int> v(1, 2, 3);
    assert(__deref__(begin(v)) == 1);

[endsect]

[section end]

[heading Description]

Returns an iterator pointing to one element past the end of the sequence.

[heading Synopsis]

    template <typename Sequence>
    typename __result_of_end__<Sequence>::type
    end(Sequence& seq);

    template <typename Sequence>
    typename __result_of_end__<Sequence const>::type
    end(Sequence const& seq);

[heading Parameters]

[table
    [[Parameter]    [Requirement]                   [Description]]
    [[`seq`]        [Model of __forward_sequence__] [The sequence we wish to get an iterator from.]]
]

[heading Expression Semantics]

    end(seq);

[*Return type]: __forward_iterator__ if `seq` is a __forward_sequence__
else, __bidirectional_iterator__ if `seq` is a __bidirectional_sequence__
else, __random_access_iterator__ if `seq` is a __random_access_sequence__.

[*Semantics]: Returns an iterator pointing to one element past the end of
the sequence.

[heading Header]

    #include <boost/fusion/sequence/intrinsic/end.hpp>
    #include <boost/fusion/include/end.hpp>

[heading Example]

    __vector__<int, int, int> v(1, 2, 3);
    assert(__deref__(__prior__(end(v))) == 3);

[endsect]

[section empty]

[heading Description]