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

Алгоритмы equal_range(), lower_bound()и upper_bound()возвращают итераторы на позиции последовательности, куда мог бы быть вставлен заданный элемент при сохранении существующего порядка в последовательности. Если элемент больше всех остальных в последовательности, то возвращаемый итератор будет итератором после конца.

Каждый алгоритм предоставлен в двух версиях: первая использует для проверки элементов оператор меньше ( <) типа элемента, а вторая использует заданную функцию сравнения. В следующих алгоритмах " xменьше, чем y" означает, что выражения xи comp(x, y)истинны:

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.

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

Для обозначения назначения этим алгоритмам требуются итераторы вывода . Версии _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.