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

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 = {} );

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 = {} );

template< class I1, class I2, class O >
using set_union_result = ranges::in_in_out_result<I1, I2, O>;

Construye una unión ordenada comenzando en result que consiste en el conjunto de elementos presentes en uno o ambos rangos de entrada ordenados [first1, last1) y [first2, last2).

Si algún elemento se encuentra m veces en [first1, last1) y n veces en [first2, last2), entonces todos los m elementos serán copiados desde [first1, last1) a result, preservando el orden, y luego exactamente max(n - m, 0) elementos serán copiados desde [first2, last2) a result, también preservando el orden.

El comportamiento no está definido si

• los rangos de entrada no están ordenados con respecto a comp y proj1 o proj2, respectivamente, o
• el rango resultante se superpone con alguno de los rangos de entrada.

Las entidades similares a funciones descritas en esta página son objetos de función de algoritmo (informalmente conocidos como niebloids), es decir:

• No se pueden especificar listas de argumentos de plantilla explícitas al llamar a cualquiera de ellas.
• Ninguna de ellas es visible a la búsqueda dependiente de argumentos.
• Cuando alguna de ellas se encuentra mediante búsqueda no calificada normal como el nombre a la izquierda del operador de llamada a función, búsqueda dependiente de argumentos se inhibe.

Parámetros

Valor de retorno

{ last1, last2, result_last } , donde result_last es el final del rango construido.

Complejidad

Como máximo \(\scriptsize 2\cdot(N_1+N_2)-1\) 2·(N 1 +N 2 )-1 comparaciones y aplicaciones de cada proyección, donde \(\scriptsize N_1\) N 1 y \(\scriptsize N_2\) N 2 son ranges:: distance ( first1, last1 ) y ranges:: distance ( first2, last2 ) , respectivamente.

Notas

Este algoritmo realiza una tarea similar a la que hace ranges::merge . Ambos consumen dos rangos de entrada ordenados y producen una salida ordenada con elementos de ambas entradas. La diferencia entre estos dos algoritmos está en el manejo de valores de ambos rangos de entrada que son equivalentes al comparar (ver notas sobre LessThanComparable ). Si cualquier valor equivalente apareció n veces en el primer rango y m veces en el segundo, ranges::merge produciría todas las n + m ocurrencias, mientras que ranges::set_union produciría solo std:: max ( n, m ) . Por lo tanto, ranges::merge produce exactamente \(\scriptsize (N_1+N_2)\) (N 1 +N 2 ) valores y ranges::set_union puede producir menos.

Implementación posible

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 {};

Ejemplo

#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 }

Véase también