Последовательности

В MPL концепции последовательностей систематизированы подобно STL. Каждый уровень концепций уточняет ввод новых возможностей и интерфейсов.

Обход

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

Последовательность подобно паре итераторов, ссылающихся на элементы. Большинство задач для работы с последовательностью способен выполнять итератор.

Прямые

Любая последовательность MPL (например, mpl::list) явялется прямой.

В Таблице S представляет прямую последовательность.

Expression	Result	Assertion
mpl::begin<S>::type	A Forward Iterator.
mpl::end<S>::type	A Forward Iterator.	Reachable from mpl::begin<S>::type.

Каждая непустая последовательность MPL также поддерживает выражение:

mpl::front<S>::type

что эквивалентно следующей записи:

mpl::deref<mpl::begin<S>::type>::type

Двунаправленные

Expression	Result
mpl::begin<S>::type	A Bidirectional Iterator.
mpl::end<S>::type	A Bidirectional Iterator.

Каждая непустая двунаправленная последовательность поддерживает выражение:

mpl::back<S>::type // возврат пред-последнего итератора «[)»

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

mpl::deref<

mpl::prior< // смещение на 1 позицию назад

mpl::end<S>::type

>::type

>::type

Произвольные

Пример произвольной последовательности – mpl::vector.

Expression	Result
mpl::begin<S>::type	A Random Access Iterator.
mpl::end<S>::type	A Random Access Iterator.

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

mpl::at<S,N>::type

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

mpl::deref<

mpl::advance<

mpl::begin<S>::type

, N

>::type

>::type

Расширенные

Расширяемая последовательность - та, которая поддерживает операции вставки, удаления и очистки (push_front и pop_front, push_back и pop_back). Так как метаданные являются константными, ни одна из этих операций не может изменить оригинальную последовательность. Вместо этого они все возвращают измененную копию оригинальной последовательности.

Таблица:

S - расширяемая последовательность, pos – позиция некоторого итератора в S, finish - итератор относительно pos, X любой тип, выражения в таблице возвращают новую последовательность, которая является моделью последовательности с эквивалентной концепцией S:

Expression	Elements of Result
mpl::insert<S,pos,X>::type	[mpl::begin<S>::type, pos), X, [pos, mpl::end<S>::type)
mpl::erase<S,pos>::type	[mpl::begin<S>::type, pos), [mpl::next<pos>::type, mpl::end<S>::type)
mpl::erase< S, pos, finish >::type	[mpl::begin<S>::type, pos), [finish, mpl::end<S>::type)
mpl::clear<S>::type	None.

Многие из последовательностей MPL расширяемы, но с различной сложностью для различных операций. Например, вставка и удаление в вершину «голову» списка mpl::list - O(1) (постоянное время и ресурсы компилятора), в конец «хвост», O(N) – сложность пропорциональна длине списка. Вставка и удаление в конец вектора, при этом, постоянна mpl::vector - O (1), но модификации для других позиций, могут гарантировать лишь O(N).

MPL также предоставляет метафункции push_front и pop_front, которые вставляют и стирают единственный элемент с вершины «голову» последовательности, а push_back и pop_back делают то же самое в «хвосте» последовательности. Каждая из этих операций доступна только для последовательностей, которые поддержиавать постоянную сложность O(1).