Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

CKTIS / C++

std::merge — fusión estable de rangos ordenados

std::merge, de <algorithm>, copia dos rangos ordenados en un rango de salida independiente. Conserva los duplicados y la estabilidad, y devuelve un iterador situado después del último elemento escrito.

Versión: C++23; repository compiler flag, production runtime not attested

Sintaxis

#include <algorithm>
std::merge(first1, last1, first2, last2, result);
std::merge(first1, last1, first2, last2, result, comp);

std::merge combina [first1, last1) y [first2, last2), escribiendo todos los elementos a partir de result. Ambas entradas deben estar ya ordenadas según el mismo criterio: ascendente de forma predeterminada o según el orden especificado por comp. El comparador debe definir un orden débil estricto. Las entradas desordenadas incumplen las precondiciones del algoritmo; la función no las ordena primero.

La fusión es estable: conserva el orden de los elementos dentro de cada entrada, y los elementos con claves equivalentes del primer rango preceden a los del segundo. Equivalencia significa que ni comp(a, b) ni comp(b, a) es verdadero. Los duplicados permanecen en la salida.

El rango de salida no debe solaparse con ninguno de los rangos de entrada. Reserva espacio para la suma de sus longitudes o usa un iterador de inserción adecuado. Llamar únicamente a reserve() en un vector no crea elementos en los que se pueda escribir mediante begin(). El iterador devuelto apunta a la posición siguiente al último elemento escrito.

Para las sobrecargas tratadas aquí, sin una política de ejecución, el trabajo es lineal respecto al número total de elementos N, con un máximo de N - 1 comparaciones cuando N > 0. No confundas esta función con std::inplace_merge, que combina dos subrangos ordenados adyacentes dentro del mismo rango. El ejemplo usa sintaxis compatible con C++23; el borrador de trabajo citado se actualiza y también puede incluir extensiones posteriores.

Ejemplos

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    const std::array<int, 3> a{1, 3, 5};
    const std::array<int, 3> b{2, 3, 6};
    std::array<int, 6> result{};

    const auto end = std::merge(a.begin(), a.end(),
                                b.begin(), b.end(), result.begin());

    for (auto it = result.begin(); it != end; ++it) {
        if (it != result.begin()) {
            std::cout << ' ';
        }
        std::cout << *it;
    }
    std::cout << '\n';
}

Resultado

1 2 3 3 5 6

El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.

Fuentes