std::ranges:: set_symmetric_difference, std::ranges:: set_symmetric_difference_result

Berechnet die symmetrische Differenz von zwei sortierten Bereichen: Die Elemente, die in einem der Bereiche gefunden werden, aber nicht in beiden, werden in den Bereich kopiert, der bei result beginnt. Der resultierende Bereich ist ebenfalls sortiert.

Wenn ein Element m -mal in [ first1 , last1 ) und n -mal in [ first2 , last2 ) vorkommt, wird es genau │m - n│ -mal nach result kopiert. Wenn m > n , dann werden die letzten m - n dieser Elemente aus [ first1 , last1 ) kopiert, andernfalls werden die letzten n - m Elemente aus [ first2 , last2 ) kopiert. Der resultierende Bereich darf sich mit keinem der Eingabebereiche überlappen.

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.

Mögliche Implementierung

struct set_symmetric_difference_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_symmetric_difference_result<I1, I2, O>
        operator()(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        while (!(first1 == last1 or first2 == last2))
        {
            if (std::invoke(comp, std::invoke(proj1, *first1), std::invoke(proj2, *first2)))
            {
                *result = *first1;
                ++first1;
                ++result;
            }
            else if (std::invoke(comp, std::invoke(proj2, *first2),
                                       std::invoke(proj1, *first1)))
            {
                *result = *first2;
                ++first2;
                ++result;
            }
            else
            {
                ++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_symmetric_difference_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_symmetric_difference_fn set_symmetric_difference {};

Beispiel

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
void visualize_this(const auto& v, int min = 1, int max = 9)
{
    for (auto i {min}; i <= max; ++ i)
    {
        std::ranges::binary_search(v, i) ? std::cout << i : std::cout << '.';
        std::cout << ' ';
    }
    std::cout << '\n';
}
int main()
{
    const auto in1 = {1, 3, 4,    6, 7, 9};
    const auto in2 = {1,    4, 5, 6,    9};
    std::vector<int> out {};
    std::ranges::set_symmetric_difference(in1, in2, std::back_inserter(out));
    visualize_this(in1);
    visualize_this(in2);
    visualize_this(out);
}

1 . 3 4 . 6 7 . 9
1 . . 4 5 6 . . 9
. . 3 . 5 . 7 . .

Siehe auch