std::ranges::set_intersection, std::ranges::set_intersection_result

Определено в заголовке `<algorithm>`
Подпись вызова
template< std::input_iterator I1, std::sentinel_for<I1> S1, std::input_iterator I2, std::sentinel_for<I2> S2, std::weakly_incrementable O, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr set_intersection_result<I1, I2, O> set_intersection( I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(1)	(с C++20)
template< ranges::input_range R1, ranges::input_range R2, std::weakly_incrementable O, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr set_intersection_result<ranges::borrowed_iterator_t<R1>, ranges::borrowed_iterator_t<R2>, O> set_intersection( R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(2)	(с C++20)
Вспомогательные типы
template< class I1, class I2, class O > using set_intersection_result = ranges::in_in_out_result<I1, I2, O>;	(3)	(с C++20)

Создаёт отсортированный диапазон, начинающийся с result , состоящий из элементов, присутствующих в обоих отсортированных входных диапазонах [first1, last1) и [first2, last2). Если некоторый элемент встречается m раз в [first1, last1) и n раз в [first2, last2), то первые min(m, n) элементов будут скопированы из первого диапазона в result. Порядок эквивалентных элементов сохраняется.

Поведение не определено, если

входные диапазоны не отсортированы относительно comp и proj1 или proj2, соответственно, или
результирующий диапазон перекрывается с одним из входных диапазонов.

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

2) Аналогично (1), но использует r1 в качестве первого диапазона и r2 в качестве второго диапазона, как если бы ranges::begin(r1) использовался как first1, ranges::end(r1) как last1, ranges::begin(r2) как first2, и ranges::end(r2) как last2.

Функциональные сущности, описанные на этой странице, являются ниблоидами, то есть:

Явные списки шаблонных аргументов не могут быть указаны при вызове любого из них.
Ни один из них не виден для поиска зависимого от аргументов.
Когда любой из них найден обычным поиском без квалификации в качестве имени слева от оператора вызова функции, поиск зависимый от аргументов подавляется.

На практике они могут быть реализованы как объекты-функции или с помощью специальных расширений компилятора.

Параметры

first1, last1	-	пара итератор-граница, обозначающая первый входной отсортированный диапазон
first2, last2	-	пара итератор-граница, обозначающая второй входной отсортированный диапазон
r1	-	первый отсортированный входной диапазон
r2	-	второй отсортированный входной диапазон
result	-	начало выходного диапазона
comp	-	сравнение для применения к спроектированным элементам
proj1	-	проектирование для применения к элементам в первом диапазоне
proj2	-	проектирование для применения к элементам во втором диапазоне

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

{last1, last2, result_last}, где result_last — конец созданного диапазона.

Сложность

Максимум \(\scriptsize 2\cdot(N_1+N_2)-1\)2·(N₁+N₂)-1 сравнений и применений каждого проектирования, где \(\scriptsize N_1\)N₁ и \(\scriptsize N_2\)N₂ — ranges::distance(first1, last1) и ranges::distance(first2, last2), соответственно.

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

struct set_intersection_fn
{
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::input_iterator I2, std::sentinel_for<I2> S2,
             std::weakly_incrementable O, class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
    constexpr ranges::set_union_result<I1, I2, O>
        operator()(I1 first1, S1 last1, I2 first2, S2 last2,
                   O result, Comp comp = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        while (!(first1 == last1 or first2 == last2))
        {
            if (std::invoke(comp, std::invoke(proj1, *first1),
                                  std::invoke(proj2, *first2)))
                ++first1;
            else if (std::invoke(comp, std::invoke(proj2, *first2),
                                       std::invoke(proj1, *first1)))
                ++first2;
            else
                *result = *first1, ++first1, ++first2, ++result;
        }
        return {ranges::next(std::move(first1), std::move(last1)),
                ranges::next(std::move(first2), std::move(last2)),
                std::move(result)};
    }
 
    template<ranges::input_range R1, ranges::input_range R2,
             std::weakly_incrementable O, class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,
                            O, Comp, Proj1, Proj2>
    constexpr ranges::set_intersection_result<ranges::borrowed_iterator_t<R1>,
                                              ranges::borrowed_iterator_t<R2>, O>
        operator()(R1&& r1, R2&& r2, O result, Comp comp = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), ranges::end(r1),
                       ranges::begin(r2), ranges::end(r2),
                       std::move(result), std::move(comp),
                       std::move(proj1), std::move(proj2));
    }
};
 
inline constexpr set_intersection_fn set_intersection {};

Пример

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
void print(const auto& v, const auto& rem)
{
    std::cout << "{ ";
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '}' << rem;
}
 
int main()
{
    const auto in1 = {1, 2, 2, 3, 4, 5, 6};
    const auto in2 = {2, 2, 3, 3, 5, 7};
    std::vector<int> out {};
 
    std::ranges::set_intersection(in1, in2, std::back_inserter(out));
 
    print(in1, " ∩ "), print(in2, " = "), print(out, "\n");
}

Вывод:

{ 1 2 2 3 4 5 6 } ∩ { 2 2 3 3 5 7 } = { 2 2 3 5 }

См. также

ranges::set_union (C++20)	вычисляет объединение двух множеств (ниблоид)
ranges::set_difference (C++20)	вычисляет разность двух множеств (ниблоид)
ranges::set_symmetric_difference (C++20)	вычисляет симметрическую разность двух множеств (ниблоид)
ranges::includes (C++20)	возвращает `true` , если одна последовательность является подпоследовательностью другой (ниблоид)
set_intersection	вычисляет пересечение двух множеств (шаблон функции)

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