Итеративные алгоритмы

Итеративные алгоритмы - фундаментальные строительные блоки для многих алгоритмов MPL. Являются основой для написания пользовательских алгоритмов.

fold

Фомрат:

template

<

typename Sequence,

typename State,

typename ForwardOp

>

struct fold

{

typedef unspecified type;

};

Описание:

Возвращает результат последовательного применения бинарной операции ForwardOp к результату предыдущих вызовов ForwardOp (для первого вызова используется State) для каждого элемента последовательности в диапазоне

[begin<Sequence>::type, end<Sequence>::type).

Заголовок:

#include <boost/mpl/fold.hpp>

Параметры:

Выражение	Требование	Описание
Sequence	Прямая последовательность	Последовательность для итераций.
State	Любой тип	Исходное состояние для первого применения ForwardOp.
ForwardOp	Бинарное лямбда-выражение	Операция, которая будет выполнена при прямом обходе последовательности.

Семантика выражений:

Для любой прямой последовательности s, бинарного лямбда-выражения op и произвольного типа state:

typedef fold<s,state,op>::type t;

Возвращаемый тип: тип.

Семантика: эквивалентно

typedef iter_fold<

s,

state,

apply<

op,

_1,

deref<_2>

>

>::type t;

Сложность:

Линейная. Время работы прямо пропорционально значению размера

size<s>::value

Пример:

int main()

{

typedef mpl::vector<long,float,short,double,float,long,long double> types;

typedef mpl::fold<

types, // последовательность

mpl::int_<0>, // исходное состояние

mpl::if_< // условная операция

boost::is_float<mpl::_2>,

mpl::next<mpl::_1>,

mpl::_1

>

>::type number_of_floats;

BOOST_MPL_ASSERT_RELATION( number_of_floats::value, ==, 4 );

return 0;

}

Смотри также:

Algorithms, accumulate, reverse_fold, iter_fold, reverse_iter_fold, copy, copy_if

iter_fold

Фомрат:

template

<

typename Sequence,

typename State,

typename ForwardOp

>

struct iter_fold

{

typedef unspecified type;

};

Описание:

Возвращает результат последовательного применения бинарной операции ForwardOp к результату предыдущих вызовов ForwardOp (для первого вызова используется State) для каждого итератора последовательности в диапазоне

[begin<Sequence>::type, end<Sequence>::type).

Заголовок:

#include <boost/mpl/iter_fold.hpp>

Параметры:

Выражение	Требование	Описание
Sequence	Прямая последовательность	Последовательность для итераций.
State	Любой тип	Исходное состояние для первого применения ForwardOp.
ForwardOp	Бинарное лямбда-выражение	Операция, которая будет выполнена при прямом обходе последовательности.

Семантика выражений:

Для любой прямой последовательности s, бинарного лямбда-выражения op и произвольного типа state:

typedef iter_fold<s,state,op>::type t;

Возвращаемый тип: тип.

Семантика: эквивалентно

typedef begin<Sequence>::type i₁;

typedef apply<op,state,i₁>::type state₁;

typedef next<i₁>::type i₂;

typedef apply<op,state₁,i₂>::type state₂;

...

typedef apply<op,state_n−1,i_n>::type state_n;

typedef next<i_n>::type - last;

typedef state_n t;

где

n == size<s>::value

last == end<s>::type;

если

empty<s>::value == true,

то эквивалентно

typedef state t;

Сложность:

Линейная. Время работы прямо пропорционально значению размера

size<s>::value

Пример:

int main()

{

typedef mpl::vector_c<int,5,-1,0,7,2,0,-5,4> numbers;

typedef mpl::iter_fold<

numbers,

mpl::begin<numbers>::type,

mpl::if_<

mpl::less<

mpl::deref<_1>,

mpl::deref<_2>

>,

mpl::_2,

mpl::_1

>

>::type max_element_iter;

BOOST_MPL_ASSERT_RELATION

(mpl::deref<max_element_iter>::type::value, ==, 7);

return 0;

}

Смотри также:

Algorithms, reverse_iter_fold, fold, reverse_fold, copy

reverse_fold

Фомрат:

template

<

typename Sequence,

typename State,

typename BackwardOp,

typename ForwardOp = mpl::_1

>

struct reverse_fold

{

typedef unspecified type;

};

Описание:

Возвращает результат последовательного применения в обратном порядке бинарной операции BackwardOp к результату предыдущих вызовов BackwardOp (для первого вызова используется State) для каждого элемента последовательности в диапазоне

[begin<Sequence>::type, end<Sequence>::type).

Если ForwardOp обеспечивается, то она применяется на этапе раскрутки рекурсии, сформированный результат передается первому вызову BackwardOp.

Заголовок:

#include <boost/mpl/reverse_fold.hpp>

Параметры:

Выражение	Требование	Описание
Sequence	Прямая последовательность	Последовательность для итераций.
State	Любой тип	Исходное состояние для первого применения BackwardOp/ForwardOp.
BackwardOp	Бинарное лямбда-выражение	Операция, которая будет выполнена при обратном обходе последовательности.
ForwardOp	Бинарное лямбда-выражение	Операция, которая будет выполнена при прямом обходе последовательности.

Семантика выражений:

Для любой прямой последовательности s, бинарного лямбда-выражения backward_op и forward_op и произвольного типа state:

typedef reverse_fold<s, state, backward_op >::type t;

Возвращаемый тип: тип.

Семантика: эквивалентно

typedef reverse_iter_fold<

s,

state,

apply<backward_op, _1, deref<_2>>

>::type t;

