Александр Степанов - РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

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

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). Выполняется максимально log(last-first) сравнений.

template ‹class RandomAccessIterator›

void pop_heap(RandomAccessIterator first, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

pop_heap полагает, что диапазон [first, last) является соответствующей пирамидой, затем обменивает значения в позициях first и last-1 и превращает [first, last-1) в пирамиду. Выполняется максимально 2*log(last-first) сравнений.

template ‹class RandomAccessIterator›

void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

make_heap создает пирамиду из диапазона [first, last). Выполняется максимально 3*(last-first) сравнений.

template ‹class RandomAccessIterator›

void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

sort_heap сортирует элементы в пирамиде [first, last). Выполняется максимально NlogN сравнений, где N равно last-first. sort_heap не устойчив.

Минимум и максимум (Minimum and maximum)

template ‹class T›

const T& min(const T& a, const T& b);

template ‹class T, class Compare›

const T& min(const T& a, const T& b, Compare comp);

template ‹class T›

const T& max(const T& a, const T& b);

template ‹class T, class Compare›

const T& max(const T& a, const T& b, Compare comp);

min возвращает меньшее, а max большее. min и max возвращают первый параметр, когда их параметры равны.