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

template ‹class InputIterator1, class InputIterator2, class OutputIterator, class Compare›

OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

set_intersection создаёт сортированное пересечение элементов из двух диапазонов. Он возвращает конец созданного диапазона. Гарантируется, что set_intersection устойчив, то есть, если элемент присутствует в обоих диапазонах, он копируется из первого диапазона. Выполняется максимально ((last1-first1)+(last2-first2))*2-1 сравнений. Результат set_union не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

template ‹class InputIterator1, class InputIterator2, class OutputIterator›

OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template ‹class InputIterator1, class InputIterator2, class OutputIterator, class Compare›

OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

set_difference создаёт сортированную разность элементов из двух диапазонов. Он возвращает конец созданного диапазона. Выполняется максимально ((last1-first1)+(last2-first2))*2- сравнений. Результат set_difference не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

template ‹class InputIterator1, class InputIterator2, class OutputIterator›

OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template ‹class InputIterator1, class InputIterator2, class OutputIterator, class Compare›

OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

set_symmetric_difference создаёт сортированную симметричную разность элементов из двух диапазонов. Он возвращает конец созданного диапазона. Выполняется максимально ((last1-first1)+(last2-first2))*2-1 сравнений. Результат set_symmetric_difference не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

Пирамида - специфическая организация элементов в диапазоне между двумя итераторами произвольного доступа [a, b). Два её ключевые свойства: (1) *a - самый большой элемент в диапазоне, (2) *a может быть удалён с помощью pop_heap или новый элемент добавлен с помощью push_heap за O(logN) время. Эти свойства делают пирамиды полезными для приоритетных очередей. make_heap преобразовывает диапазон в пирамиду, a sort_heap превращает пирамиду в сортированную последовательность.

template ‹class RandomAccessIterator›

void push_heap(RandomAccessIterator first, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

push_heap полагает, что диапазон [first, last-1) является соответствующей пирамидой, и надлежащим образом помещает значение с позиции last-1 в результирующую пирамиду [first, last). Выполняется максимально log(last-first) сравнений.

template ‹class RandomAccessIterator›

void pop_heap(RandomAccessIterator first, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

pop_heap полагает, что диапазон [first, last) является соответствующей пирамидой, затем обменивает значения в позициях first и last-1 и превращает [first, last-1) в пирамиду. Выполняется максимально 2*log(last-first) сравнений.

template ‹class RandomAccessIterator›

void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

make_heap создает пирамиду из диапазона [first, last). Выполняется максимально 3*(last-first) сравнений.

template ‹class RandomAccessIterator›

void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

sort_heap сортирует элементы в пирамиде [first, last). Выполняется максимально NlogN сравнений, где N равно last-first. sort_heap не устойчив.

template ‹class T›

const T& min(const T& a, const T& b);

template ‹class T, class Compare›

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

template ‹class T›

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

template ‹class T, class Compare›

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) соответствующих сравнений.

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)) сравнений.

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 перестановок.