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

Führt zwei sortierte Bereiche [ [ first1 , last1 ) und [ first2 , last2 ) zu einem sortierten Bereich zusammen, beginnend bei result .

Eine Sequenz wird als sortiert bezüglich des Vergleichsfunktors comp bezeichnet, wenn für jeden Iterator it , der auf die Sequenz zeigt, und jede nicht-negative Ganzzahl n , sodass it + n ein gültiger Iterator ist, der auf ein Element der Sequenz zeigt, std:: invoke ( comp, std:: invoke ( proj2, * ( it + n ) ) , std:: invoke ( proj1, * it ) ) ) zu false ausgewertet wird.

Das Verhalten ist undefiniert, wenn der Zielbereich einen der Eingabebereiche überlappt (die Eingabebereiche können sich gegenseitig überlappen).

Diese Merge-Funktion ist stabil , was bedeutet, dass für äquivalente Elemente in den beiden ursprünglichen Bereichen die Elemente aus dem ersten Bereich (unter Beibehaltung ihrer ursprünglichen Reihenfolge) vor den Elementen aus dem zweiten Bereich (unter Beibehaltung ihrer ursprünglichen Reihenfolge) stehen.

Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithm Function Objects (informell bekannt als Niebloids ), das heißt:

• Explizite Template-Argumentlisten können beim Aufruf keiner von ihnen angegeben werden.
• Keiner von ihnen ist sichtbar für argument-dependent lookup .
• Wenn einer von ihnen durch normal unqualified lookup als Name links vom Funktionsaufrufoperator gefunden wird, wird argument-dependent lookup unterdrückt.

Parameter

Rückgabewert

{ last1, last2, result_last } , wobei result_last das Ende des konstruierten Bereichs ist.

Komplexität

Höchstens N − 1 Vergleiche und Anwendungen jeder Projektion, wobei N = ranges:: distance ( first1, last1 ) + ranges:: distance ( first2, last12 ) .

Hinweise

Dieser Algorithmus führt eine ähnliche Aufgabe aus wie ranges:: set_union es tut. Beide verarbeiten zwei sortierte Eingabebereiche und erzeugen eine sortierte Ausgabe mit Elementen aus beiden Eingaben. Der Unterschied zwischen diesen beiden Algorithmen liegt im Umgang mit Werten aus beiden Eingabebereichen, die als äquivalent verglichen werden (siehe Hinweise zu LessThanComparable ). Wenn äquivalente Werte n -mal im ersten Bereich und m -mal im zweiten auftraten, würde ranges::merge alle n + m Vorkommen ausgeben, während ranges::set_union nur max ( n, m ) ausgeben würde. Daher gibt ranges::merge exakt N Werte aus und ranges::set_union kann weniger erzeugen.

Mögliche Implementierung

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

Beispiel

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

Siehe auch