std::ranges:: set_union, std::ranges:: set_union_result

Konstruiert eine sortierte Vereinigung beginnend bei result , bestehend aus der Menge der Elemente, die in einem oder beiden sortierten Eingabebereichen [ first1 , last1 ) und [ first2 , last2 ) vorhanden sind.

Wenn ein Element m mal in [ first1 , last1 ) und n mal in [ first2 , last2 ) gefunden wird, dann werden alle m Elemente aus [ first1 , last1 ) nach result kopiert, wobei die Reihenfolge erhalten bleibt, und anschließend genau max ( n - m, 0 ) Elemente aus [ first2 , last2 ) nach result kopiert, ebenfalls unter Beibehaltung der Reihenfolge.

Das Verhalten ist undefiniert, falls

• die Eingabebereiche sind nicht sortiert in Bezug auf comp und proj1 oder proj2 , beziehungsweise, oder
• der resultierende Bereich überschneidet sich mit einem der Eingabebereiche.

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 \(\scriptsize 2\cdot(N_1+N_2)-1\) 2·(N 1 +N 2 )-1 Vergleiche und Anwendungen jeder Projektion, wobei \(\scriptsize N_1\) N 1 und \(\scriptsize N_2\) N 2 jeweils ranges:: distance ( first1, last1 ) und ranges:: distance ( first2, last2 ) entsprechen.

Hinweise

Dieser Algorithmus führt eine ähnliche Aufgabe aus wie ranges::merge 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 Anmerkungen zu LessThanComparable ). Wenn äquivalente Werte n -mal im ersten Bereich und m -mal im zweiten Bereich auftreten, würde ranges::merge alle n + m Vorkommen ausgeben, während ranges::set_union nur std:: max ( n, m ) Vorkommen ausgeben würde. Daher gibt ranges::merge exakt \(\scriptsize (N_1+N_2)\) (N 1 +N 2 ) Werte aus, und ranges::set_union kann weniger erzeugen.

Mögliche Implementierung

struct set_union_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::set_union_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(proj1, *first1), 
                                  std::invoke(proj2, *first2)))
            {
                *result = *first1;
                ++first1;
            }
            else if (std::invoke(comp, std::invoke(proj2, *first2),
                                       std::invoke(proj1, *first1)))
            {
                *result = *first2;
                ++first2;
            }
            else
            {
                *result = *first1;
                ++first1;
                ++first2;
            }
        }
        auto res1 = ranges::copy(std::move(first1), std::move(last1), std::move(result));
        auto res2 = ranges::copy(std::move(first2), std::move(last2), std::move(res1.out));
        return {std::move(res1.in), std::move(res2.in), std::move(res2.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::set_union_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 set_union_fn set_union {};

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 << "} ∪ { ";
    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::set_union(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::set_union(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 4 5 6 7 }
{ 1 2 3 4 5 5 5 } ∪ { 3 4 5 6 7 } =
{ 1 2 3 4 5 5 5 6 7 }

Siehe auch