Слияние смежных упорядоченных интервалов

void

lnplace ffierge (Bidirectionallterator begl,

Bidirectionallterator endlbeg2. Bidirectionallterator end?)

void

inplace merge (Bidirectionallterator begl.

Bidirectionallterator endlbeg2. Bidirectionallterator end2. BinaryPredicate op)

О Обе формы выполняют слияние смежных упорядоченных интервалов [beg1, end1beg2) и [end1beg2,end2) так, чтобы интервал [beg1,end2) содержал упорядоченную совокупность элементов обоих интервалов.

О Сложность линейная при наличии дополнительной памяти (питЬеЮ/Е1ете}и£-1 сравнений), nxlog(n) в противном случае (numberOfElementsxiog(numberOf-Elements) сравнений).

Пример использования алгоритма inplace merge():

algo/imergel.cpp #include algostuff.hpp using namespace std:

int main() {

list<int> coll:

Вставка двух упорядоченных интервалов INSERTJLEMENTS(C011.1.7); lNSERT ELEMENTS(col 1.1.8): PRINTJLEMENTS(coll);

Определение начала второго интервала (злемент после 7) list<int>;:iterator pos;

pos = find (coll.beginO. coll.endO. Интервал 7); Значение

++pos;

Слияние в один упорядоченный интервал inplace merge (coll.beginO, pos, coll.endO);

PRINT ELEMENTS(coll):

Результат выполнения программы выглядит так:

123456712345678 112233445566778

Численные алгоритмы

В этом разделе представлены алгоритмы STL, предназначенные для обработки числовых данных. Впрочем, с их помощью можно обрабатывать и другую информацию. Например, алгоритм accumulate() может применяться для конкатенации строк. Чтобы использовать числовые алгоритмы, в программу необходимо включить заголовочный файл <numeric>:

#includG <nurner1c>

Обработка интервалов

Вычисление результата по одному интервалу

accumulate (Inputlterator beg. Inputlterator end. T initValue)

accumulate (Inputlterator beg. Inputlterator end. T initVdlue. BinaryFunc op)

О Первая форма вычисляет и возвращает сумму initValue и всех элементов в интервале lbeg,end). Для каждого элемента выполняется команда:

initValue = initValue + elem

О Вторая форма вычисляет и возвращает накопленный результат вызова ор для initValue и каждого элемента в интервале [beg,end). Для каждого элемента выполняется команда:

initValue = opdnitValue, elem)

О Таким образом, пусть мы имеем следующие значения:

al а2 аЗ а4 ,

Для этих значений соответственно вычисляются и записываются такие величины:

initValue + al + а2 + аЗ + .,. initValue ор al ор а2 ор вЗ ор ...

О Для пустого интервала (beg end) обе формы возвращают initValue.

О Предикат ор не должен модифицировать передаваемые аргументы.

О Сложность линейная (numberOfElements вызовов оператора + или opQ соответственно).

В исходной версии STL численные алгоритмы определялись в заголовочном файле <aIgo.h>.

В следующем примере алгоритм accumulate() используется для вычисления суммы и произведения всех элементов интервала.

algo/accul.cpp Iinclude algostuff.hpp using namespace std;

lnt maln() {

vector<int> coll;

INSERTjLEMENTS(coll.l.9); PRINTJLEMENTSCcoll);

Вычисление суммы элементов cout sum;

accumulate Ccoll.beglnO, coll.endO, Интервал

0) Начальное значение

endl;

Вычисление суммы элементов с вычетом 100 cout sum:

accumulate (coll.beginO, coll.endO, Интервал

-100) Начальное значение

endl;

Вычисление произведения элементов cout product:

accumulate (coll.beginO. coll.endO, Интервал

1. Начальное значение

multiplles<int>()) Операция

endl:

Вычисление произведения элементов (с начальным значением 0) cout product:

accumulate (coll.beginO. coll.endO, Интервал

0. Начальное значение

multiplies<int>0) Операция

endl;

Результат выполнения программы выглядит так:

1 2 3 4 5 6 7 8 9 sum; 45 sum: -55 product: 362880 product; О

Последнее произведение равно нулю, поскольку при умножении любого числа на ноль результат равен нулю.