Александр Степанов - РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)
template ‹class BidirectionalIterator›
void reverse(BidirectionalIterator first, BidirectionalIterator last);
Для каждого неотрицательного целого числа i‹=(last-first)/2 функция reverse применяет перестановку ко всем парам итераторов first+i, (last-i)-1. Выполняется точно (last-first)/2 перестановок.
template ‹class BidirectionalIterator, class OutputIterator›
OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
reverse_copy копирует диапазон [first, last) в диапазон [result, result+(last-first)) такой, что для любого неотрицательного целого числа i ‹ (last-first) происходит следующее присваивание: *(result+(last-first)-i) = *(first+i). reverse_copy возвращает result+(last-first). Делается точно last-first присваиваний. Результат reverse_copy не определён, если [first, last) и [result, result +(last-first)) перекрываются.
Переместить по кругу (Rotate)
template ‹class ForwardIterator›
void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
Для каждого неотрицательного целого числа i ‹ (last-first) функция rotate помещает элемент из позиции first+i в позицию first+(i+(last-middle))%(last-first). [first, middle) и [middle, last) - допустимые диапазоны. Максимально выполняется last-first перестановок.
template ‹class ForwardIterator, class OutputIterator›
OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
rotate_copy копирует диапазон [first, last) в диапазон [result, result+(last-first)) такой, что для каждого неотрицательного целого числа i ‹ (last-first) происходит следующее присваивание: *(result+(i+(last-middle))%(last-first)) = *(first+i). rotate_copy возвращает result+(last-first). Делается точно last-first присваиваний. Результат rotate_copy не определён, если [first, last) и [result, result+(last-first)) перекрываются.
Перетасовать (Random shuffle)
template ‹class RandomAccessIterator›
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
template ‹class RandomAccessIterator, class RandomNumberGenerator›
void random_shuffie(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand);
random_shuffle переставляет элементы в диапазоне [first, last) с равномерным распределением. Выполняется точно last-first перестановок. random_shuffle может брать в качестве параметра особый генерирующий случайное число функциональный объект rand такой, что rand берёт положительный параметр n типа расстояния RandomAccessIterator и возвращает случайно выбранное значение между 0 и n-1.
Разделить (Partitions)
template ‹class BidirectionalIterator, class Predicate›
BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
partition помещает все элементы в диапазоне [first, last), которые удовлетворяют pred, перед всеми элементами, которые не удовлетворяют. Возвращается итератор i такой, что для любого итератора j в диапазоне [first, i) будет pred(*j)==true, а для любого итератора k в диапазоне [i, last) будет pred(*k)==false. Делается максимально (last-first)/2 перестановок. Предикат применяется точно last-first раз.
template ‹class BidirectionalIterator, class Predicate›
BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
stable_partition помещает все элементы в диапазоне [first, last), которые удовлетворяют pred, перед всеми элементами, которые не удовлетворяют. Возвращается итератор i такой, что для любого итератора j в диапазоне [first, i) будет pred(*j)==true, а для любого итератора k в диапазоне [i, last) будет pred(*k)==false. Относительный порядок элементов в обеих группах сохраняется. Делается максимально (last-first)*log(last-first) перестановок, но только линейное число перестановок, если имеется достаточная дополнительная память. Предикат применяется точно last-first раз.
Операции сортировки и отношения (Sorting and related operations)
Все операции в этом разделе имеют две версии: одна берёт в качестве параметра функциональный объект типа Compare, а другая использует operator‹.
Compare - функциональный объект, который возвращает значение, обратимое в bool. Compare comp используется полностью для алгоритмов, принимающих отношение упорядочения. comp удовлетворяет стандартным аксиомам для полного упорядочения и не применяет никакую непостоянную функцию к разыменованному итератору. Для всех алгоритмов, которые берут Compare, имеется версия, которая использует operator‹ взамен. То есть comp(*i, *j)==true по умолчанию для *i‹*j==true.
Последовательность сортируется относительно компаратора comp, если для любого итератора i, указывающего на элемент в последовательности, и любого неотрицательного целого числе n такого, что i + n является допустимым итератором, указывающим на элемент той же самой последовательности, comp(*(i+n), *i)==false.
В описаниях функций, которые имеют дело с упорядочивающими отношениями, мы часто используем представление равенства, чтобы описать такие понятия, как устойчивость. Равенство, к которому мы обращаемся, не обязательно operator==, а отношение равенства стимулируется полным упорядочением. То есть два элементa a и b считаются равными, если и только если !(a ‹ b)&&!(b ‹ a).
Сортировка (Sort)
template ‹class RandomAccessIterator›
void sort(RandomAccessIterator first, RandomAccessIterator last);
template ‹class RandomAccessIterator, class Compare›
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare соmр);
sort сортирует элементы в диапазоне [first, last). Делается приблизительно NIogN (где N равняется last-first) сравнений в среднем. Если режим наихудшего случая важен, должны использоваться stable_sort или partial_sort.
template ‹class RandomAccessIterator›
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template ‹class RandomAccessIterator, class Compare›
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
stable_sort сортирует элементы в диапазоне [first, last). Он устойчив, то есть относительный порядок равных элементов сохраняется. Делается максимум N(logN)2 (где N равняется last-first) сравнений; если доступна достаточная дополнительная память, тогда это - NlogN.
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 сравнений.
