std::inplace_merge

template< class BidirIt >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );

template< class ExecutionPolicy, class BidirIt >
void inplace_merge( ExecutionPolicy&& policy,
                    BidirIt first, BidirIt middle, BidirIt last );

template< class BidirIt, class Compare >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last,
                    Compare comp );

template< class ExecutionPolicy, class BidirIt, class Compare >
void inplace_merge( ExecutionPolicy&& policy,
                    BidirIt first, BidirIt middle, BidirIt last,
                    Compare comp );

Fusiona dos rangos ordenados consecutivos [first, middle) y [middle, last) en un rango ordenado [first, last).

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 se cumple alguna de las siguientes condiciones, el comportamiento es indefinido:

• [first, middle) o [middle, last) no es un rango válido.

Parámetros

Complejidad

Dado \(\scriptsize N\)N como std::distance(first, last):

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 una de las políticas estándar, se llama a std::terminate. Para cualquier otro ExecutionPolicy, el comportamiento está definido por la implementación.
• Si el algoritmo no puede asignar memoria, se lanza std::bad_alloc.

Posible implementación

Véanse las implementaciones en libstdc++ y libc++.

Notas

Esta función intenta asignar un búfer temporal. Si la asignación falla, se elige el algoritmo menos eficiente.

Ejemplo

#include <algorithm>
#include <iostream>
#include <vector>

template<class Iter>
void merge_sort(Iter first, Iter last)
{
    if (last - first > 1)
    {
        Iter middle = first + (last - first) / 2;
        merge_sort(first, middle);
        merge_sort(middle, last);
        std::inplace_merge(first, middle, last);
    }
}

int main()
{
    std::vector<int> v{8, 2, -2, 0, 11, 11, 1, 7, 3};
    merge_sort(v.begin(), v.end());
    for (const auto& n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

-2 0 1 2 3 7 8 11 11

Véase también