Александр Степанов - РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

Адаптеры - шаблонные классы, которые обеспечивают отображения интерфейса. Например, insert_iterator обеспечивает контейнер интерфейсом итератора вывода.

Часто бывает полезно обеспечить ограниченные интерфейсы контейнеров. Библиотека предоставляет stack, queue и priority_queue через адаптеры, которые могут работать с различными типами последовательностей.

Любая последовательность, поддерживающая операции 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.

Любая последовательность, поддерживающая операции 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 х.с ‹ у.с;}

Любая последовательность, с итератором произвольного доступа и поддерживающая операции 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();

}

}; // Никакое равенство не обеспечивается

Двунаправленные итераторы и итераторы произвольного доступа имеют соответствующие адаптеры обратных итераторов, которые выполняют итерации через структуру данных в противоположном направлении.Они имеют те же самые сигнатуры, как и соответствующие итераторы. Фундаментальное соотношение между обратным итератором и его соответствующим итератором 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;}