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