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

Менг Ли

template ‹class RandomAccessIterator›

void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);

partial_sort помещает первые middle - first сортированных элементов из диапазона [first, last) в диапазон [first, middle). Остальная часть элементов в диапазоне [middle, last)

помещена в неопределённом порядке. Берётся приблизительно (last-first)*log(middle-first) сравнений.

template ‹class InputIterator, class RandomAccessIterator›

RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last);

template ‹class InputIterator, class RandomAccessIterator, class Compare›

RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);

partial_sort_copy помещает первые min(last-first, result_last-result_first) сортированных элементов в диапазон [result_first, result_first+min(last-first, result_last-result_first)). Возвращается или result_last, или result_first+(last-first), какой меньше. Берётся приблизительно (last-first)*log(min(last-first, result_last-result_first)) сравнений.

N-й элемент (Nth element)

template ‹class RandomAccessIterator›

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);

После операции nth_element элемент в позиции, указанной nth, является элементом, который был бы в той позиции, если бы сортировался целый диапазон. Также для любого итератора i в диапазоне [first, nth) и любого итератора j в диапазоне [nth, last) считается, что !(*i › *j) или comp(*i, *j)==false. Операция линейна в среднем.

Двоичный поиск (Binary search)

Все алгоритмы в этом разделе - версии двоичного поиска. Они работают с итераторами не произвольного доступа, уменьшая число сравнений, которое будет логарифмическим для всех типов итераторов. Они особенно подходят для итераторов произвольного доступа, так как эти алгоритмы делают логарифмическое число шагов в структуре данных. Для итераторов не произвольного доступа они выполняют линейное число шагов.

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