std:: set_union

Construit une union triée commençant à d_first constituée de l'ensemble des éléments présents dans un ou les deux intervalles triés [ first1 , last1 ) et [ first2 , last2 ) .

Si [ first1 , last1 ) contient m éléments équivalents entre eux et [ first2 , last2 ) contient n éléments qui leur sont équivalents, alors tous les m éléments seront copiés depuis [ first1 , last1 ) vers la plage de sortie, en préservant l'ordre, et ensuite les std:: max ( n - m, 0 ) éléments finaux seront copiés depuis [ first2 , last2 ) vers la plage de sortie, en préservant également l'ordre.

Si la plage de sortie chevauche [ first1 , last1 ) ou [ first2 , last2 ) , le comportement est indéfini.

Paramètres

Valeur de retour

Itérateur après la fin de la plage construite.

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

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_union(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++;
        else
        {
            *d_first = *first1;
            if (!(*first1 < *first2))
                ++first2;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt set_union(InputIt1 first1, InputIt1 last1,
                   InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp)
{
    for (; first1 != last1; ++d_first)
    {
        if (first2 == last2)
            // Plage 2 terminée, inclure le reste de la plage 1 :
            return std::copy(first1, last1, d_first);
        if (comp(*first2, *first1))
            *d_first = *first2++;
        else
        {
            *d_first = *first1;
            if (!comp(*first1, *first2)) // Équivalent => pas besoin d'inclure *first2.
                ++first2;
            ++first1;
        }
    }
    // Plage 1 terminée, inclure le reste de la plage 2 :
    return std::copy(first2, last2, d_first);
}

Notes

Cet algorithme effectue une tâche similaire à celle de std::merge . 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 en comparaison (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 <iostream>
#include <iterator>
#include <vector>
void println(const std::vector<int>& v)
{
    for (int i : v)
        std::cout << i << ' ';
    std::cout << '\n';
}
int main()
{
    std::vector<int> v1, v2, dest;
    v1 = {1, 2, 3, 4, 5};
    v2 = {3, 4, 5, 6, 7};
    std::set_union(v1.cbegin(), v1.cend(),
                   v2.cbegin(), v2.cend(),
                   std::back_inserter(dest));
    println(dest);
    dest.clear();
    v1 = {1, 2, 3, 4, 5, 5, 5};
    v2 = {3, 4, 5, 6, 7};
    std::set_union(v1.cbegin(), v1.cend(),
                   v2.cbegin(), v2.cend(),
                   std::back_inserter(dest));
    println(dest);
}

1 2 3 4 5 6 7 
1 2 3 4 5 5 5 6 7

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