algorithm.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 Algorithm]

[heading Lazy Evaluation]

Unlike __mpl__, Fusion algorithms are lazy and non sequence-type
preserving. What does that mean? It means that when you operate on a
sequence through a Fusion algorithm that returns a sequence, the sequence
returned may not be of the same class as the original. This is by design.
Runtime efficiency is given a high priority. Like __mpl__, and unlike
__stl__, fusion algorithms are functional in nature such that algorithms
are non mutating (no side effects). However, due to the high cost of
returning full sequences such as vectors and lists, /Views/ are returned
from Fusion algorithms instead. For example, the __transform__ algorithm
does not actually return a transformed version of the original sequence.
__transform__ returns a __transform_view__. This view holds a reference to
the original sequence plus the transform function. Iteration over the
__transform_view__ will apply the transform function over the sequence
elements on demand. This /lazy/ evaluation scheme allows us to chain as
many algorithms as we want without incurring a high runtime penalty.

[heading Sequence Extension]

The /lazy/ evaluation scheme where __algorithms__ return __views__ also
allows operations such as __push_back__ to be totally generic. In Fusion,
__push_back__ is actually a generic algorithm that works on all sequences.
Given an input sequence `s` and a value `x`, Fusion's __push_back__
algorithm simply returns a __joint_view__: a view that holds a reference to
the original sequence `s` and the value `x`. Functions that were once
sequence specific and need to be implemented N times over N different
sequences are now implemented only once. That is to say that Fusion
sequences are cheaply extensible. However, an important caveat is that the
result of a sequence extending operation like __push_back__ does not retain
the properties of the original sequence such as associativity of __set__(s).
To regain the original sequence, __conversion__ functions are provided. You
may use one of the __conversion__ functions to convert back to the original
sequence type.

[heading Header]

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

[section Iteration]

The iteration algorithms provide the fundamental algorithms for traversing
a sequence repeatedly applying an operation to its elements.

[heading Header]

    #include <boost/fusion/algorithm/iteration.hpp>
    #include <boost/fusion/include/iteration.hpp>

[section Functions]

[section fold]

[heading Description]
For a sequence `Seq`, initial state, and binary function object or function pointer `f`, fold repeatedly applies binary `f` to each element of `Seq` and the previous state.

[heading Synopsis]
    template<
        typename Sequence,
        typename State,
        typename F
        >
    typename __result_of_fold__<Sequence, State, F>::type fold(
        Sequence& seq, State const& initial_state, F const& f);