typedef reverse_fold<s, state, backward_op, forward_op>::type t;

Сложность:

Линейная. Время работы прямо пропорционально значению размера

size<s>::value

Пример:

int main()

{

typedef mpl::list_c<int,5,-1,0,-7,-2,0,-5,4> numbers;

typedef mpl::list_c<int,-1,-7,-2,-5> negatives;

typedef mpl::reverse_fold<

numbers,

mpl::list_c<int>,

mpl::if_<

mpl::less<

mpl::_2, // т.к. _1 - проверен

mpl::int_<0>

>,

push_front<mpl::_1, mpl::_2>,

mpl::_1

>

>::type result;

BOOST_MPL_ASSERT(( mpl::equal< negatives, result > ));

return 0;

}

Достигнуть того же эффекта можно более лакончино, с помощью метафункции remove_if.

Смотри также:

Algorithms, fold, reverse_iter_fold, iter_fold

reverse_iter_fold

Фомрат:

template

<

typename Sequence,

typename State,

typename BackwardOp,

typename ForwardOp = mpl::_1

>

struct reverse_iter_fold

{

typedef unspecified type;

};

Описание:

Возвращает результат последовательного применения в обратном порядке бинарной операции BackwardOp к результату предыдущих вызовов BackwardOp (для первого вызова используется State) для каждого итератора последовательности в диапазоне

[begin<Sequence>::type, end<Sequence>::type).

Если ForwardOp обеспечивается, то она применяется на этапе раскрутки рекурсии, сформированный результат передается первому вызову BackwardOp.

Заголовок:

#include <boost/mpl/reverse_iter_fold.hpp>

Параметры:

Выражение	Требование	Описание
Sequence	Прямая последовательность	Последовательность для итераций.
State	Любой тип	Исходное состояние для первого применения BackwardOp/ForwardOp.
BackwardOp	Бинарное лямбда-выражение	Операция, которая будет выполнена при обратном обходе последовательности.
ForwardOp	Бинарное лямбда-выражение	Операция, которая будет выполнена при прямом обходе последовательности.

Семантика выражений:

Для любой прямой последовательности s, бинарного лямбда-выражения backward_op и forward_op и произвольного типа state:

1:

typedef reverse_iter_fold<s, state, backward_op>::type t;

Возвращаемый тип: тип.

Семантика: эквивалентно

typedef begin<s>::type i₁;

typedef next<i₁>::type i₂;

...

typedef next<i_n>::type last;

typedef apply<backward_op,state,i_n>::type state_n;

typedef apply<backward_op,state_n,i_n−1>::type state_n−1;

...

typedef apply<backward_op,state₂,i₁>::type state₁;

typedef state₁ t;

где

n == size<s>::value

last == end<s>::type;

если

empty<s>::value == true,

то эквивалентно

typedef state t;

2:

typedef reverse_iter_fold< s,state,backward_op,forward_op >::type t;

Возвращаемый тип: тип.

Семантика: эквивалентно

typedef reverse_iter_fold<

Sequence,

iter_fold<s,state,forward_op>::type,

backward_op

>::type t;

Сложность:

Линейная. Время работы прямо пропорционально значению размера

size<s>::value

Пример:

int main()

{

typedef mpl::vector_c<int,5,-1,0,-7,-2,0,-5,4> numbers;

typedef mpl::list_c<int,-1,-7,-2,-5> negatives;

typedef mpl::reverse_iter_fold<

numbers,

mpl::list<>,

mpl::if_<

mpl::less<

mpl::deref<mpl::_2>,

mpl::int_<0>

>,

mpl::push_front<mpl::_1, mpl::_2>,

mpl::_1

>

>::type iters;

BOOST_MPL_ASSERT

((

mpl::equal<

negatives,

mpl::transform_view<

iters,

mpl::deref<mpl::_1>

>

>

));

return 0;

}

Смотри также:

Algorithms, iter_fold, reverse_fold, fold

accumulate

Фомрат:

template

<

typename Sequence,

typename State,

typename ForwardOp

>

struct accumulate

{

typedef unspecified type;

};

Описание:

Возвращает результат последовательного применения бинарной операции ForwardOp к результату предыдущих вызовов ForwardOp (для первого вызова используется State) для каждого элемента последовательности в диапазоне

[begin<Sequence>::type, end<Sequence>::type).

[accumulate - синоним fold]

Заголовок:

#include <boost/mpl/accumulate.hpp>

Параметры:

Выражение	Требование	Описание
Sequence	Прямая последовательность	Последовательность для итераций.
State	Любой тип	Исходное состояние для первого применения ForwardOp.
ForwardOp	Бинарное лямбда-выражение	Операция, которая будет выполнена при прямом обходе последовательности.

Семантика выражений:

Для любой прямой последовательности s, бинарного лямбда-выражения op и произвольного типа state:

typedef accumulate<s,state,op>::type t;

Возвращаемый тип: тип.

Семантика: эквивалентно

typedef fold<s,state,op>::type t;

Сложность:

Линейная. Время работы прямо пропорционально значению размера

size<s>::value

Пример:

int main()

{

typedef mpl::vector<long,float,short,double,float,long,long double> types;

typedef mpl::accumulate<

types,

mpl::int_<0>,

mpl::if_<

boost::is_float<mpl::_2>,

mpl::next<mpl::_1>,

mpl::_1

>

>::type number_of_floats;

BOOST_MPL_ASSERT_RELATION( number_of_floats::value, ==, 4 );

return 0;

}

Смотри также:

Algorithms, fold, reverse_fold, iter_fold, reverse_iter_fold, copy, copy_if