На этом шаге мы приведем общие сведения об алгоритмах, используемых для объединения двух упорядоченных множеств элементов.
Для выполнения этой операции можно использовать следующие алгоритмы:
OutputIterator
set_union (InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg, InputIterator source2End,
OutputIterator destBeg)
set_union (InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg, InputIterator source2End,
OutputIterator destBeg, BinaryPredicate op)
Обе формы комбинируют элементы упорядоченных исходных интервалов [source1Beg,source1End) и [source2Beg,source2End) таким образом, что приемный интервал [destBeg,...) содержит все элементы, присутствующие в первом интервале, во втором интервале или в обоих интервалах сразу. Например, рассмотрим два интервала:
1 2 2 4 6 7 7 9 2 2 2 3 6 6 8 9
В результате вызова алгоритма set_union() для этих интервалов будет получен следующий интервал:
1 2 2 2 3 4 6 6 7 7 8 9
В приемном интервале элементы следуют в порядке сортировки.
Элементы, входящие в оба интервала, включаются в объединение только в одном экземпляре. Тем не менее приемный интервал может содержать дубликаты, если соответствующий элемент дублируется в одном из исходных интервалов. Количество элементов с одинаковыми значениями в приемном интервале равно их максимальному количеству в двух исходных интервалах.
Обе формы возвращают позицию за последним скопированным элементом в приемном интервале (то есть позицию первого элемента, который не был перезаписан).
В необязательном параметре ор передается бинарный предикат, определяющий критерий сортировки: op(elem1,elem2).
Алгоритмы не изменяют состояние исходных интервалов.
Перед вызовом интервалы должны быть упорядочены по соответствующему критерию сортировки.
Перед вызовом необходимо убедиться в том, что приемный интервал имеет достаточный размер, или использовать итераторы вставки.
Приемный интервал не должен перекрываться с исходными интервалами.
Чтобы без удаления элементов включить в приемный интервал все элементы, присутствующие в обоих исходных интервалах, используйте алгоритм merge().
Сложность линейная (не более 2*(numberOfElements1+numberOfElements2)-l сравнений).
Пример использования алгоритма set_union() приведен на 319 шаге. В этом примере также продемонстрированы отличия алгоритма set_union() от других алгоритмов, комбинирующих элементы двух упорядоченных интервалов.
На следующем шаге мы рассмотрим пересечение двух упорядоченных множеств элементов.
