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>;

Combina dos rangos ordenados [[first1, last1) y [first2, last2) en un rango ordenado que comienza en result.

Se dice que una secuencia está ordenada con respecto al comparador comp si para cualquier iterador it que apunte a la secuencia y cualquier entero no negativo n tal que it + n sea un iterador válido apuntando a un elemento de la secuencia, std::invoke(comp, std::invoke(proj2, *(it + n)), std::invoke(proj1, *it))) se evalúa a false.

El comportamiento no está definido si el rango de destino se superpone con cualquiera de los rangos de entrada (los rangos de entrada pueden superponerse entre sí).

Esta función de mezcla es estable, lo que significa que para elementos equivalentes en los dos rangos originales, los elementos del primer rango (conservando su orden original) preceden a los elementos del segundo rango (conservando su orden original).

Las entidades similares a funciones descritas en esta página son objetos de función de algoritmo (conocidos informalmente como niebloids), esto es:

• No se pueden especificar listas de argumentos de plantilla explícitas al llamar a cualquiera de ellos.
• Ninguno de ellos es visible mediante búsqueda dependiente de argumentos.
• Cuando alguno de ellos es encontrado mediante búsqueda no calificada normal como el nombre a la izquierda del operador de llamada a función, la búsqueda dependiente de argumentos se inhibe.

Parámetros

Valor de retorno

{ last1, last2, result_last } , donde result_last es el final del rango construido.

Complejidad

Como máximo N − 1 comparaciones y aplicaciones de cada proyección, donde N = ranges:: distance ( first1, last1 ) + ranges:: distance ( first2, last12 ) .

Notas

Este algoritmo realiza una tarea similar a la que hace ranges:: set_union . Ambos consumen dos rangos de entrada ordenados y producen una salida ordenada con elementos de ambas entradas. La diferencia entre estos dos algoritmos está en el manejo de valores de ambos rangos de entrada que se comparan como equivalentes (ver notas sobre LessThanComparable ). Si cualquier valor equivalente apareció n veces en el primer rango y m veces en el segundo, ranges::merge produciría todas las n + m ocurrencias mientras que ranges::set_union produciría solo max ( n, m ) . Por lo tanto, ranges::merge produce exactamente N valores y ranges::set_union puede producir menos.

Implementación posible

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 {};

Ejemplo

#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 }

Véase también