std::set_union

template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_union( InputIt1 first1, InputIt1 last1,
                    InputIt2 first2, InputIt2 last2,
                    OutputIt d_first );

template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2, class ForwardIt3 >
ForwardIt3 set_union( ExecutionPolicy&& policy,
                      ForwardIt1 first1, ForwardIt1 last1,
                      ForwardIt2 first2, ForwardIt2 last2,
                      ForwardIt3 d_first );

template< class InputIt1, class InputIt2,
          class OutputIt, class Compare >
OutputIt set_union( InputIt1 first1, InputIt1 last1,
                    InputIt2 first2, InputIt2 last2,
                    OutputIt d_first, Compare comp );

template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2,
          class ForwardIt3, class Compare >
ForwardIt3 set_union( ExecutionPolicy&& policy,
                      ForwardIt1 first1, ForwardIt1 last1,
                      ForwardIt2 first2, ForwardIt2 last2,
                      ForwardIt3 d_first, Compare comp );

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

Si [first1, last1) contiene m elementos que son equivalentes entre sí y [first2, last2) contiene n elementos que son equivalentes a ellos, entonces todos los m elementos se copiarán de [first1, last1) al rango de salida, preservando el orden, y luego los últimos std::max(n - m, 0) elementos se copiarán de [first2, last2) al rango de salida, también preservando el orden.

Si el rango de salida se superpone con [first1, last1) o [first2, last2), el comportamiento no está definido.

Parámetros

Valor de retorno

Iterador más allá del final del rango construido.

Complejidad

Dado \(\scriptsize N_1\) N 1 como std:: distance ( first1, last1 ) y \(\scriptsize N_2\) N 2 como std:: distance ( first2, last2 ) :

Excepciones

Las sobrecargas con un parámetro de plantilla llamado ExecutionPolicy reportan errores de la siguiente manera:

• Si la ejecución de una función invocada como parte del algoritmo lanza una excepción y ExecutionPolicy es uno de los standard policies , std::terminate es llamado. Para cualquier otro ExecutionPolicy , el comportamiento está definido por la implementación.
• Si el algoritmo falla al asignar memoria, std::bad_alloc es lanzado.

Implementación posible

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_union(InputIt1 first1, InputIt1 last1,
                   InputIt2 first2, InputIt2 last2, OutputIt d_first)
{
    for (; first1 != last1; ++d_first)
    {
        if (first2 == last2)
            return std::copy(first1, last1, d_first);
        if (*first2 < *first1)
            *d_first = *first2++;
        else
        {
            *d_first = *first1;
            if (!(*first1 < *first2))
                ++first2;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt set_union(InputIt1 first1, InputIt1 last1,
                   InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp)
{
    for (; first1 != last1; ++d_first)
    {
        if (first2 == last2)
            // Rango 2 finalizado, incluir el resto del rango 1:
            return std::copy(first1, last1, d_first);
        if (comp(*first2, *first1))
            *d_first = *first2++;
        else
        {
            *d_first = *first1;
            if (!comp(*first1, *first2)) // Equivalente => no es necesario incluir *first2.
                ++first2;
            ++first1;
        }
    }
    // Rango 1 finalizado, incluir el resto del rango 2:
    return std::copy(first2, last2, d_first);
}

Notas

Este algoritmo realiza una tarea similar a la que std::merge realiza. 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 comparan equivalentes (ver notas sobre LessThanComparable ). Si cualquier valor equivalente apareció n veces en el primer rango y m veces en el segundo, std::merge produciría todas las n + m ocurrencias mientras que std::set_union produciría solo std:: max ( n, m ) . Por lo tanto, std::merge produce exactamente std:: distance ( first1, last1 ) + std:: distance ( first2, last2 ) valores y std::set_union puede producir menos.

Ejemplo

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
void println(const std::vector<int>& v)
{
    for (int i : v)
        std::cout << i << ' ';
    std::cout << '\n';
}
int main()
{
    std::vector<int> v1, v2, dest;
    v1 = {1, 2, 3, 4, 5};
    v2 = {3, 4, 5, 6, 7};
    std::set_union(v1.cbegin(), v1.cend(),
                   v2.cbegin(), v2.cend(),
                   std::back_inserter(dest));
    println(dest);
    dest.clear();
    v1 = {1, 2, 3, 4, 5, 5, 5};
    v2 = {3, 4, 5, 6, 7};
    std::set_union(v1.cbegin(), v1.cend(),
                   v2.cbegin(), v2.cend(),
                   std::back_inserter(dest));
    println(dest);
}

1 2 3 4 5 6 7 
1 2 3 4 5 5 5 6 7

Informes de defectos

Los siguientes informes de defectos que modifican el comportamiento se aplicaron retroactivamente a los estándares de C++ publicados anteriormente.

Véase también