std::set_intersection

Определено в заголовке `<algorithm>`
	(1)
template< class InputIt1, class InputIt2, class OutputIt > OutputIt set_intersection( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );		(до C++20)
template< class InputIt1, class InputIt2, class OutputIt > constexpr OutputIt set_intersection( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );		(с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 > ForwardIt3 set_intersection( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first );	(2)	(с C++17)
	(3)
template< class InputIt1, class InputIt2, class OutputIt, class Compare > OutputIt set_intersection( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );		(до C++20)
template< class InputIt1, class InputIt2, class OutputIt, class Compare > constexpr OutputIt set_intersection( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );		(с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3, class Compare > ForwardIt3 set_intersection( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first, Compare comp );	(4)	(с C++17)

Создаёт отсортированный диапазон, начинающийся в d_first , содержащий элементы, которые присутствуют в обоих отсортированных диапазонах [first1, last1) и [first2, last2).

Если [first1, last1) содержит m элементов, эквивалентных друг другу, и [first2, last2) содержит n элементов, эквивалентных им, первые std::min(m, n) элементов будут скопированы из [first1, last1) в диапазон вывода, сохраняя порядок.

1) Элементы сравниваются с использованием operator< , и диапазоны должны быть отсортированы относительно этого же порядка.

3) Элементы сравниваются с использованием заданной бинарной функции сравнения comp , и диапазоны должны быть отсортированы относительно этого же порядка.

2,4) Аналогично (1,3), но выполняется согласно policy. Эти перегрузки не участвуют в разрешении перегрузки, если

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>` является `true`.	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` является `true`.	(с C++20)

Если какой-либо из входных диапазонов не отсортирован (используя operator< или comp соответственно) или перекрывается с диапазоном вывода, поведение не определено.

Параметры

first1, last1	-	первый диапазон элементов для проверки
first2, last2	-	второй диапазон элементов для проверки
d_first	-	начало диапазона вывода
policy	-	используемая политика выполнения. Подробнее см. политика выполнения.
comp	-	объект-функция сравнения (т.е. объект, удовлетворяющий требованиям Compare), возвращающий `true` , если первый аргумент меньше (т.е. предшествует) второму. Подпись функции сравнения должна быть эквивалентна следующей: `bool cmp(const Type1& a, const Type2& b);` Хотя подпись не обязательно должна содержать const&, функция не должна изменять переданные ей объекты и должна быть способна принимать все значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (поэтому `Type1&` запрещено, а также `Type1` , за исключением случаев, когда для `Type1` перемещение эквивалентно копированию(с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объекты типов InputIt1 и InputIt2 можно было дереферировать и затем неявно преобразовать в оба типа Type1 и Type2.
Требования к типу
-`InputIt1, InputIt2` должен удовлетворять требованиям LegacyInputIterator.
-`OutputIt` должен удовлетворять требованиям LegacyOutputIterator.
-`ForwardIt1, ForwardIt2, ForwardIt3` должен удовлетворять требованиям LegacyForwardIterator.

Возвращаемое значение

Итератор после конца построенного диапазона.

Сложность

Даны M и N как std::distance(first1, last1) и std::distance(first2, last2) соответственно:

1,2) не более 2·(M + N) - 1 сравнений с использованием operator<.

3,4) не более 2·(M + N) - 1 применений предиката p.

Исключения

Перегрузки с параметром шаблона под названием ExecutionPolicy сообщают об ошибках следующим образом:

Если во время выполнения функции, вызванной как часть алгоритма, возникает исключение, и ExecutionPolicy является одной из стандартных политик, вызывается std::terminate. Для любой другой ExecutionPolicy, поведение определяется реализацией.
Если алгоритм не может выделить память, выбрасывается std::bad_alloc .

Возможная реализация

set_intersection (1)
template<class InputIt1, class InputIt2, class OutputIt> OutputIt set_intersection(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first) { while (first1 != last1 && first2 != last2) { if (first1 < first2) ++first1; else { if (!(first2 < first1)) d_first++ = first1++; // first1 and first2 are equivalent. ++first2; } } return d_first; }
set_intersection (3)
template<class InputIt1, class InputIt2, class OutputIt, class Compare> OutputIt set_intersection(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp) { while (first1 != last1 && first2 != last2) { if (comp(first1, first2)) ++first1; else { if (!comp(first2, first1)) d_first++ = first1++; // first1 and first2 are equivalent. ++first2; } } return d_first; }

set_intersection (1)

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2, OutputIt d_first)
{
    while (first1 != last1 && first2 != last2)
    {
        if (*first1 < *first2)
            ++first1;
        else
        {
            if (!(*first2 < *first1))
                *d_first++ = *first1++; // *first1 and *first2 are equivalent.
            ++first2;
        }
    }
    return d_first;
}

set_intersection (3)

template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp)
{
    while (first1 != last1 && first2 != last2)
    {
        if (comp(*first1, *first2))
            ++first1;
        else
        {
            if (!comp(*first2, *first1))
                *d_first++ = *first1++; // *first1 and *first2 are equivalent.
            ++first2;
        }
    }
    return d_first;
}

Пример

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
int main()
{
    std::vector<int> v1{7, 2, 3, 4, 5, 6, 7, 8};
    std::vector<int> v2{5, 7, 9, 7};
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
 
    std::vector<int> v_intersection;
    std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(),
                          std::back_inserter(v_intersection));
 
    for (int n : v_intersection)
        std::cout << n << ' ';
    std::cout << '\n';
}

Вывод:

5 7 7

Отчёты об ошибках

Следующие изменения поведения, связанные с отчётами об ошибках, были применены ретроактивно к ранее опубликованным стандартам C++.

DR	Применяется к	Поведение, как опубликовано	Правильное поведение
LWG 291	C++98	не было указано, как обрабатывать эквивалентные элементы в входных диапазонах	указано

См. также

set_union	вычисляет объединение двух множеств (шаблон функции)
ranges::set_intersection (C++20)	вычисляет пересечение двух множеств (неблоковый)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/set_intersection