РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (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 не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

Операции над пирамидами (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›