РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

template ‹class ForwardIterator, class T›

ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

template ‹class ForwardIterator, class T, class Compare›

ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

lower_bound находит первую позицию, в которую value может быть вставлено без нарушения упорядочения. lower_bound возвращает самый дальний итератор i в диапазоне [first, last) такой, что для любого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: *j‹value или comp(*j, value)==true. Делается максимум log(last-first)+1 сравнений.

template ‹class ForwardIterator, class T›

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&∁(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);