9.7. Адаптеры

Адаптеры в STL служат для расширения возможностей существующих шаблонов. Такое расширение достигается введением новых компонент либо сокрытием существующих компонент. В STL выделяются три категории адаптеров: 1) адаптеры контейнеров; 2) адаптеры итераторов; 3) адаптеры функций.

Адаптеры контейнеров позволяют строить на основе существующих контейнеров контейнеры с новой функциональностью. К их числу относятся стеки, очереди и приоритетные очереди (все они будут доступны при условии включения заголовочного файла stack.h). Стек может быть получен из вектора, списка или двухсторонней очереди. Стек доопределяет пять новых компонентных функций: empty (проверка пустоты), size (текущий размер стека), top (значение объекта из вершины стека), push (запись элемента в вершину), pop (удаление объекта из вершины). Дополнительно вводятся операции для сравнения стеков operator== и operator<.

Пример

...

stack < vector<int> > s1; // стек на базе вектора

stack < list<int> > s2; // стек на базе списка

stack < deque<int> > s3; // стек на базе очереди

S1.Push(1); s1.Push(5);

cout << s1.top() << endl;

s1.pop();

cout << s1.size() << endl;

s1.empty()? cout << "стек пуст" : cout << "стек еще не пуст";

...

Очередь можно получить либо из списка, либо из двухсторонней очереди:

queue < list<int> > q1;

queue < deque<int> > q2;

Очередь доопределяет почти те же новые функции и операции, что и стек, только вместо функции top вводятся функции back (последний объект очереди) и front (первый объект очереди).

Приоритетную очередь получают от вектора или двухсторонней очереди. В приоритетной очереди, в отличие от обычной, объекты сортируются с помощью функтора comp, передаваемого через параметр. Приоритетная очередь инкапсулирует функции empty и size, push (запись объекта в очередь согласно его приоритету), pop (удаление объекта с максимальным приоритетом), top (получение наиболее приоритетного объекта).

Пример

...

// используем less как функтор сравнения

priority_queue < vector<int>, less<int> > pq1;

// используем greater как функтор сравнения

priority_queue < deque<int>, greater<int> > pq2;

vector v(3,1);

// создаем приоритетную очередь из вектора с функтором сравнения less

priority_queue < deque<int>, less<int> > pq3 ( v.begin(), v.end() );

...

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

Многие контейнеры содержат компонентные функции rbegin, rend, которые подобно begin, end возвращают итераторы на начало и за конец контейнера; однако итератор на начало, возвращаемый rbegin, фактически ссылается на хвост контейнера, а для rend соответствующий итератор указывает перед началом контейнера. Например

list<int> l;

// записать в список значения 1 2 3 4

...

// вывод списка в обратном порядке

copy (l.rbegin(), l.rend(), ostream_iterator<int> (cout, " "));

В файле iterator.h явно определены шаблоны для введения реверсивных итераторов. Шаблон reverse_bidirectional_iterator позволяет определять двунаправленные реверсивные итераторы, а шаблон reverse_iterator – реверсивные итераторы произвольного доступа.

Еще пример:

list<int> l;

// заполнить список значениями 1 2 3 4

...

// вывод списка в обратном порядке

copy (reverse_iterator<int *, int, int &, ptrdiff_t>(l.end()),

reverse_iterator<int *, int, int &, ptrdiff_t>(l.begin()),

ostream_iterator<int> (cout, " ") ); // выведет 4 3 2 1

В примере reverse_iterator<int *, int, int &, ptrdiff_t>() представляет собой вызов конструктора копирования итератора, который создает реверсивный итератор произвольного доступа по итератору, переданному через параметр.

Итераторы вставки служат для упрощения процедуры вставки объектов в контейнеры. Принцип их применения состоит в том, что вставляемый объект записывается в итератор, а последний обеспечивает его вставку в нужную позицию контейнера. В зависимости от этой позиции выделяются три вида итераторов вставки: back_insert_iterator (вставка в хвост); front_insert_iterator (вставка в голову); insert_iterator (вставка в произвольную позицию). Для использования итераторов первого вида контейнер должен поддерживать функцию вставки в конец (push_back); для итераторов второго вида необходима поддержка операции вставки в начало (push_front). Итераторы вставки обладают возможностями выходных итераторов.

Примеры формирования итераторов вставки:

deque<int> d;

back_insert_iterator < deque<int> > bi(d);

front_insert_iterator < deque<int> > fi(d);

insert_iterator < deque<int> > i (d, d.end());

Формирование итераторов вставки может быть автоматическим. Для этого предусмотрены шаблоны функций back_inserter, front_inserter, inserter (этот шаблон мы уже использовали выше). Их определения выглядят так:

template <class Container>

back_insert_iterator<Container> back_inserter(Container & x) {

return back_insert_iterator<Container>(x);

}

template <class Container>

front_insert_iterator<Container> front_inserter(Container & x) {

return front_insert_iterator<Container>(x);

}

template <class Container, class Iterator>

insert_iterator<Container> inserter(Container & x, Iterator i) {

return insert_iterator<Container>(x, Container::iterator(i));

}

Пример

ifstream f("example"); // содержимое файла example: 1 3

deque<int> d;

copy( istream_iterator<int, ptrdiff_t>(f),

istream_iterator<int, ptrdiff_t>(),

back_inserter(d) ); // берем 1 3 из файла в d

vector<int> w (2,7); // вектор 7 7

copy( w.begin(), w.end(), front_inserter(d) ); // вставляем w в начало d

insert_iterator < deque<int> > i = inserter(d, ++d.begin());

*i = 9; // вставляем 9 в d перед позицией итератора i

// результат 7 9 7 1 3

Кроме двух рассмотренных видов адаптеров итераторов, в STL имеется еще один адаптер, называемый итератором неинициализированной памяти (raw storage iterator). Этот итератор используется главным образом внутренними алгоритмами STL для разбиения и слияния контейнеров.

Адаптеры функций нацелены на расширение возможностей функций и функторов (определения их содержатся в файле function.h). Основные их категории: инверторы, байндеры, адаптеры указателей на функции. Инверторы (negator) служат для инвертирования значений предикатов:

template <class Predicate> // для унарных предикатов

unary_negate<Predicate> not1(const Predicate & pred) {

return unary_negate<Predicate>(pred);

}

template <class Predicate> // для бинарных предикатов

binary_negate<Predicate> not2(const Predicate & pred) {

return binary_negate<Predicate>(pred);

}

Пример

vector<int> v;