Итераторы «Просмотр» и итераторы-адаптеры

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

Просмотр последовательности:

Просмотр – оболочка для одной или нескольких базовых последовательностей, с одним или несколькими итераторами-адаптерами, для их обработки. Использование в алгоритмах последовательность не напрямую, а через механизм просмотра позволяет осуществлять «ленивое» поведение.

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

«Ленивый» подход последовательностей просмотра может также эффективно применяться в коде времени выполнения.

Концепция просмотра

Текущий вид концепций в С++ сводится к формальным требованиями организации интерфейса.

С интерфейсной точки зрения «просмотр» - не что иное как обычная последовательность, и отличатеся от остальных последовательностей по двум причинам:

• Ленивый подход: элементы вычисляются только по требованию. Но не все ленивые последовательности являются также и просмотром. Например, range_c <...> явялется ленивой последовательности, но не просмотром.

• Возможность быть просмотренным по требованию, т.к. элементы должны быть сгенерированы от одной или более входных последовательностей.

Свойства, связанные с фундаментальными характеристиками (для всех просмотров):

• Применяется ко всем ленивым последовательностям: элементы не могут быть расширяемыми. Если необходима расширяемость, то нужно использовать алгоритм mpl::copy, чтобы явно создать расширяемую последовательность из просмотра.

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

Применение просмотра Сравнения значений элементов последовательности:

Напишем метафункцию padded_size, которая принимает целочисленное значение MinSize и последовательность типов Seq, упорядоченых по возрастанию их размера, возвращает размер первого элемента Seq - e, для которого выполняется условие: sizeof (е) >= MinSize.

Тот факт, что мы ищем в отсортированной последовательности является ключом к использованию одного из алгоритмов бинарного поиска: upper_bound или lower_bound, но, т.к. поиск ведется первого элемента, то применим lower_bound:

template<class Seq, class MinSize>

struct padded_size

: mpl::sizeof_< // the size of

typename mpl::deref< // the element at

typename mpl::lower_bound< // the first position

Seq,

MinSize,

//comparison predicate…

>::type

>::type

>

{};

Условие, которое должно выполняться: sizeof (е) >= MinSize, но предикат сравнения (компоратор) lower_bound не совсем применим к данной ситуации:

Документация: возвращается первая позиция отсортированной последовательности [то есть Seq], где Т [то есть, MinSize] может быть вставлен без нарушения упорядочения.

После выполнения метафункции, Seq упорядочен по размеру элементов, а MinSize будет вставлен в новую последовательность, что не планировалось.

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

typedef lower_bound< Sequence, T, Pred >::type i;

Возвращает: модель прямого итератора.

Семантика: i - самый дальний итератор в последовательности, в которой для каждого итератора j в диапазое [begin<Sequence>::type, i), следующая запись является правдой:

apply<Pred, deref<j>::type, T >::type::value

Это означает, что результатом работы lower_bound будет последняя позиция в последовательности, для которой предикат, возвращает правду, при сравнеии элементов до текущйей позиции с Т. Это кажется то, что нам необходимо, чтобвы выполнялось условие sizeof (е) < MinSize::value до той позиции, которую мы ищем.

Таким образом, предикат будет иметь вид:

mpl::less<mpl::sizeof_<_1>, _2>

Так, для первого аргумента (mpl::sizeof_<_1>) будет расчитываться размер, а второй (MinSize::value) уже является размером, потому используем только заполнитель «_2».

Добавим данный предикат в метафункцию:

template<class Seq, class MinSize>

struct padded_size

: mpl::sizeof_<

typename mpl::deref<

typename mpl::lower_bound<

Seq,

MinSize,

mpl::less<mpl::sizeof_<_1>, _2> // приведение к однородному сравнению

>::type

>::type

>

{};

Результатом работы lower_bound с данным предикатом будет возврат последней позиции, котороая соответсвуте условию sizeof (е) < MinSize::value, что эквиваленто нашему настоящему условию – вернуть первый элемент, для которого справделиво обратное условие: sizeof (е) >= MinSize::value.

Проблема: повторный расчет размера элементов последовательности внутри lower_bound и при возвращении позиции.