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

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

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

  OutputIterator
  set_intersection (InputIterator source1Beg, InputIterator source1End,
                    InputIterator source2Beg, InputIterator source2End,
                    OutputIterator destBeg)

  set_intersection (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_intersection() для этих интервалов будет получен следующий интервал:

 2 2 6 9

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

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

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

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

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

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

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

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

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

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



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

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