std::ranges::set_symmetric_difference, std::ranges::set_symmetric_difference_result
From cppreference.com
| Defined in header <algorithm>
|
||
| Call signature |
||
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>
set_symmetric_difference( I1 first1, S1 last1, I2 first2, S2 last2,
O d_first, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(1) | (since C++20) |
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>
set_symmetric_difference( R1&& r1, R2&& r2, O d_first, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(2) | (since C++20) |
template< /*execution-policy*/ Ep,
std::random_access_iterator I1, std::sized_sentinel_for<I1> S1,
std::random_access_iterator I2, std::sized_sentinel_for<I2> S2,
std::random_access_iterator O, std::sized_sentinel_for<O> OutS,
class Comp = ranges::less,
class Proj1 = std::identity, class Proj2 = std::identity >
requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
ranges::set_symmetric_difference_result<I1, I2, O>
set_symmetric_difference( Ep&& policy, I1 first1, S1 last1,
I2 first2, S2 last2,
O d_first, OutS d_last, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(3) | (since C++26) |
template< /*execution-policy*/ Ep,
/*sized-random-access-range*/ R1, /*sized-random-access-range*/ R2,
/*sized-random-access-range*/ OutR, class Comp = ranges::less,
class Proj1 = std::identity, class Proj2 = std::identity >
requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,
ranges::iterator_t<OutR>, Comp, Proj1, Proj2>
ranges::set_symmetric_difference_result<ranges::borrowed_iterator_t<R1>,
ranges::borrowed_iterator_t<R2>,
ranges::borrowed_iterator_t<OutR>>
set_symmetric_difference( Ep&& policy, R1&& r1, R2&& r2,
OutR&& d_r, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(4) | (since C++26) |
| Helper types |
||
template< class I1, class I2, class O >
using set_symmetric_difference_result = ranges::in_in_out_result<I1, I2, O>;
|
(5) | (since C++20) |
For the definition of /*execution-policy*/, see this page; for the definition of /*sized-random-access-range*/, see this page.
Constructs a hypothetical sorted symmetric difference from two sorted source ranges, the symmetric difference consists of the set of elements present in exactly one of the source ranges. Copies elements of the difference to the destination range.
1,2) All elements of the symmetric difference will be copied to the destination range beginning at
d_first. For each group of equivalent elements to be included in the symmetric difference, let
n1 and n2 be the numbers of elements from the two source ranges respectively:
- The first
std::min(n1, n2)elements from the first source range will be skipped, and all remaining elments will be included in the symmetric difference in order. - The first
std::min(n1, n2)elements from the second source range will be skipped, and all remaining elments will be included in the symmetric difference in order.
1) The two source ranges are
[first1, last1) and [first2, last2).2) The two source ranges are
r1 and r2.3,4) Same as (1,2), but executed according to
policy, and the destination range is [d_first, d_last) or d_r. If the destination range is exhausted, the remaining elements in the two source ranges will not be copied.If any of the following conditions is satisfied, the behavior is undefined:
- The first source range is not sorted with respect to the comparator
compand projectionproj1. - The second source range is not sorted with respect to the comparator
compand projectionproj2. - The destination range overlaps with any of the two source ranges.
The function-like entities described on this page are algorithm function objects (informally known as 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.
Parameters
| first1, last1 | - | the iterator-sentinel pair defining the first source range |
| r1 | - | the first source range |
| first2, last2 | - | the iterator-sentinel pair defining the second source range |
| r2 | - | the second source range |
| d_first | - | the beginning of the destination range |
| d_last | - | the sentinel of the destination range |
| d_r | - | the destination range |
| comp | - | the comparator to be applied to the (projected) elements |
| proj1 | - | the projection to be applied to the elements in the first source range |
| proj2 | - | the projection to be applied to the elements in the second source range |
| policy | - | the execution policy to use |
Return value
A ranges::set_symmetric_difference_result object where:
- For the data member in1:
- If all elements of the first source range are copied or skipped,
in1holds the past-the-end iterator of that range. - Otherwise, if all elements of the second source range are copied or skipped,
in1holds an iterator to the first remaining non-skipped element in the first source range. - Otherwise see below.
- If all elements of the first source range are copied or skipped,
- For the data member in2:
- If all elements of the second source range are copied or skipped,
in2holds the past-the-end iterator of that range. - Otherwise, if all elements of the first source range are copied or skipped,
in2holds an iterator to the first remaining non-skipped element in the second source range. - Otherwise see below.
- If all elements of the second source range are copied or skipped,
- The data member out holds an iterator past the last assigned element in the destination range, or an iterator to the beginning of the destination range if no element is assigned.
If both source ranges have elements remaining, let elem1 and elem2 be the first remaining non-skipped elements in the two source ranges respectively:
- If
elem2does not exist orelem1orders beforeelem2,in1holds an iterator toelem1, andin2holds an iterator to the first remaining element in the second source range that is ordered afterelem1. - Otherwise,
in2holds an iterator toelem2, andin1holds an iterator to the first remaining element in the first source range that is ordered afterelem2.
Complexity
Given
- N1 as
ranges::distance(first1, last1)orranges::distance(r1), - N2 as
ranges::distance(first2, last2)orranges::distance(r2):
1,2) At most 2⋅(N1+N2)-1 applications of
comp, proj1 and proj2.3,4) 𝓞(N1+N2) applications of
comp, proj1 and proj2.Exceptions
3,4) During the execution process:
- If the temporary memory resources required for parallelization are not available, std::bad_alloc is thrown.
- If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for standard policies, std::terminate is invoked).
Possible implementation
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 d_first,
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)))
{
*d_first = *first1;
++first1;
++result;
}
else if (std::invoke(comp, std::invoke(proj2, *first2),
std::invoke(proj1, *first1)))
{
*d_first = *first2;
++first2;
++result;
}
else
{
++first1;
++first2;
}
}
auto res1{ranges::copy(std::move(first1), std::move(last1), std::move(d_first))};
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 R>
constexpr get_end(R&& r)
{
return ranges::end(r);
}
template<ranges::forward_range R>
constexpr get_end(R&& r)
{
return ranges::next(ranges::begin(r), ranges::end(r));
}
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 d_first,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
{
return (*this)(ranges::begin(r1), get_end(r1),
ranges::begin(r2), get_end(r2),
std::move(d_first), 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 . .