ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
template ‹class ForwardIterator, class T, class Compare›
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
upper_bound находит самую дальнюю позицию, в которую value может быть вставлено без нарушения упорядочения. upper_bound возвращает самый дальний итератор i в диапазоне [first, last) такой, что для любого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: !(value‹*j) или comp(value, *j)==false. Делается максимум log(last-first)+1 сравнений.
template ‹class ForwardIterator, class T›
ForwardIterator equal_range(ForwardIterator first, ForwardIterator last, const T& value);
template ‹class ForwardIterator, class T, class Compare›
ForwardIterator equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
equal_range находит самый большой поддиапазон [i, j) такой, что значение может быть вставлено по любому итератору k в нём. k удовлетворяет соответствующим условиям: !(*k ‹ value)&&!(value ‹ *k) или comp(*k, value)==false&& comp(value, *k)==false. Делается максимум 2*log(last-first)+1 сравнений.
template ‹class ForwardIterator, class T›
ForwardIterator binary_search(ForwardIterator first, ForwardIterator last, const T& value);
template ‹class ForwardIterator, class T, class Compare›
ForwardIterator binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
binary_search возвращает истину, если в диапазоне [first, last) имеется итератор i, который удовлетворяет соответствующим условиям: !(*i ‹ value)&&!(value ‹ *i) или comp(*i, value)==false&&comp(value, *i)==false. Делается максимум log(last-first)+2 сравнений.
Объединение (Merge)
template ‹class InputIterator1, class Input Iterator2, class OutputIterator›
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template ‹class InputIterator1, class InputIterator2, class OutputIterator, class Compare›
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
merge объединяет два сортированных диапазона [first1, last1) и [first2, last2) в диапазон [result, result+(last1-first1)+(last2-first2)). Объединение устойчиво, то есть для равных элементов в двух диапазонах элементы из первого диапазона всегда предшествуют элементам из второго. merge возвращает result+(last1-first1)+(last2-first2). Выполняется максимально (last1-first1)+(last2-first2)-1 сравнений. Результат merge не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.
template ‹class BidirectionalIterator›
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);