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

const T& max(const T& a, const T& b, Compare comp);

min возвращает меньшее, а max большее. min и max возвращают первый параметр, когда их параметры равны.

template ‹class ForwardIterator›

ForwardIterator max_element(ForwardIterator first, ForwardIterator last);

template ‹class ForwardIterator, class Compare›

ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp);

max_element возвращает первый такой итератор i в диапазоне [first, last), что для любого итератора j в диапазоне [first, last) выполняются следующие соответствующие условия: !(*i‹*j) или comp(*i, *j)==false. Выполняется точно max((last-first)-1, 0) соответствующих сравнений.

template ‹class ForwardIterator›

ForwardIterator min_element(ForwardIterator first, ForwardIterator last);

template ‹class ForwardIterator, class Compare›

ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp);

min_element возвращает первый такой итератор i в диапазоне [first, last), что для любого итератора j в диапазоне [first, last) выполняются следующие соответствующие условия: !(*j‹*i) или comp(*j, *i)==false. Выполняется точно max((last-first)-1, 0) соответствующих сравнений.

Лексикографическое сравнение (Lexicographical comparison)

template ‹class InputIterator1, class InputIterator2›

bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

template ‹class InputIterator1, class InputIterator2, class Compare›

bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);

lexicographical_compare возвращает true, если последовательность элементов, определённых диапазоном [first1, last1), лексикографически меньше, чем последовательность элементов, определённых диапазоном [first2, last2). Иначе он возвращает ложь. Выполняется максимально 2*min((last1-first1), (last2-first2)) сравнений.

Генераторы перестановок (Permutation generators)

template ‹class BidirectionalIterator›

bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);

template ‹class BidirectionalIterator, class Compare›

bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

next_permutation берёт последовательность, определённую диапазоном [first, last), и трансформирует её в следующую перестановку. Следующая перестановка находится, полагая, что множество всех перестановок лексикографически сортировано относительно operator‹ или comp. Если такая перестановка существует, возвращается true. Иначе он трансформирует последовательность в самую маленькую перестановку, то есть сортированную по возрастанию, и возвращает false. Максимально выполняется (last-first)/2 перестановок.

template ‹class BidirectionalIterator›

bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);

template ‹class BidirectionalIterator, class Compare›

bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

prev_permutation берёт последовательность, определённую диапазоном [first, last), и трансформирует её в предыдущую перестановку. Предыдущая перестановка находится, полагая, что множество всех перестановок лексикографически сортировано относительно operator‹ или comp. Если такая перестановка существует, возвращается true. Иначе он трансформирует последовательность в самую большую перестановку, то есть сортированную по убыванию, и возвращает false. Максимально выполняется (last - first)/2 перестановок.

Обобщённые численные операции (Generalized numeric operations)

Накопление (Accumulate)

template ‹class InputIterator, class T›

T accumulate(InputIterator first, InputIterator last, T init);

template ‹class InputIterator, class T, class BinaryOperation›

T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op);

accumulate подобен оператору APL reduction и функции Common Lisp reduce, но он избегает трудности определения результата уменьшения для пустой последовательности, всегда требуя начальное значение. Накопление выполняется инициализацией сумматора acc начальным значением init и последующим изменением его acc = acc+*i или acc = binary_op(acc, *i) для каждого итератора i в диапазоне [first, last) по порядку. Предполагается, что binary_op не вызывает побочных эффектов.

Скалярное произведение (Inner product)

template ‹class InputIterator1, class InputIterator2, class T›

T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init);

template ‹class InputIterator1, class InputIterator2, class T, class BinaryOperation1, class BinaryOperation2›

T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init, BinaryOperation1 binary_op1, BinaryOperation2 binary_op2);

inner_product вычисляет свой результат, инициализируя сумматор acc начальным значением init и затем изменяя его acc = acc+(*i1)*(*i2) или acc = binary_op1(acc, binary_op2(*i1, *i2)) для каждого итератора i1 в диапазоне [first, last) и итератора i2 в диапазоне [first2, first2+(last-first)) по порядку. Предполагается, что binary_op1 и binary_op2 не вызывают побочных эффектов.

Частичная сумма (Partial sum)

template ‹class InputIterator, class OutputIterator›

OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result);

template ‹class InputIterator, class OutputIterator, class BinaryOperation›

OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op);

partial_sum присваивает каждому итератору i в диапазоне [result, result+(last-first)) значение, соответственно равное ((…(*first+*(first+1))+…)+*(first+(i-result))) или binary_op(binary_op(…, binary_op(*first, *(first+1)),…), *(first+(i-result))). Функция partial_sum возвращает result+(last-first). Выполняется binary_op точно (last-first)-1 раз. Ожидается, что binary_op не имеет каких-либо побочных эффектов. result может быть равен first.

Смежная разность (Adjacent difference)

template ‹class InputIterator, class OutputIterator›

OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);

template ‹class InputIterator, class OutputIterator, class BinaryOperation›

OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op);

adjacent_difference присваивает каждому элементу, указываемому итератором i в диапазоне [result+1, result+(last-first)) значение, соответственно равное *(first+(i-result))-*(first+(i-result)-1) или binary_op(*(first+(i-result)), *(first+(i-result)-1)). Элемент, указываемый result, получает значение *first. Функция adjacent_difference возвращает result+(last-first). Применяется binary_op точно (last-first)-1 раз. Ожидается, что binary_op не имеет каких-либо побочных эффектов. result может быть равен first.

АДАПТЕРЫ

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