Язык программирования C++. Пятое издание - Стенли Липпман

lower_bound(beg, end, val)

lower_bound(beg, end, val, comp)

Возвращает итератор, обозначающий первый элемент, значение которого больше или равно значению val, или итератор end, если такого элемента нет.

upper_bound(beg, end, val)

upper_bound(beg, end, val, comp)

Возвращает итератор, обозначающий первый элемент, значение которого меньше значения val, или итератор end, если такого элемента нет.

equal_range(beg, end, val)

equal_range(beg, end, val, comp)

Возвращает пару (см. раздел 11.2.3), член first которой является итератором, возвращаемым функцией lower_bound(), а член second — итератором, возвращаемым функцией upper_bound().

binary_search(beg, end, val)

binary_search(beg, end, val, comp)

Возвращает логическое значение, свидетельствующее о наличии в последовательности элемента, значение которого равно val. Два значения, x и y, считаются равными, если x не меньше y и y не меньше x.

А.2.4. Алгоритмы записи в элементы контейнера

Запись в элементы контейнера осуществляется многими алгоритмами. Эти алгоритмы могут отличаться видом итераторов, используемых для обозначения их исходной последовательности, а также тем, осуществляют ли они запись в элементы исходного диапазона или указанного результирующего диапазона.

Алгоритмы, которые записывают, но не читают значения элементов

Для обозначения назначения этим алгоритмам требуются итераторы вывода. Версии _n получают второй определяющий количество аргумент и записывают заданный набор элементов по назначению.

fill(beg, end, val)

fill_n(dest, cnt, val)

generate(beg, end, Gen)

generate_n(dest, cnt, Gen)

Присваивают новое значение каждому элементу исходной последовательности. Алгоритм fill() присваивает значение val; алгоритм generate() выполняет объект генератора Gen. Генератор — это вызываемый объект (см. раздел 10.3.2), возвращающий при каждом вызове разные значения. Алгоритмы fill() и generate() возвращают тип void. Версии _n возвращают итератор на позицию непосредственно после последнего элемента, записанного в последовательность назначения.

Алгоритмы записи с итераторами ввода

Каждый из этих алгоритмов читает исходную последовательность и пишет последовательность вывода. Они требуют, чтобы dest был итератором вывода, а итераторы, обозначающие исходный диапазон, должны быть итераторами ввода.

copy(beg, end, dest)

copy_if(beg, end, dest, unaryPred)

copy_n(beg, n, dest)

Копирует из исходного диапазона последовательности, обозначенные итератором dest. Алгоритм copy() копирует все элементы, а алгоритм copy_if() копирует те из них, для которых предикат unaryPred истин, а алгоритм copy_n() копирует первые n элементов. У исходной последовательности должно быть по крайней мере n элементов.

move(beg, end, dest)

Вызов функции std::move() (см. раздел 13.6.1) для каждого элемента в исходной последовательности позволяет переместить этот элемент в последовательность, начиная с итератора dest.

transform(beg, end, dest, unaryOp)

transform(beg, end, beg2, dest, binaryOp)

Вызывает заданную операцию и пишет ее результат в dest. Первая версия применяет унарную операцию к каждому элементу в исходном диапазоне. Вторая применяет бинарную операцию к элементам этих двух исходных последовательностей.

replace_copy(beg, end, dest, old_val, new_val)

replace_copy_if(beg, end, dest, unaryPred, new_val)

Копируют каждый элемент в dest, заменяя определенные элементы значением new_val. Первая версия заменяет элементы == old_val, а вторая версия — элементы, удовлетворяющие предикату unaryPred.

merge(beg1, end1, beg2, end2, dest)

merge(beg1, end1, beg2, end2, dest, comp)

Сортирует обе исходные последовательности. Записывает в dest объединенную последовательность. Первая версия сравнивает элементы при помощи оператора <; а вторая использует предоставленный оператор сравнения.

Алгоритмы записи с прямыми итераторами

