Адаптеры - шаблонные классы, которые обеспечивают отображения
интерфейса. Например, insert_iterator обеспечивает контейнер
интерфейсом итератора вывода.
Адаптеры контейнеров (Container adaptors)
Часто бывает полезно обеспечить ограниченные интерфейсы контейнеров.
Библиотека предоставляет stack, queue и
priority_queue через адаптеры, которые могут работать с различными
типами последовательностей.
Стек (Stack)
Любая последовательность, поддерживающая операции back,
push_back и pop_back, может использоваться для модификации
stack. В частности, могут использоваться vector,
list и deque.
template <class Container>
class stack {
friend bool operator==(const stack<Container>& х, const stack<Container>& y);
friend bool operator<(const stack<Container>& х, const stack<Container>& y);
public:
typedef Container::value_type value_type;
typedef Container::size_type size_type;
protected:
Container c;
public:
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
value_type& top() { return c.back(); }
const value_type& top() const { return c.back(); }
void push(const value_type& х) { с.push_back(х); }
void pop() { c.pop_back(); }
};
template <class Container>
bool operator==(const stack <Container>& х, const stack<Container>& y)
{ return х.с == у.с;}
template <class Container>
bool operator<(const stack<Container>& х, const stack<Container>& y)
{ return х.с < у.с; }
Например, stack<vector<int> > - целочисленный
стек, сделанный из vector, а stack<deque<char>
> - символьный стек, сделанный из deque.
Очередь (Queue)
Любая последовательность, поддерживающая операции front,
push_back и pop_front, может использоваться для
модификации queue. В частности, могут использоваться list
и deque.
template <class Container>
class queue {
friend bool operator==(const queue<Container>& х, const queue<Container>& y);
friend bool operator<(const queue<Container>& х, const queue<Container>& y);
public:
typedef Container::value_type value_type;
typedef Container::size_type size_type;
protected:
Container c;
public:
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
value_type& front() { return c.front(); }
const value_type& front() const { return c.front(); }
value_type& back() { return c.back(); }
const value_type& back() const { return c.back(); }
void push(const value_type& х) { с.push_back(х); }
void pop() { с.pop_front(); }
};
template <class Container>
bool operator==(const queue<Container>& х, const queue<Container>& y)
{ return х.с == у.с;}
template <class Container>
bool operator<(const queue<Container>& х, const queue<Container>& y)
{ return х.с < у.с; }
Очередь с приоритетами (Priority queue)
Любая последовательность, с итератором произвольного доступа и
поддерживающая операции front, push_back и
pop_front, может использоваться для модификации
priority_queue. В частности, могут использоваться vector и
deque.
template <class Container, class Compare = less<Container::value_type> >
class priority_queue {
public:
typedef Container::value_type value_type;
typedef Container::size_type size_type;
protected:
Container c;
Compare comp;
public:
priority_queue(const Compare& х = Compare()) : c(), comp(х) {}
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last,
const Compare& х = Compare()) : c(first, last), comp(x)
{ make_heap(c.begin(), с.end(), comp); }
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const value_type& top() const { return c.front(); }
void push(const value_type& х) {
c.push_back(х);
push_heap(c.begin(), c.end(), comp);
}
void pop() {
pop_heap(c.begin(), c.end(), comp);
с.рор_bасk();
}
}; // Никакое равенство не обеспечивается
Адаптеры итераторов (Iterator adaptors)
Обратные итераторы (Reverse iterators)
Двунаправленные итераторы и итераторы произвольного доступа имеют
соответствующие адаптеры обратных итераторов, которые выполняют итерации через
структуру данных в противоположном направлении.Они имеют те же самые сигнатуры,
как и соответствующие итераторы. Фундаментальное соотношение между обратным
итератором и его соответствующим итератором i установлено тождеством
&*(reverse_iterator(i)) == &*(i - 1). Это отображение
продиктовано тем, что, в то время как после конца массива всегда есть указатель,
может не быть допустимого указателя перед началом массива.
template <class BidirectionalIterator, class T, class Reference = T&,
class Distance = ptrdiff_t>
class reverse_bidirectionaiIterator
: public bidirectional_iterator<T, Distance> {
typedef reverse_bidirectional_iterator<BidirectionalIterator, T,
Reference, Distance> self;
friend bool operator==(const self& х, const self& y);
protected:
BidirectionalIterator current;
public:
reverse_bidirectional_iterator() {}
reverse_bidirectional_iterator(BidirectionalIterator х)
: current(х) {}
BidirectionalIterator base() { return current; }
Reference operator*() const {
BidirectionalIterator tmp = current;
return *--tmp;
}
self& operator++() {
--current;
return *this;
}
self operator++(int) {
self tmp = *this;
--current;
return tmp;
}
self& operator--() {
++current;
return *this;
}
self operator--(int) {
self tmp = *this;
++current;
return tmp;
}
};
template <class BidirectionalIterator, class T, class Reference,
class Distance>
inline bool operator==(
const reverse_bidirectional_iterator<BidirectionalIterator, T,
Reference, Distance>& x,
const reverse_bidirectional_iterator<BidirectionalIterator,
T, Reference, Distance>& y){
return x.current == y.current;
}
template <class RandomAccessIterator, class T, class Reference = T&,
class Distance = ptrdiff_t>
class reverse_iterator : public random_access_iterator<T, Distance>{
typedef reverse_iterator<RandomAccessIterator, T, Reference,
Distance> self;
friend bool operator==(const self& x, const self& y);
friend bool operator<(const self& x, const self& y);
friend Distance operator-(const self& x, const self& y);
friend self operator+(Distance n, const self& x);
protected:
RandomAccessIterator current;
public:
reverse_iterator() {}
reverse_iterator(RandomAccessIterator x) : current (x) {}
RandomAccessIterator base() { return current; }
Reference operator*() const {
RandomAccessIterator tmp = current;
return *--tmp;
}
self& operator++() {
--current;
return *this;
}
self operator++(int) {
self tmp = *this;
--current;
return tmp;
}
self& operator--() {
++current;
return *this;
}
self operator--(int) {
self tmp = *this;
++current;
return tmp;
}
self operator+(Distance n) const {
return self (current - n);
}
self& operator+=(Distance n) {
current -= n;
return *this;
}
self operator-(Distance n) const {
return self(current + n);
}
self operator-=(Distance n) {
current +- n;
return *this;
}
Reference operator[](Distance n) { return *(*this + n);}
};
template <class RandomAccessIterator, class T, class Reference, class Distance>
inline bool operator==(
const reverse_iterator<RandomAccessIterator, T, Reference, Distance>& x,
const reverse_iterator<RandomAccessIterator, T, Reference, Distance>& y) {
return x.current == y.current;
}
template <class RandomAccessIterator, class T, class Reference, class Distance>
inline bool operator<(
const reverse_iterator<RandomAccessIterator, T, Reference, Distance>& x,
const reverse_iterator<RandomAccessIterator, T, Reference, Distance>& y) {
return y.current < x.current;
}
template <class RandomAccessIterator, class T, class Reference, class Distance>
inline Distance operator-(
const reverse_iterator<RandomAccessIterator, T, Reference, Distance>& х,
const reverse_iterator<RandomAccessIterator, T, Reference, Distance>& y) {
return y.current - x.current;
}
template <class RandomAccessIterator, class T, class Reference, class Distance>
inline reverse_iterator<RandomAccessIterator, T, Reference, Distance> operator+(
Distance n,
const reverse_iterator<RandomAccessIterator, T, Reference, Distance>& x) {
return reverse_iterator<RandomAccessIterator, T, Reference, Distance>
(x.current - n);
}
Итераторы вставки (Insert iterators)
Чтобы было возможно иметь дело с вставкой таким же образом, как с
записью в массив, в библиотеке обеспечивается специальный вид адаптеров
итераторов, называемых итераторами вставки (insert iterators). С
обычными классами итераторов
while (first != last) *result++ =
*first++;
вызывает копирование диапазона [first, last) в
диапазон, начинающийся с result. Тот же самый код с
result, являющимся итератором вставки, вставит соответствующие
элементы в контейнер. Такой механизм позволяет всем алгоритмам копирования в
библиотеке работать в режиме вставки (insert mode) вместо обычного
режима наложения записей.
Итератор вставки создаётся из контейнера и, возможно, одного из его
итераторов, указывающих, где вставка происходит, если это ни в начале, ни в
конце контейнера. Итераторы вставки удовлетворяют требованиям итераторов вывода.
operator* возвращает непосредственно сам итератор вставки.
Присваивание operator=(const T& х) определено для итераторов
вставки, чтобы разрешить запись в них, оно вставляет х прямо перед
позицией, куда итератор вставки указывает. Другими словами, итератор вставки
подобен курсору, указывающему в контейнер, где происходит вставка.
back_insert_iterator вставляет элементы в конце контейнера,
front_insert_iterator вставляет элементы в начале контейнера, а
insert_iterator вставляет элементы, куда итератор указывает в
контейнере. back_inserter, front_inserter и
inserter - три функции, создающие итераторы вставки из контейнера.
template <class Container>
class back_insert_iterator : public output_iterator {
protected:
Container& container;
public:
back_insert_iterator(Container& x) : container(x) {}
back_insert_iterator <Container>&
operator=(const Container::value_type& value) {
container.push_back(value);
return *this;
}
back_insert_iterator<Container>& operator*() { return *this; }
back_insert_iterator<Container>& operator++() { return *this; }
back_insert_iterator<Container>& operator++(int) { return *this; }
};
template <class Container>
back_insert_iterator<Container> back_inserter(Container& x) {
return back_insert_iterator<Container>(x);
}
template <class Container>
class front_insert_iterator : public output_iterator {
protected:
Container& container;
public:
front_insert_iterator(Container& x) : container (x) {}
front_insert_iterator<Container>&
operator=(const Container::value_type& value) {
container.push_front(value);
return *this;
}
front_insert_iterator<Container>& operator*() { return *this; }
front_insert_iterator<Container>& operator++() { return *this; }
front_insert_iterator<Container>& operator++(int) { return *this;}
};
template <class Container>
front_insert_iterator<Container> front_inserter(Container& x) {
return front_insert_iterator<Container>(х);
}
template <class Container>
class insert_iterator : public output_iterator {
protected:
Container& container;
Container::iterator iter;
public:
insert_iterator(Container& x, Container::iterator i)
: container (x), iter(i) {}
insert_iterator<Container>& operator=(const Container::value_type& value) {
iter = container.insert(iter, value);
++iter;
return *this;
}
insert_iterator<Container>& operator*() { return *this; }
insert_iterator<Container>& operator++() { return *this; }
insert_iterator<Container>& operator++(int) { return *this; }
};
template <class Container, class Iterator>
insert_iterator&tl;Container> inserter(Container& x, Iterator i) {
return insert_iterator<Container>(x, Container::iterator(i));
}
Адаптеры функций (Function adaptors)
Функциональные адаптеры работают только с классами функциональных
объектов с определёнными типами параметров и типом результата.
Отрицатели (Negators)
Отрицатели not1 и not2 берут унарный и бинарный
предикаты соответственно и возвращают их дополнения.
template <class Predicate>
class unary_negate : public unary_function<Predicate::argument_type, bool> {
protected:
Predicate pred;
public:
unary_negate(const Predicate& x) : pred(x) {}
bool operator()(const argument_type& x) const { return !pred(x); }
};
template <class Predicate>
unary_negate<Predicate> not1(const Predicate& pred) {
return unary_negate<Predicate>(pred);
}
template <class Predicate>
class binary_negate : public binary_function<Predicate::first_argument_type,
Predicate::second_argument_type, bool> {
protected:
Predicate pred;
public:
binary_negate(const Predicate& x) : pred(x) {}
bool operator()(const first_argument_type& x,
const second_argument_type& y) const {
return !pred(x, y);
}
};
template <class Predicate>
binary_negate<Predicate> not2(const Predicate& pred) {
return binary_negate<Predicate>(pred);
}
Привязки (Binders)
Привязки bind1st и bind2nd берут функциональный
объект f двух параметров и значение x и возвращают
функциональный объект одного параметра, созданный из f с первым или
вторым параметром соответственно, связанным с х.
template <class Predicate>
class binder1st : public unary_function {
protected:
Operation op;
Operation::first_argument_type value;
public:
binder1st(const Operation& x, const Operation::first_argument_type& y)
: op(x), value(y) {}
result_type operator()(const argument_type& x) const {
return op(value, x);
}
};
template <class Operation, class T>
binder1st<0peration> bind1st(const Operation& op, const T& x) {
return binder1st<0peration>(op, Operation::first_argument_type(x));
}
template <class Operation>
class binder2nd : public unary_function<0peration::first_argument_type,
Operation::result_type> {
protected:
Operation op;
Operation::second_argument_type value;
public:
binder2nd(const Operation& x, const Operation::second_argument_type& y)
: op(x), value(y) {}
result_type operator()(const argument_type& x) const {
return op(x, value);
}
};
template <class Operation, class T>
binder2nd<Operation> bind2nd(const Operation& op, const T& x) {
return binder2nd<0peration>(op, Operation::second_argument_type(x));
}
Например, find_if(v.begin(), v.end(), bind2nd(greater<int>(),
5)) находит первое целое число в векторе v большее, чем 5;
find_if(v.begin(), v.end(), bind1st(greater<int>(), 5)) находит
первое целое число в v меньшее, чем 5.
Адаптеры указателей на функции (Adaptors for pointers to functions)
Чтобы позволить указателям на (унарные и бинарные) функции работать с
функциональными адаптерами, библиотека обеспечивает следующее:
template <class Arg, class Result>
class pointer_to_unary_function : public unary_function<Arg, Result> {
protected:
Result (*ptr)(Arg);
public:
pointer_to_unary_function() {}
pointer_to_unary_function(Result (*x)(Arg)) : ptr(x) {}
Result operator()(Arg x) const { return ptr(x); }
};
template <class Arg, class Result>
pointer_to_unary_function<Arg, Result> ptr_fun(Result (*x)(Arg)) {
return pointer_to_unary_function<Arg, Result>(x);
}
template
class pointer_to_binary_function : public binary_function {
protected:
Result (*ptr)(Arg1, Arg2);
public:
pointer_to_binary_function() {}
pointer_to_binary_function(Result (*x)(Arg1, Arg2)) : ptr(х) {}
Result operator()(Arg1 x, Arg2 y) const { return ptr(x, y); }
};
template <class Arg1, class Arg2, class Result>
pointer_to_binary_function<Arg1, Arg2, Result>
ptr_fun(Result (*x)(Arg1, Arg2)) {
return pointer_to_binary_function<Argl, Arg2, Result>(x);
}
Например, replace_if(v.begin(), v.end(),
not1(bind2nd(ptr_fun(strcmp), "C")), "C++") заменяет все "С" на
"C++" в последовательности v.
Системы трансляции, которые имеют множественный указатель на типы
функций, должны обеспечить дополнительные шаблоны функций ptr_fun.
