Ассоциативные

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

Таблица:

В таблицах, k и k2 могут быть любым типом, pos1 и pos2 - итераторы в S:

Требования

Expression	Result	Precondition/Assertion
mpl::has_key< S, k >::value	true if k is in S's set of keys; false otherwise.
mpl::at< S, k >::type	The value type associated with k.	Precondition: k is in S's set of keys
mpl::order< S, k >::type	An unsigned integral constant wrapper.	If mpl::order<S,k>::type::value == mpl::order<S,k2>::type::value then k is identical to k2. Precondition: k is in S's set of keys.
mpl::key_type< S, t >::type	The key type that S would use for an element type t.	If mpl::key_type< S, mpl::deref<pos1>::type >::type is identical to mpl::key_type< S, mpl::deref<pos2>::type >::type then pos1 is identical to pos2.
mpl::value_type< S, t >::type	The value type that S would use for an element type t.

Расширения

Expression	Result	Note
mpl::insert< S, pos1, t >::type mpl::insert< S, t >::type	S' equivalent to S except that mpl::at< S' , mpl::key_type<S,t>::type >::type is mpl::value_type<S,t>::type.	May incur an erasure penalty if mpl::has_key< S, mpl::key_type< S, t >::type >::value is true.
mpl::erase< S, pos1 >::type	S' equivalent to S except that mpl::has_key< S' , mpl::key_type< S , mpl::deref<pos1>::type >::type >::value is false.
mpl::erase_key< S, k >::type	S' equivalent to S except that mpl::has_key<S' , k>::value is false.
mpl::clear< S >::type	An empty sequence with the same properties as S.

Нет никаких гарантий, относительно возвращаемых значений, кроме той, что для каждого значения существет уникальный ключ в последовательности. В частности, значения не обязаны следовать какому-либо порядку для их обхода итератором. В отличие от ассоциативного контейнера STL, значеняи в котором строго упорядочены( по умолчанию компаратором выступает std::less<KeyType>), у ассоциативных метапоследовательностей нет четко установленного порядка, для обхода их итераторами, порядок зависит от конкретной реализации.

Расширенные ассоциативные последовательности

Расширяемая ассоциативная последовательность поддерживает операции вставки, удаления и очистки. Результатом работы каждая операции является новая последовательность. Так как порядок расположения элементов в ассоциативной последовательности произволен, позиция вставляемого элемента не обязана соответствовать указанной итератором, при обращении к метафункции вставк, это очень существенное отличие от одноименных ассоциативных последовательностей STL. Например, в то время как последовательность STL может использовать итератор в качестве «подсказки» как улучшить сложность операции вставки с O (log(N)) до O(1), ассоциативная метапоследовательность вообще игнорирует итератор- аргумент. Фактически, вставка всегда O(1). Такое постоянство – удобно для авторов алгоритмов, но постоянная передача итератора нет. Поэтому, в дополнение к mpl::insert<S, pos, t>, Расширяемая ассоциативная последовательность должна также поддержать эквивалентную форму mpl::insert<S, t>.

Другое различие от ассоциативных контейнеров времени выполнения - то, что очистка фактически оказывает влияние на эффективность итерации: для полного обхода ассоциативной метапоследовательности необходима худшая сложность O(N+E), где N - количество элементов последовательности, и E - количество элементов, которые должны быть стерты. Когда элемент стерт из ассоциативной последовательности, библиотека добавляет специальный элемент- маркер, который заставляет стертый элемент быть пропущенным во время повторения. Метафункции clear для ассоциативной последовательности не имеет подобного недостатка, т.к. результат - совершенно новая последовательность.

Следующие выражения имеют постоянную сложность и возвращают новую последовательность.

Поскольку стирание из любой позиции в расширенной ассоциативной последовательности - O(1), операции pop_front, и pop_back доступны. Операция вставки также - O(1), а mpl::push_front <S, t> и mpl::push_back <S, t> поддерживаются, но оба эквивалентны сложности mpl:: insert <S, t>, потому как итератор- аргумент в mpl::insert<S, pos, t> игнорируется.