АДАПТЕРЫ

Адаптеры - шаблонные классы, которые обеспечивают отображения интерфейса. Например, 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

 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‹Operation› bind1st(const Operation& op, const T& x) {

 return binder1st‹Operation›(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.

Загрузка...