std:: merge

Fusionne deux plages triées [ first1 , last1 ) et [ first2 , last2 ) en une seule plage triée commençant à d_first .

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 la plage de sortie chevauche [ first1 , last1 ) ou [ first2 , last2 ) , le comportement est indéfini.

Paramètres

Valeur de retour

Un itérateur de sortie vers l'élément situé après le dernier élément copié.

Complexité

Soit \(\scriptsize N_1\) N 1 défini comme std:: distance ( first1, last1 ) et \(\scriptsize N_2\) N 2 défini comme std:: distance ( first2, last2 ) :

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 également les implémentations dans libstdc++ et 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);
}

Notes

Cet algorithme effectue une tâche similaire à celle de std:: set_union . Les deux consomment deux plages d'entrée triées et produisent une sortie triée avec des éléments des deux entrées. La différence entre ces deux algorithmes réside dans la gestion des valeurs des deux plages d'entrée qui sont équivalentes (voir les notes sur LessThanComparable ). Si des valeurs équivalentes apparaissaient n fois dans la première plage et m fois dans la seconde, std::merge produirait toutes les n + m occurrences tandis que std::set_union ne produirait que std:: max ( n, m ) . Ainsi, std::merge produit exactement std:: distance ( first1, last1 ) + std:: distance ( first2, last2 ) valeurs et std::set_union peut en produire moins.

Exemple

#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()
{
    // remplir les vecteurs avec des nombres aléatoires
    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("Originalement :\nv1 : ", v1);
    print("v2 : ", v2);
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    print("Après tri :\nv1 : ", v1);
    print("v2 : ", v2);
    // fusion
    std::vector<int> dst;
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));
    print("Après fusion :\ndst : ", dst);
}

Originalement :
v1 : 2 6 5 7 4 2 2 6 7 0
v2 : 8 3 2 5 0 1 9 6 5 0
Après tri :
v1 : 0 2 2 2 4 5 6 6 7 7
v2 : 0 0 1 2 3 5 5 6 8 9
Après fusion :
dst : 0 0 0 1 2 2 2 2 3 4 5 5 5 6 6 6 7 7 8 9

Rapports de défauts

Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.

Voir aussi