std::ranges...ence_result(3)

📦 version 2024.07.05, in nixpkgs unstable, opensuse-leap 16.0

💅 std::ranges::set_symmetric_difference + std::ranges::set_symmetric_difference_result 💅

okay bestie, welcome to the C++ Standard Libary manual — yes, that spelling is staying, it's part of the vibe 💀. This page is all about std::ranges::set_symmetric_difference and std::ranges::set_symmetric_difference_result, and it's giving C++20 set-operation main character energy ✨.

🌸 NAME 🌸

std::ranges::set_symmetric_difference,std::ranges::set_symmetric_difference_result — the two names, together, exactly like the manpage says. And because the original NAME section is literally the same thing twice, here's the encore: std::ranges::set_symmetric_difference,std::ranges::set_symmetric_difference_result 🫶.

✨ Synopsis ✨

Defined in header <algorithm> — iconic, as always 💖.

📞 Call signature 📞

These overloads are since C++20 🦋.

(1):

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

(2):

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

🧸 Helper types 🧸

(3) — since C++20:

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

okay so here's the lore, bestie: this computes the symmetric difference of two sorted ranges — the elements found in either range, but not in both of them, get copied to the range beginning at result 💅. The resulting range is also sorted. Obsessed with a tidy output range, honestly.

If some element is found m times in [first1, last1) and n times in [first2, last2), it will be copied to result exactly │m - n│ times. If m > n, then the last m - n of those elements are copied from [first1, last1); otherwise the last n - m elements are copied from [first2, last2). The resulting range cannot overlap with either of the input ranges. no cap, that part matters 🚨.

The behavior is undefined if: - the input ranges are not sorted with respect to comp and proj1 or proj2, respectively, or - the resulting range overlaps with either of the input ranges.

That's a hard vibe check fail, bestie — undefined behavior is not the moment 💀.

1) Elements are compared using the given binary comparison function comp.

2) Same as (1), but uses r1 as the first range and r2 as the second range, as if using ranges::begin(r1) as first1, ranges::end(r1) as last1, ranges::begin(r2) as first2, and ranges::end(r2) as last2.

The function-like entities described on this page are niebloids, that is:

  • Explicit template argument lists cannot be specified when calling any of them.
  • None of them are visible to argument-dependent lookup.
  • When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.

In practice, they may be implemented as function objects, or with special compiler extensions ✨.

🎀 Parameters 🎀

  • first1, last1 — iterator-sentinel pair denoting the first input sorted range
  • first2, last2 — iterator-sentinel pair denoting the second input sorted range
  • r1 — the first sorted input range
  • r2 — the second sorted input range
  • result — the beginning of the output range
  • comp — comparison to apply to the projected elements
  • proj1 — projection to apply to the elements in the first range
  • proj2 — projection to apply to the elements in the second range

🦋 Return value 🦋

{last1, last2, result_last}, where result_last is the end of the constructed range. cute little triple, honestly 🫶.

🔥 Complexity 🔥

At most 2·(N1+N2)-1 comparisons and applications of each projection, where N1 and N2 are ranges::distance(first1, last1) and ranges::distance(first2, last2), respectively. math girlie said stay in your lane, and the lane is logarithmic-ish set algorithm business 💅.

👑 Possible implementation 👑

not me about to show you the whole implementation, but yes bestie, every line is here — we don't skip:

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

🌈 Example 🌈

// Run this code

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

Output:

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

ate, honestly 💅✨.

🫶 See also 🫶

  • ranges::set_union (C++20) — computes the union of two sets (niebloid)
  • ranges::set_difference (C++20) — computes the difference between two sets (niebloid)
  • ranges::set_intersection (C++20) — computes the intersection of two sets (niebloid)
  • ranges::includes (C++20) — returns true if one sequence is a subsequence of another (niebloid)
  • set_symmetric_difference — computes the symmetric difference between two sets (function template)

byeee bestie 💖 this was the C++ Standard Libary page from source cppreference.com, dated 2024.06.10, page std::ranges...ence_result(3) — mwah, slay, periodt 🎀🦋💜.

📦 where this page comes from