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

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

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

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

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

 1 4 7 7

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

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

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

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

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

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

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

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

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

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

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



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

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