Александр Степанов - РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)
Очередь с приоритетами (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;
}
