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

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 merge_result<I1, I2, O>
    merge( I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {},
           Proj1 proj1 = {}, Proj2 proj2 = {} );

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 merge_result<ranges::borrowed_iterator_t<R1>,
                       ranges::borrowed_iterator_t<R2>, O>
    merge( R1&& r1, R2&& r2, O result, Comp comp = {},
           Proj1 proj1 = {}, Proj2 proj2 = {} );

template< class I1, class I2, class O >
using merge_result = ranges::in_in_out_result<I1, I2, O>;

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 est indéfini si la plage de destination chevauche l'une des plages d'entrée (les plages d'entrée peuvent se chevaucher entre elles).

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

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

• Les listes explicites d'arguments template ne peuvent pas être spécifiées lors de l'appel de l'une d'entre elles.
• Aucune d'entre elles n'est visible par recherche dépendante des arguments.
• Lorsque l'une d'entre elles est trouvée par recherche normale non qualifiée comme le 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