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 );

Fusionne deux vues triées consécutives [first, middle) et [middle, last) en une seule vue triée [first, last).

Cette fonction de fusion est stable, ce qui signifie que pour les éléments équivalents dans les deux vues d'origine, les éléments de la première vue (en conservant leur ordre original) précèdent les éléments de la deuxième vue (en conservant leur ordre original).

Si l'une des conditions suivantes est satisfaite, le comportement est indéfini :

• [first, middle) ou [middle, last) n'est pas une vue valide.

Paramètres

Complexité

Étant donné \(\scriptsize N\)N comme std::distance(first, last) :

Exceptions

Les surcharges avec un paramètre template nommé ExecutionPolicy signalent les erreurs comme suit :

• Si l'exécution d'une fonction invoquée dans le cadre de l'algorithme lève une exception et que ExecutionPolicy est l'une des politiques standard, std::terminate est appelé. Pour toute autre ExecutionPolicy, le comportement est défini par l'implémentation.
• Si l'algorithme ne parvient pas à allouer de la mémoire, std::bad_alloc est levé.

Implémentation possible

Voir les implémentations dans libstdc++ et libc++.

Notes

Cette fonction tente d'allouer un tampon temporaire. Si l'allocation échoue, l'algorithme moins efficace est choisi.

Exemple

#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

Voir aussi