std:: merge

Combina dos rangos ordenados [ first1 , last1 ) y [ first2 , last2 ) en un único rango ordenado que comienza en d_first .

Esta función de fusión es estable, lo que significa que para elementos equivalentes en los dos rangos originales, los elementos del primer rango (preservando su orden original) preceden a los elementos del segundo rango (preservando su orden original).

Si el rango de salida se superpone con [ first1 , last1 ) o [ first2 , last2 ) , el comportamiento es indefinido.

Parámetros

Valor de retorno

Un iterador de salida al elemento después del último elemento copiado.

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

Véase también las implementaciones en libstdc++ y libc++ .

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt merge(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;
            ++first2;
        }
        else
        {
            *d_first = *first1;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

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

Notas

Este algoritmo realiza una tarea similar a la que hace std:: set_union . 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 se comparan como 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 <functional>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>
auto print = [](const auto rem, const auto& v)
{
    std::cout << rem;
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
};
int main()
{
    // llenar los vectores con números aleatorios
    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_int_distribution<> dis(0, 9);
    std::vector<int> v1(10), v2(10);
    std::generate(v1.begin(), v1.end(), std::bind(dis, std::ref(mt)));
    std::generate(v2.begin(), v2.end(), std::bind(dis, std::ref(mt)));
    print("Originalmente:\nv1: ", v1);
    print("v2: ", v2);
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    print("Después de ordenar:\nv1: ", v1);
    print("v2: ", v2);
    // fusionar
    std::vector<int> dst;
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));
    print("Después de fusionar:\ndst: ", dst);
}

Originalmente:
v1: 2 6 5 7 4 2 2 6 7 0
v2: 8 3 2 5 0 1 9 6 5 0
Después de ordenar:
v1: 0 2 2 2 4 5 6 6 7 7
v2: 0 0 1 2 3 5 5 6 8 9
Después de fusionar:
dst: 0 0 0 1 2 2 2 2 3 4 5 5 5 6 6 6 7 7 8 9

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