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 не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.
Операции над пирамидами (Heap operations)
Пирамида - специфическая организация элементов в диапазоне между двумя итераторами произвольного доступа [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 не устойчив.
Минимум и максимум (Minimum and maximum)
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›