О В приемном интервале элементы следуют в порядке сортировки.

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

О Обе формы возвращают позицию за последним скопированным элементом в приемном интервале.

О В необязательном параметре ор передается бинарный предикат, определяющий критерий сортировки: op(elem1 ,elem2),

О Алгоритмы не изменяют состояние исходных интервалов.

О Перед вызовом интервалы должны быть упорядочены по соответствующему критерию сортировки.

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

О Приемный интервал не должен перекрываться с исходными интервалами.

О Сложность линейная (не более 2x(numberOfElements1+numberOfElements2)-[ сравнений).

Пример использования алгоритма set difference() приведен далее. В этом примере также продемонстрированы отличия алгоритма set difference() от других алгоритмов, комбинирующих элементы двух упорядоченных интервалов.

Пример использования алгоритмов слияния

в следующем примере сравниваются алгоритмы, комбинирующие элементы двух упорядоченных исходных интервалов, демонстрируются принципы их работы и различия между ними:

algo/sGtalgos.cpp #lnclude "algostuff.hpp" using namespace std;

int mainO {

int cl[] = { 1. 2. 2. 4. 6. 7. 7. 9 }: int numl = sizeof(cl) / sizeofCint);

int c2[] = { 2. 2. 2. 3, 6. 6. 8. 9 }; int num2 = sizeof(c2) / sizeof(int):

Вывод исходных интервалов

cout « "cl: " ;

copy (Cl, cl+numl.

ostream iterator<int>(cout." ")); cout « endl;

cout « "C2; " ;

copy (c2, c2+num2,

ostream iterator<int>(cout," "));

cout « \n « endl;

Суммирование интервалов апгоритмом mergeO cout « "mergeO: ":

merge (cl. cl+numl. cl, c2+num2.

ostreamjterator<1nt>(cout." ")); cout « endl;

Объединение интервалов алгоритмом set union() cout « set un1on(); ":

set union (cl, cl+numl, c2, c2+num2,

ostream iterator<1nt>(cout." ")); cout « endl;

Пересечение интервалов алгоритмом setJntersect1on() cout « "setJntersectionO: setjntersection (cl, cl+numl.

c2. c2+num2,

ostreamjterator<int>(cout. ")):

cout « endl:

Определение злементов первого интервала, не входящих во второй интервап. алгоритмом set difference() cout « "setJifferenceO: ";

set difference (cl, cl+numl, c2. c2+num2,

ostreamjterator<int>(cout," "));

cout « endl;

Вычисление разности интервалов алгоритмом set symmetric difference() cout « "set symmetric difference(): ": set symmetric difference (cl. cl+numl.

c2, c2+num2.

ostreamjterator<1nt>(cout." "))\

cout « endl:

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

cl: 12 2 4 6 7 7 9

с2: 2 2 2 3 6 6 8 9

mergeO: 1222223466677899

set union(): 122234557789

setJntersectionO; 2 2 6 9

set difference(); 14 7 7

set symmetric difference(): 12346778

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

void

inplace ffierge (Bidirectionallterator begi,

Bidirectionallterator endlbeg2. Bidirectionallterator end?)

void

inplace merge (Bidirectionallterator begi.

Bidirectionallterator endlbeg2. Bidirectionallterator end2. BinaryPredicate op)

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

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

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

algo/iinergel,cpp #include "algostuff.hpp" using namespace std:

int main() {

list<int> coll:

Вставка двух упорядоченных интервалов INSERTJLEMENTS(C011.1.7); lNSERT ELEMENTS(coll.l.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