Алгоритмы

MPL предоставляет широкий спектр фундаментальных алгоритмов, которые обеспечивают обработку данных для большинства последовательностей времени компиляции.

У алгоритмов MPL есть свои аналоги в STL, а также итеративные алгоритмы аналогичные одноименным из функциональных языков программирования. В отличие от алгоритмов STL, которые работают с неявными диапазонами итераторов, большинство алгоритмов MPL принимают и возвращают последовательности. Такой подход не столько связан с функциональной природой вычислений C++ времени компиляции, сколько желанием улучшить общее удобство работы с библиотекой, что делает программирование структур данных времени компиляции более удобным и эффективным.

Подобно STL, алгоритмы MPL являются обобщенными - не привязаны к конкретному классу последовательности и могут работать с широким спектром аргументов, которые удовлетворяют документированным требованиям. Требования формулируются в терминах концепций. Во внутренней реализации, алгоритмы не связаны с конкретными реализациями последовательностей, т.к. оперируют итераторами.

Все MPL алгоритмы могут быть разделены на три основные категории:

• Итерационные алгоритмы;

• Алгоритмы запросов;

• Алгоритмы преобразования;

Алгоритмы преобразования представляют концепцию Inserter (механизм вставки) как грубый эквивалент концепции выходного итератора в стандартной библиотеке. Каждый алгоритм преобразования имеет свой reverse_ аналог, что позволяет выполнять более широкий спектр эффективных преобразований.

Концепции

Inserter

(Инсертер: механизм вставок)

Описание:

Инсертер заменяет во время компиляции итератор вывода STL. Во внутренней реализации, это просто тип, содержащий в себе две сущности:

• Состояние;

• Операция;

Когда алгоритму преобразования передается инсертер, то его бинарная операция вызывается для каждого элемента, которые обычно записываются в выходной итератор.

Технически, вместо того, чтобы принимать один параметр инсертера, алгоритм преобразования мог бы принимать раздельно состояния и операцию «вывода». Но такая группировка их в единый параметр делает алгоритмы семантически и синтаксически ближе к своим аналогами из STL, что значительно упрощает многие общие варианты использования.

Действительные выражения:

В следующей таблице и спецификациях, in - модель инсертера.

Выражение	Тип
in::state	Любой тип
in::operation	Бинарное лямбда-выражение

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

Выражение	Семантика
in::state	Исходное состояние в инсертере.
in::operation	Операция «вывода» в инсертере.

Пример:

int main()

{

typedef mpl::transform<

mpl::range_c<int,0,10>,

mpl::plus<mpl::_1,mpl::_1>,

mpl::back_inserter< mpl::vector0<> >

>::type result;

return 0;

};

Модели:

• inserter

• front_inserter

• back_inserter

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

Algorithms, Transformation Algorithms, inserter, front_inserter, back_inserter

Reversible Algorithm

Описание:

Реверсивные алгоритмы является элементом парных алгоритмов преобразования (прямые, обратные/реверсные), позволяющие обходить входную последовательность в обратном направлении.

Требования к выражениям:

В следующей таблице и спецификациях, х - заполнительный маркер (placeholder) для текущего имени реверсного алгоритма, s₁, s₂, ... s_n. являются прямыми последовательностями, in - инсертер.

Выражение	Тип	Сложность
x<s1,s2, ... sn, ...>::type	Прямая последовательность	Не определено.
x<s1,s2, ... sn, ... in>::type	Любой тип	Не определено.
reverse_x<s1,s2, ... sn, ... >::type	Прямая последовательность	Не определено.
reverse_x<s1,s2, ... sn, ... in>::type	Любой тип	Не определено.

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

1:

typedef x<s₁,s₂, ... s_n, ...>::type t;

Предусловие: s₁ – расширяемая последовательность.

Семантика: если

has_push_back<s₁>::value == true

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

x<

s₁,s₂, ... s_n, ...,

back_inserter<clear<s₁>::type>

>::type

В противном случае:

reverse_x<

s₁,s₂, ... s_n, ...,

front_inserter<clear<s₁>::type>

>::type

2:

typedef x<s₁,s₂, ... s_n, ... in>::type t;

Семантика: t – результат вызова х с аргументами s₁,s₂, ... s_n, ... in.

3:

typedef reverse_x<s₁,s₂, ... s_n, ... >::type t;

Предусловие: s₁ – расширяемая последовательность.

Семантика: если

has_push_back<s₁>::value == true

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

x<

s₁,s₂, ... s_n, ...,

front_inserter<clear<s₁>::type>

>::type

В противном случае:

reverse_x<

s₁,s₂, ... s_n, ...,

back_inserter<clear<s₁>::type>

>::type

4:

typedef reverse_x<s₁,s₂, ... s_n, ... in>::type t;

Семантика: t – результат вызова reverse_х с аргументами s₁,s₂, ... s_n, ... in.

Пример:

int main()

{

//=================================

typedef mpl::transform<

mpl::range_c<int,0,10>,

mpl::plus<

mpl::_1,

mpl::int_<7>

>,

mpl::back_inserter<vector0<>>

>::type r1;

//=================================

typedef mpl::transform<

r1,

mpl::minus<

mpl::_1,

mpl::int_<2>

>

>::type r2;

//=================================

typedef mpl::reverse_transform<

r2,

mpl::minus<

mpl::_1,

mpl::int_<5>

>,

mpl::front_inserter<vector0<>>

>::type r3;

//=================================

BOOST_MPL_ASSERT(( mpl::equal<r1, mpl::range_c<int,7,17>> ));

BOOST_MPL_ASSERT(( mpl::equal<r2, mpl::range_c<int,5,15>> ));

BOOST_MPL_ASSERT(( mpl::equal<r3, mpl::range_c<int,0,10>> ));

return 0;

};

Модели:

• transform

• remove

• replace

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

Transformation Algorithms, Inserter