Алгоритмы упорядоченных интервалов. Объединение двух упорядоченных множеств элементов

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

   
Для выполнения этой операции можно использовать следующие алгоритмы:

  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() от других алгоритмов, комбинирующих элементы двух упорядоченных
интервалов.

   
На следующем шаге мы рассмотрим пересечение двух упорядоченных множеств элементов.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий