std::ranges::set_union, std::ranges::set_union_result

Defined in header `<algorithm>`
Call signature
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_union_result<I1, I2, O> set_union( I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(1)	(since 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_union_result<ranges::borrowed_iterator_t<R1>, ranges::borrowed_iterator_t<R2>, O> set_union( R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(2)	(since C++20)
Helper types
template< class I1, class I2, class O > using set_union_result = ranges::in_in_out_result<I1, I2, O>;	(3)	(since C++20)

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

Если какой-либо элемент встречается m раз в [first1, last1) и n раз в [first2, last2), то все m элементов будут скопированы из [first1, last1) в result, сохраняя порядок, а затем ровно max(n - m, 0) элементов будут скопированы из [first2, last2) в 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.

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

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

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

Параметры

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

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

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

Сложность

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

Примечания

Этот алгоритм выполняет задачу, аналогичную ranges::merge. Оба потребляют два отсортированных входных диапазона и производят отсортированный выходной диапазон с элементами из обоих входных диапазонов. Разница между этими двумя алгоритмами заключается в обработке значений из обоих входных диапазонов, которые сравниваются как эквивалентные (см. примечания к LessThanComparable). Если какие-либо эквивалентные значения появляются n раз в первом диапазоне и m раз во втором, ranges::merge выведет все n+m появления, тогда как ranges::set_union выведет только std::max(n, m). Таким образом, ranges::merge выводит ровно \(N_1+N_2\) значений, а ranges::set_union может произвести меньше.

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

struct set_union_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
    {
        for (; !(first1 == last1 or first2 == last2); ++result)
        {
            if (std::invoke(comp, std::invoke(proj1, *first1), std::invoke(proj2, *first2)))
            {
                *result = *first1;
                ++first1;
            }
            else if (std::invoke(comp, std::invoke(proj2, *first2),
                                       std::invoke(proj1, *first1)))
            {
                *result = *first2;
                ++first2;
            }
            else
            {
                *result = *first1;
                ++first1;
                ++first2;
            }
        }
        auto res1 = ranges::copy(std::move(first1), std::move(last1), std::move(result));
        auto res2 = ranges::copy(std::move(first2), std::move(last2), std::move(res1.out));
        return {std::move(res1.in), std::move(res2.in), std::move(res2.out)};
    }
 
    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_union_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_union_fn set_union {};

Пример

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
void print(const auto& in1, const auto& in2, auto first, auto last)
{
    std::cout << "{ ";
    for (const auto& e : in1)
        std::cout << e << ' ';
    std::cout << "} ∪ { ";
    for (const auto& e : in2)
        std::cout << e << ' ';
    std::cout << "} =\n{ ";
    while (!(first == last))
        std::cout << *first++ << ' ';
    std::cout << "}\n\n";
}
 
int main()
{
    std::vector<int> in1, in2, out;
 
    in1 = {1, 2, 3, 4, 5};
    in2 = {      3, 4, 5, 6, 7};
    out.resize(in1.size() + in2.size());
    const auto ret = std::ranges::set_union(in1, in2, out.begin());
    print(in1, in2, out.begin(), ret.out);
 
    in1 = {1, 2, 3, 4, 5, 5, 5};
    in2 = {      3, 4, 5, 6, 7};
    out.clear();
    out.reserve(in1.size() + in2.size());
    std::ranges::set_union(in1, in2, std::back_inserter(out));
    print(in1, in2, out.cbegin(), out.cend());
}

Вывод:

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

См. также

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

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