std::ranges:: merge, std::ranges:: merge_result

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

Une séquence est dite triée par rapport au comparateur comp si pour tout itérateur it pointant vers la séquence et tout entier non négatif n tel que it + n soit un itérateur valide pointant vers un élément de la séquence, std:: invoke ( comp, std:: invoke ( proj2, * ( it + n ) ) , std:: invoke ( proj1, * it ) ) ) s'évalue à false .

Le comportement n'est pas défini si la plage de destination chevauche l'une des plages d'entrée (les plages d'entrée peuvent se chevaucher mutuellement).

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

Les entités de type fonction décrites sur cette page sont des objets fonction d'algorithmes (informellement appelés niebloids ), c'est-à-dire :

• Les listes d'arguments de modèle explicites ne peuvent pas être spécifiées lors de l'appel de l'une d'entre elles.
• Aucune d'entre elles n'est visible pour la recherche dépendante des arguments .
• Lorsque l'une d'entre elles est trouvée par la recherche non qualifiée normale comme nom à gauche de l'opérateur d'appel de fonction, la recherche dépendante des arguments est inhibée.

Paramètres

Valeur de retour

{ last1, last2, result_last } , où result_last est la fin de la plage construite.

Complexité

Au plus N − 1 comparaisons et applications de chaque projection, où N = ranges:: distance ( first1, last1 ) + ranges:: distance ( first2, last12 ) .

Notes

Cet algorithme effectue une tâche similaire à celle de ranges:: 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 le traitement 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, ranges::merge produirait toutes les n + m occurrences tandis que ranges::set_union n'en produirait que max ( n, m ) . Ainsi, ranges::merge produit exactement N valeurs et ranges::set_union peut en produire moins.

Implémentation possible

struct merge_fn
{
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::input_iterator I2, std::sentinel_for<I2> S2,
             std::weakly_incrementable O, class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
    constexpr ranges::merge_result<I1, I2, O>
        operator()(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        for (; !(first1 == last1 or first2 == last2); ++result)
        {
            if (std::invoke(comp, std::invoke(proj2, *first2), std::invoke(proj1, *first1)))
                *result = *first2, ++first2;
            else
                *result = *first1, ++first1;
        }
        auto ret1{ranges::copy(std::move(first1), std::move(last1), std::move(result))};
        auto ret2{ranges::copy(std::move(first2), std::move(last2), std::move(ret1.out))};
        return {std::move(ret1.in), std::move(ret2.in), std::move(ret2.out)};
    }
    template<ranges::input_range R1, ranges::input_range R2, std::weakly_incrementable O,
             class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,
                            O, Comp, Proj1, Proj2>
    constexpr ranges::merge_result<ranges::borrowed_iterator_t<R1>,
                                   ranges::borrowed_iterator_t<R2>, O>
        operator()(R1&& r1, R2&& r2, O result, Comp comp = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), ranges::end(r1),
                       ranges::begin(r2), ranges::end(r2),
                       std::move(result), std::move(comp),
                       std::move(proj1), std::move(proj2));
    }
};
inline constexpr merge_fn merge {};

Exemple

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
void print(const auto& in1, const auto& in2, auto first, auto last)
{
    std::cout << "{ ";
    for (const auto& e : in1)
        std::cout << e << ' ';
    std::cout << "} +\n{ ";
    for (const auto& e : in2)
        std::cout << e << ' ';
    std::cout << "} =\n{ ";
    while (!(first == last))
        std::cout << *first++ << ' ';
    std::cout << "}\n\n";
}
int main()
{
    std::vector<int> in1, in2, out;
    in1 = {1, 2, 3, 4, 5};
    in2 = {3, 4, 5, 6, 7};
    out.resize(in1.size() + in2.size());
    const auto ret = std::ranges::merge(in1, in2, out.begin());
    print(in1, in2, out.begin(), ret.out);
    in1 = {1, 2, 3, 4, 5, 5, 5};
    in2 = {3, 4, 5, 6, 7};
    out.clear();
    out.reserve(in1.size() + in2.size());
    std::ranges::merge(in1, in2, std::back_inserter(out));
    print(in1, in2, out.cbegin(), out.cend());
}

{ 1 2 3 4 5 } +
{ 3 4 5 6 7 } =
{ 1 2 3 3 4 4 5 5 6 7 }
{ 1 2 3 4 5 5 5 } +
{ 3 4 5 6 7 } =
{ 1 2 3 3 4 4 5 5 5 5 6 7 }

Voir aussi