На этом шаге мы приведем общие сведения об алгоритмах, используемых для нахождения разности двух упорядоченных множеств элементов.
Для выполнения этой операции можно использовать следующие алгоритмы:
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() от других алгоритмов, комбинирующих элементы двух упорядоченных интервалов.
На следующем шаге мы рассмотрим пример использования алгоритмов слияния.
