Слияние отсортированных интервалов

Как и прежде, первая форма каждого алгоритма предполагает, что при сортировке интервала используется внутренний оператор <. Вторая форма применяется в том случае, если сортировка выполнялась специальным объектом функции. При вызове алгоритмов должен быть задействован тот же способ сравнения, что и при сортировке; в противном случае результат выполнения алгоритма не определен. Попытка применить эти алгоритмы к несортированным интервалам также приводит к неопределенным результатам.

Outputlterator mergeCInputlteratorl firstl. Inputlteratorl lastl.

InputIterator2 first2. InputIterator2 last2. Outputlterator result): Outputlterator merge(Inputlteratorl firstl. Inputlteratorl lastl.

InputIterator2 first2, InputIterator2 last2.

Outputlterator result. StrictWeakOrdering binary pred):

Алгоритм копирует элементы из [firstl,lastl) в result так, что полученный интервал сортируется по возрастанию. После выполнения операции сохраняется относительный порядок следования элементов.

void inplace merge(BTdirectionalIterator first.

Bidirectionallterator middle. Bidirectionallterator last): void inplace merge(BidirectionalIterator first.

Bidirectionallterator middle. Bidirectionallterator last.

StrictWeakOrdering binary pred):

Предполагается, что [firstmiddle) и [middLe,last) являются отсортированными последовательностями, образующими один интервал. Алгоритм производит слияние последовательностей таким образом, что полученный интервал [firstlast) содержит отсортированную совокупность элементов исходных последовательностей.

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

: C06:MergeTest.cpp

Слияние отсортированных интервалов

{L} Generators

linclude <algorithm>

linclude PrintSequence.h

linclude Generators.h

using namespace std:

int mainO { const int SZ = 15: int a[SZ*2] = {0}:

Оба подынтервала принадлежат одному массиву: generate(a. а + SZ. SkipGenCO, 2)): а[3] = 4: а[4] = 4:

generateCa + SZ. а + SZ*2. SkipGend. 3)):

printCa. a + SZ. rangel , ):

printCa + SZ. a + SZ*2. range2 . ):

int b[SZ*2] = {0}: Инициализация всего массива нулями

mergeCa. а + SZ, а + SZ. а + SZ*2. b):

printCb. b + SZ*2. merge . );

Обнуление b

forCint i = 0: i < SZ*2: i++)

Ь[1] = 0:

inplace merge(a, а + SZ. а + SZ*2); print(a. а + SZ*2. inplace merge . ): int* end = set union(a. a + SZ. a + SZ. a + SZ*2. b): print(b. end. set un1on . ): } /:-

В функции main() вместо двух раздельных массивов мы создаем два интервала, расположенных вплотную друг к другу в массиве а (это удобно для алгоритма inplace merge). Первый вызов merge() заносит результат в другой массив Ь. Для сравнения также вызывается алгоритм set union(), который обладает сходной сигнатурой и аналогичным поведением, но с одним отличием: он удаляет дубликаты из второго набора. Наконец, алгоритм inplace merge() объединяет обе части а.

Теоретико-множественные операции с отсортированными интервалами

с отсортированными интервалами также можно выполнять математические операции из теории множеств.

bool includes(Inputlteratorl firstl. Inputlteratorl lastl.

InputIterator2 first2. InputIterator2 last2): bool includes(Inputlteratorl firstl. Inputlteratorl lastl.

InputIterator2 first2. InputIterator2 last2.

StrictWeakOrdering binary pred):

Алгоритм возвращает true, если интервал [first2,last2) является подмножеством интервала [firstl,lastl). Ни один из интервалов не обязан содержать только уникальные элементы, но если интервал [first2,last2) содержит п экземпляров некоторого значения, то интервал [firstl,lastl) тоже должен содержать минимум п экземпляров этого значения.

Outputlterator set union(Inputlteratorl firstl,

Inputlteratorl lastl, InputIterator2 first2.

InputIterator2 last2, Outputlterator result); Outputlterator set union(Inputlteratorl firstl.

Inputlteratorl lastl. InputIterator2 first2.

InputIterator2 last2. Outputlterator result,

Stri ctWeakOrderi ng bi nary pred);

Алгоритм создает теоретико-множественное объединение двух отсортированных интервалов в интервале result и возвращает конечный итератор полученного интервала. Ни один из исходных интервалов не обязан содержать только уникальные элементы, но если некоторое значение многократно встречается в обоих исходных интервалах, то в объединении будет присутствовать наибольшее из этих двух количеств.

Outputlterator set intersection(Inputlteratorl firstl,

Inputlteratorl lastl, InputIterator2 first2,

InputIterator2 last2, Outputlterator result); Outputlterator set intersection(Inputlteratorl firstl,

Inputlteratorl lastl, InputIterator2 first2.

InputIterator2 last2, Outputlterator result,

StrictWeakOrdering binary pred);

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

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

Outputlterator set difference(Inputlteratorl firstl.

Inputlteratorl lastl. InputIterator2 f1rst2.

InputIterator2 last2. Outputlterator result): Outputlterator set difference(Inputlteratorl firstl.

Inputlteratorl lastl. InputIterator2 f1rst2.

InputIterator2 last2. Outputlterator result.

StrictWeakOrdering binary pred):

Алгоритм строит в интервале result теоретико-множественную разность двух исходных интервалов и возвращает конечный итератор полученного интервала. В приемный интервал включаются только элементы, присутствующие в интервале [firstl,lastl), но отсутствующие в интервале [first2,last2). Ни один из исходных интервалов не обязан содержать только уникальные элементы, но если некоторое значение многократно встречается в обоих исходных интервалах (п в интервале 1 и m в интервале 2), то разность будет содержать max(n-ni,0) экземпляров этого значения.

Outputlterator set sy[mietric difference(Inputlteratorl firstl.

Inputlteratorl lastl. InputIterator2 first2.

InputIterator2 last2. Outputlterator result): Outputlterator set sy[mietr1c difference(InputIteratorl firstl,

Inputlteratorl lastl. InputIterator2 first2.

InputIterator2 last2. Outputlterator result,

StrictWeakOrdering b1nary pred):

Алгоритм заносит в интервал result:

все элементы интервала 1, отсутствующие в интервале 2;

все элементы интервала 2, отсутствующие в интервале 1.

Ни один из исходных интервалов не обязан содержать только уникальные элементы, но если некоторое значение многократно встречается в обоих исходных интервалах (п в интервале 1 и m в интервале 2), то разность будет содержать abs(n-ni) экземпляров этого значения. Возвращаемое значение представляет собой конечный итератор полученного интервала.

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

: C06:SetOperations.cpp

Теоретико-множественные операции с отсортированными интервалами

{L} Generators

#include <vector>

#include <algorithm>

#include PrintSequence.h

#include Generators.h

using namespace std;

int mainO { const int SZ = 30; char v[SZ + 1]. v2[SZ + 1];