std:: inplace_merge

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

Cette fonction de fusion est stable, ce qui signifie que pour les éléments équivalents dans les deux plages d'origine, les éléments de la première plage (préservant leur ordre d'origine) précèdent les éléments de la seconde plage (préservant leur ordre d'origine).

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

• [ first , middle ) ou [ middle , last ) n'est pas un intervalle valide .

Paramètres

Complexité

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

Exceptions

Les surcharges avec un paramètre de modèle 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 fait partie des politiques standard , std::terminate est appelé. Pour tout 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