void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
template ‹class BidirectionalIterator, class Compare›
void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
inplace_merge объединяет два сортированных последовательных диапазона [first, middle) и [middle, last), помещая результат объединения в диапазон [first, last). Объединение устойчиво, то есть для равных элементов в двух диапазонах элементы из первого диапазона всегда предшествуют элементам из второго. Когда доступно достаточно дополнительной памяти, выполняется максимально (last-first)-1 сравнений. Если никакая дополнительная память не доступна, может использоваться алгоритм со сложностью O(NlogN).
Операции над множеством для сортированных структур (Set operations on sorted structures)
Этот раздел определяет все основные операции над множеством для сортированных структур. Они даже работают с множествами с дубликатами, содержащими множественные копии равных элементов. Семантика операций над множеством обобщена на множества с дубликатами стандартным способом, определяя объединение, содержащее максимальное число местонахождений каждого элемента, пересечение, содержащее минимум, и так далее.
template ‹class InputIterator1, class InputIterator2›
bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
template ‹class InputIterator1, class InputIterator2, class Compare›
bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
includes возвращает true, если каждый элемент в диапазоне [first2, last2) содержится в диапазоне [first1, last1). Иначе возвращается false. Выполняется максимально ((last1-first1)+(last2-first2))*2-1 сравнений.
template ‹class InputIterator1, class InputIterator2, class OutputIterator›
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template ‹class InputIterator1, class InputIterator2, class OutputIterator, class Compare›
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
set_union создаёт сортированное объединение элементов из двух диапазонов. Он возвращает конец созданного диапазона. set_union устойчив, то есть, если элемент присутствует в обоих диапазонах, он копируется из первого диапазона. Выполняется максимально ((last1-first1)+(last2-first2))*2-1 сравнений. Результат set_union не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.
template ‹class InputIterator1, class InputIterator2, class OutputIterator›
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
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).