[table Parameters
    [[Parameter][Requirement][Description]]
    [[`seq`][A model of __forward_sequence__,`f(e,s)` must be a valid expression for each element `e` in `seq`, and current state `s`][Operation's argument]]
    [[`initial_state`][Any type][Initial state]]
    [[`f`][`__boost_result_of_call__<F(E,S)>::type` is the return type of `f(e,s)` for each element `e` of type `E` in `seq`, and current state `s` of type `S`][Operation's argument]]
]

[heading Expression Semantics]
    fold(seq, initial_state, f);

[*Return type]: Any type

[*Semantics]: Equivalent to `f(eN ....f(e2,f(e1,initial_state)))` where `e1 ...eN` are the elements of `seq`.

[heading Complexity]
Linear, exactly `__result_of_size__<Sequence>::value` applications of `f`.

[heading Header]

    #include <boost/fusion/algorithm/iteration/fold.hpp>
    #include <boost/fusion/include/fold.hpp>

[heading Example]
    struct make_string
    {
        typedef std::string result_type;

        template<typename T>
        std::string operator()(const T& t, const std::string& str) const
        {
            return str + boost::lexical_cast<std::string>(t);
        }
    };
    ...
    const __vector__<int,int> vec(1,2);
    assert(__fold__(vec,std::string(""), make_string()) == "12");

[endsect]

[section accumulate]

[heading Description]
For a sequence `Seq`, initial state, and binary function object or function pointer `f`, accumulate repeatedly applies binary `f` to each element of `Seq` and the previous state.

[heading Synopsis]
    template<
        typename Sequence,
        typename State,
        typename F
        >
    typename __result_of_accumulate__<Sequence, State, F>::type accumulate(
        Sequence& seq, State const& initial_state, F const& f);

[table Parameters
    [[Parameter][Requirement][Description]]
    [[`seq`][A model of __forward_sequence__, `f(eN ....f(e2,f(e1,initial_state)))` must be a valid expression for each element `e1` to `eN` in `seq`][Operation's argument]]
    [[`initial_state`][Any type][Initial state]]
    [[`f`][`__boost_result_of_call__<F(E,S)>::type` is the return type of `f(e,s)` for each element `e` of type `E` in `seq`, and current state `s` of type `S`][Operation's argument]]
]

[heading Expression Semantics]
    accumulate(seq, initial_state, f);

[*Return type]: Any type

[*Semantics]: Equivalent to `f(eN ....f(e2,f(e1,initial_state)))` where `e1 ...eN` are the elements of `seq`.

[heading Complexity]
Linear, exactly `__result_of_size__<Sequence>::value` applications of `f`.

[heading Header]

    #include <boost/fusion/algorithm/iteration/accumulate.hpp>
    #include <boost/fusion/include/accumulate.hpp>

[heading Example]
    struct make_string
    {
        typedef std::string result_type;

        template<typename T>
        std::string operator()(const T& t, const std::string& str) const
        {
            return str + boost::lexical_cast<std::string>(t);
        }
    };
    ...
    const __vector__<int,int> vec(1,2);
    assert(__accumulate__(vec,std::string(""), make_string()) == "12");

[endsect]

[section for_each]

[heading Description]
Applies a unary function object to each element of a sequence.

[heading Synopsis]
    template<
        typename Sequence,
        typename F
        >
    typename __result_of_for_each__<Sequence, F>::type for_each(
        Sequence& seq, F const& f);

[table Parameters
    [[Parameter][Requirement][Description]]
    [[`seq`][A model of __forward_sequence__, `f(e)` must be a valid expression for each element `e` in `seq`][Operation's argument]]
    [[`f`][A unary __reg_callable_obj__][Operation's argument]]
]

[heading Expression Semantics]
    __for_each__(seq, f);

[*Return type]: `void`

[*Semantics]: Calls `f(e)` for each element `e` in `seq`.

[heading Complexity]
Linear, exactly `__result_of_size__<Sequence>::value` applications of `f`.

[heading Header]

    #include <boost/fusion/algorithm/iteration/for_each.hpp>
    #include <boost/fusion/include/for_each.hpp>

[heading Example]
    struct increment
    {
        template<typename T>
        void operator()(T& t) const
        {
            ++t;
        }
    };
    ...
    __vector__<int,int> vec(1,2);
    __for_each__(vec, increment());
    assert(vec == __make_vector__(2,3));

[endsect]

[endsect]

[section Metafunctions]

[section fold]

[heading Description]
Returns the result type of __fold__.

[heading Synopsis]
    template<
        typename Sequence,
        typename State,
        typename F>
    struct fold
    {
        typedef __unspecified__ type;
    };

[table Parameters
    [[Parameter] [Requirement] [Description]]
    [[`Sequence`] [A model of __forward_sequence__] [The sequence to iterate]]
    [[`State`]    [Any type]                        [The initial state for the first application of `F`]]
    [[`F`]    [`__boost_result_of_call__<F(E,S)>::type` is the return type of `f(e,s)` for each element `e` of type `E` in `seq`, and current state `s` of type `S`] [The operation to be applied on forward traversal]]
]

[heading Expression Semantics]
    __result_of_fold__<Sequence, State, F>::type

[*Return type]: Any type

[*Semantics]: Returns the result of applying `fold` to a sequence of type `Sequence`, with an initial state of
type `State` and binary function object or function pointer of type `F`.

[heading Complexity]
Linear, exactly `__result_of_size__<Sequence>::value` applications of `F`.

[heading Header]

    #include <boost/fusion/algorithm/iteration/fold.hpp>
    #include <boost/fusion/include/fold.hpp>

[endsect]

[section accumulate]

[heading Description]
Returns the result type of __accumulate__.

[heading Synopsis]
    template<
        typename Sequence,
        typename State,
        typename F>
    struct accumulate
    {
        typedef __unspecified__ type;
    };

[table Parameters
    [[Parameter] [Requirement] [Description]]
    [[`Sequence`] [A model of __forward_sequence__] [The sequence to iterate]]
    [[`State`]    [Any type]                                 [The initial state for the first application of `F`]]
    [[`F`]    [`__boost_result_of_call__<F(E,S)>::type` is the return type of `f(e,s)` for each element `e` of type `E` in `seq`, and current state `s` of type `S`] [The operation to be applied on forward traversal]]
]

[heading Expression Semantics]
    __result_of_accumulate__<Sequence, State, F>::type

[*Return type]: Any type

[*Semantics]: Returns the result of applying `accumulate` to a sequence of type `Sequence`, with an initial state of
type `State` and binary function object or function pointer of type `F`.

[heading Complexity]
Linear, exactly `__result_of_size__<Sequence>::value` applications of `F`.

[heading Header]

    #include <boost/fusion/algorithm/iteration/accumulate.hpp>
    #include <boost/fusion/include/accumulate.hpp>

[endsect]

[section for_each]
A metafunction returning the result type of applying __for_each__ to a sequence. The
return type of __for_each__ is always `void`.

[heading Description]

[heading Synopsis]
    template<
        typename Sequence,
        typename F
    >
    struct for_each
    {
        typedef void type;
    };

[table Parameters
    [[Parameter] [Requirement] [Description]]
    [[`Sequence`] [A model of __forward_sequence__] [Operation's argument]]
    [[`F`]    [Any type] [Operation's argument]]
]

[heading Expression Semantics]
    __result_of_for_each__<Sequence, F>::type

[*Return type]: `void`.

[*Semantics]: Returns the return type of __for_each__ for a sequence of type `Sequence` and a unary function object `F`.
The return type is always `void`.

[heading Complexity]
Constant.

[heading Header]

    #include <boost/fusion/algorithm/iteration/for_each.hpp>
    #include <boost/fusion/include/for_each.hpp>

[endsect]

[endsect]

[endsect]

[section Query]
The query algorithms provide support for searching and analyzing sequences.

[heading Header]

    #include <boost/fusion/algorithm/query.hpp>
    #include <boost/fusion/include/query.hpp>

[section Functions]

[section any]

[heading Description]
For a sequence `seq` and unary function object `f`, `any` returns true if `f` returns true for at least one element of `seq`.

[heading Synopsis]
    template<
        typename Sequence,
        typename F
        >
    typename __result_of_any__<Sequence,F>::type any(
        Sequence const& seq, F f);

[table Parameters
    [[Parameter][Requirement][Description]]
    [[`seq`][A model of __forward_sequence__, `f(e)` must be a valid expression, convertible to `bool`, for each element `e` in `seq`][The sequence to search]]
    [[`f`][A unary function object][The search predicate]]
]

[heading Expression semantics]
    __any__(seq, f);

[*Return type]: `bool`

[*Semantics]: Returns true if and only if `f(e)` evaluates to `true` for some element `e` in `seq`.

[heading Complexity]
Linear. At most `__result_of_size__<Sequence>::value` comparisons.

[heading Header]

    #include <boost/fusion/algorithm/query/any.hpp>
    #include <boost/fusion/include/any.hpp>

[heading Example]
    struct odd
    {
        template<typename T>
        bool operator()(T t) const
        {
            return t % 2;
        }
    };
    ...
    assert(__any__(__make_vector__(1,2), odd()));
    assert(!__any__(__make_vector__(2,4), odd()));

[endsect]

[section all]

[heading Description]
For a sequence `seq` and unary function object `f`, `all` returns true if `f` returns true for every element of `seq`.

[heading Synopsis]
    template<
        typename Sequence,
        typename F
        >
    typename __result_of_all__<Sequence,F>::type all(
        Sequence const& seq, F f);

[table Parameters
    [[Parameter][Requirement][Description]]
    [[`seq`][A model of __forward_sequence__, `f(e)` is a valid expression, convertible to `bool`, for every element `e` in `seq`][The sequence to search]]
    [[`f`][A unary function object][The search predicate]]
]

[heading Expression Semantics]
    __all__(seq, f);

[*Return type]: `bool`

[*Semantics]: Returns true if and only if `f(e)` evaluates to `true` for every element `e` in `seq`.

[heading Complexity]
Linear. At most `__result_of_size__<Sequence>::value` comparisons.

[heading Header]

    #include <boost/fusion/algorithm/query/all.hpp>
    #include <boost/fusion/include/all.hpp>

[heading Example]
    struct odd
    {
        template<typename T>
        bool operator()(T t) const
        {
            return t % 2;
        }
    };
    ...
    assert(__all__(__make_vector__(1,3), odd()));
    assert(!__all__(__make_vector__(1,2), odd()));

[endsect]

[section none]

[heading Description]
For a sequence `seq` and unary function object `f`, `none` returns true if `f` returns false for every element of `seq`.

[heading Synopsis]
    template<
        typename Sequence,
        typename F
        >
    typename __result_of_none__<Sequence,F>::type none(
        Sequence const& seq, F f);

[table Parameters
    [[Parameter][Requirement][Description]]
    [[`seq`][A model of __forward_sequence__, `f(e)` is a valid expression, convertible to `bool`, for every element `e` in `seq`][The sequence to search]]