Этим алгоритмам требуются прямые итераторы, поскольку они пишут в элементы своих исходных последовательностей. Итераторы должны предоставлять доступ для записи в элементы.

iter_swap(iter1, iter2)

swap_ranges(beg1, end1, beg2)

Заменяет элемент, обозначенный итератором iter1, элементом, обозначенным итератором iter2; или обменивает все элементы в исходном диапазоне с таковыми из второй последовательности, начиная с позиции beg2. Диапазоны не должны пересекаться. Алгоритм iter_swap() возвращает void; алгоритм swap_ranges возвращает итератор beg2, увеличенный так, чтобы обозначить элемент сразу после последнего обмененного.

replace(beg, end, old_val, new_val)

replace_if(beg, end, unaryPred, new_val)

Заменяет каждый элемент, соответствующий значению new_val. Первая версия использует для сравнения элементов со значением old_val оператор ==, а вторая заменяет те элементы, для которых истин предикат unaryPred.

Алгоритмы записи с двунаправленными итераторами

Поскольку этим алгоритмам необходима способность вернуться назад в последовательности, они требуют двунаправленных итераторов.

copy_backward(beg, end, dest)

move_backward(beg, end, dest)

Копирует или перемещает элементы из исходного диапазона в заданный. В отличие от других алгоритмов, dest — итератор после конца для выходной последовательности (т.е. последовательность назначения закончится непосредственно перед dest). Последний элемент в исходном диапазоне копируется или перемещается в последний элемент назначения, затем копируется (перемещается) предпоследний элемент и т.д. У элементов в последовательности назначения тот же порядок, что и в исходном диапазоне. Если диапазон пуст, возвращается итератор dest, в противном случае возвращается итератор на элемент, который был скопирован или перемещен из *beg.

inplace_merge(beg, mid, end)

inplace_merge(beg, mid, end, comp)

Объединяет две отсортированные внутренние последовательности из той же последовательности в единую, упорядоченную последовательность. Внутренние последовательности от beg до mid и от mid до end объединяются и записываются назад в первоначальную последовательность. Первая версия использует для сравнения элементов оператор <, а вторая версия использует заданную операцию сравнения. Возвращают void.

А.2.5. Алгоритмы сортировки и разделения

Алгоритмы сортировка и разделения предоставляют различные стратегии упорядочивания элементов последовательности.

Каждый алгоритм сортировки и разделения поддерживает стабильные и нестабильные версии (см. раздел 10.3.1). Стабильный алгоритм обеспечивает относительный порядок равных элементов. Стабильные алгоритмы выполняют больше работы, а следовательно, могут выполняться медленней и использовать больше памяти, чем нестабильные аналоги.

Алгоритмы разделения

Алгоритмы разделения делят элементы исходного диапазона на две группы. Первая группа состоит из элементов удовлетворяющих определенному предикату, а вторая — нет. Например, элементы последовательности можно разделить на основании четности их значений или на основании того, начинается ли слово с заглавной буквы, и так далее. Этим алгоритмам требуются двунаправленные итераторы.

is_partitioned(beg, end, unaryPred)

Возвращает значение true, если все элементы, удовлетворяющие предикату unaryPred, предшествуют тем, для которых предикат unaryPred возвращает значение false. Если последовательность пуста, также возвращается значение true.

partition_copy(beg, end, dest1, dest2, unaryPred)

Копирует в dest1 элементы, для которых истин предикат unaryPred, а остальные копирует в dest2. Возвращает пару (см. раздел 11.2.3) итераторов. Член first пары обозначает конец скопированных в dest1 элементов, а член second обозначает конец элементов, скопированных в dest2. Исходная последовательность не может налагаться ни на одну из результирующих последовательностей.

partition_point(beg, end, unaryPred)

Для разделения исходной последовательности используется предикат unaryPred. Возвращает итератор на элемент за последним, удовлетворяющим предикату unaryPred. Если возвращен итератор не end, то предикат unaryPred должен возвращать значение false для возвращенного итератора и для всех элементов, следующих за ним.