Операции Внутренние операции с последовательностей

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

R - любая последовательность.

Expression	Result	Worst-Case Complexity
mpl::empty<S>::type	A bool constant wrapper; true iff the sequence is empty.	Constant.
mpl::insert_range< S, pos, R >::type	Identical to S but with the elements of R inserted at pos.	Linear in the length of the result.
mpl::size<S>::type	An integral constant wrapper whose ::value is the number of elements in S.	Linear in the length of S.

Есть 3 причины почему эти метафункции не явялются внутренними для каждой последовательности:

1. Синтаксические издержки. Шаблоны-элементы класса трудно использовать в большом метапрограммном контексте из-за необходимости использовать дополнительное ключевое слово template:

Sequence::template erase<pos>::type

Другая форма более удобная:

mpl::erase<Sequence,pos>::type

2. Эффективность. Большинство последовательностей - шаблоны, которые могут быть специализированы многими способами. Наличие в первичной версии метафункции-класса вынуждала бы переопределять этот элемент для каждой новой специализации.

3. Удобство. Эти операции можно реализовать уже встроенными альтернативными способами. Например, размер по умолчанию есть расстояние между итераторами начала и конца последовательности.

Классы

У всех последовательностей MPL есть и пронумерованная/ непронумерованная форма.

Непронумерованная формы - форма контейнера, в имени которого не указывается размер: mpl::vector<int, long, int>.

Пронумерованная форма - форма контейнера, в имени которого указывается размер: mpl::vector3<int, long, int>. Длина непронумерованных форм ограничена 20 элементами по умолчанию (можно расширить), чтобы уменьшить сцепление в библиотеке и ограничить времена компиляции. Чтобы использовать пронумерованную форму последовательности с длиной N, необходимо включать соответствующий «пронумерованный заголовок», названный по имени последовательности, длина которой - N, окруженный к самому близкому кратному числу десять.

Например:

#include <boost/mpl/vector/vector30.hpp> // 28 rounded up

// declare a sequence of 28 elements

typedef boost::mpl::vector28<

char, int, long ... 25 more types

> s;

list

Список mpl::list является самым простым из расширяемых последовательностей MPL, структурно подобен списку времени выполнения.

Сложность вствки/удаления в начало имеет постоянное премя O(1), а для середины и конца – линейное.

Операции в документации.

vector

Вектор MPL - последовательность произвольного доступа. Для обхода которой есть итератор произвольного доступа. В любой позиции итератор может вести себя как двунапралвенный.

Подобно вектору STL поддерживает эффективные операции push_back и pop_back.

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

#include <boost/mpl/vector/vector10.hpp>

typedef boost::mpl::vector9<

int[1], int[2], int[3], int[4]

, int[5], int[6], int[7], int[8], int[9]

> s9;

typedef mpl::push_back<s9, int[10]>::type s10; // OK

typedef mpl::push_back<s10, int[11]>::type s11; // error

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

Так как метакод выполняет во время компиляции, то превышение уставноленного предела вызывет ошибку времени компиляции.

Для компиляторов, которые поддерживают языковое расширение typeof, нет ограничения в количестве.

Операции с mpl::vector выполняются намного быстрее, т.к. в отличии от mpl::list, доступ к его элементам – произвольный. Это делает mpl::vector лучшим кандидатом в контейнеры по умолчанию. Однако, если требуется последовательность произвольной длины то имее смысл использовать mpl::list.

deque

mpl::deque почти точно походит на mpl::vector во всех отношениях, за исключением того, что deque позволяет выполнять более эффективно операции вставки в начало последовательности с push_front и pop_front. В отличие от соответствующих компонентов STL, эффективность mpl::deque очень близка к mpl::vector т.к. mpl::deque фактически явялется mpl::vector.

range_c

mpl::range_c – «ленивая» последовательность произвольного доступа, которая содержит последовательные целочсиленные константы. Таким образом, mpl::range_c <long, N, M> примерно эквивалентен следующей записи:

mpl::vector

<

mpl::integral_c<long,N>

, mpl::integral_c<long,N+1>

, mpl::integral_c<long,N+2>

//...

, mpl::integral_c<long,M-3>

, mpl::integral_c<long,M-2>

, mpl::integral_c<long,M-1> // Note: M-1, not M "[)"

>

Называя range_c «ленивой» последовательностью, подразумеваем, что его элементы явно не представлены: Это просто хранит конечные точки и производит новые целочисленные в пределах заданного диапазона это экономит время компиляции в больше степени, что при использовании mpl::vector.

Цена этой экономики то, что range_c ограничен, в отличии от вектора и списка. Если бы библиотека могла бы поддержать вставку произвольных элементов в range_c, элементы должны были бы быть явно представлены. Хотя mpl::range_c нерасширяем, но зато поддерживает pop_front и pop_back, т.к. ограничить диапазон можно всегда.

map

mpl::map - расширяемая ассоциативная последовательность, в которой каждый элемент поддерживает интерфейс mpl::pair.

template <class T1, class T2>

struct pair

{

typedef pair type;

typedef T1 first;

typedef T2 second;

};

Элементы first и second поддерживают конструкцию ключ-значение.

template<class TList, int D> struct AtT

: mpl::at<TList, int_<D>>

{};

int main()

{

typedef mpl::map<

mpl::pair<bool, unsigned char>,

mpl::pair<unsigned char, unsigned short>,

mpl::pair<unsigned short, unsigned int>,

mpl::pair<unsigned int, unsigned long>,

mpl::pair<signed char, signed short>,

mpl::pair<signed short, signed int>,

mpl::pair<signed int, signed long>

>::type to_larger;

// Ассоциации дескриптор-тип:

typedef mpl::map

<

mpl::pair<mpl::int_<777>, char>,

mpl::pair< mpl::int_<892>, int>

>::type TD;

PrintT<mpl::at<TD, int_<892>>::type>();

PrintT<AtT<TD,777>::type>();

return 0;

}

Количество элементов для mpl::map также является ограниченным. Когда в mpl::map есть ограниченный максимальный размер, обход всех элементов занимает O(N) вместо O (N+E), где N - размер отображения, и E – количество удаляемых элементов.

set

Множество походит на отображение, за исключением того, что каждый элемент идентичен типу своего ключа и типу значения. Тот факт, что типы ключа и значения идентичны, означает что mpl::set<S, k>::type - довольно неинтересная операция, т.к. просто возвращает k. Главное преимущество использования mpl::set - эффективное тестирование элементов с mpl::has_key <S, k>::type. Множество не имеет максимального размера и поэтому операция полного обхода всегда занимает всегда O (N+E).

iterator_range

iterator_range подобен range_c, но вместо того, чтобы хранить свои элементы явно, iterator_range хранит два итератора, которые обозначают конечные точки последовательности. Поскольку алгоритмы MPL манипулируют последовательностями вместо итераторов, iterator_range может быть обязательным, когда необходимо манипулировать в алгоритме только частью последовательности: Как только найдены конечные точки последовательности, можно можете сформировать iterator_range и выполнить проход по алгоритму, вместо того, чтобы создавать новую измененную версию оригинальной последовательности.