std::ranges::set_intersection, std::ranges::set_intersection_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_intersection_result<I1, I2, O>
set_intersection( 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_intersection_result<ranges::borrowed_iterator_t<R1>,
ranges::borrowed_iterator_t<R2>, O>
set_intersection( 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_intersection_result<I1, I2, O>
set_intersection( 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_intersection_result<ranges::borrowed_iterator_t<R1>,
ranges::borrowed_iterator_t<R2>,
ranges::borrowed_iterator_t<OutR>>
set_intersection( 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_intersection_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 intersection from two sorted source ranges, the intersection consists of the set of elements present at least one of the source ranges. Copies elements of the intersection to the destination range.
1,2) All elements of the intersection will be copied to the destination range beginning at
d_first. For each group of equivalent elements to be included in the intersection, 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 included in the intersection in order. - The remaining elements from the first source range and all
n2elements from the second source range will be skipped.
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_intersection_result object where:
- The data member in1 holds an iterator to the first remaining non-skipped element in the first source range, or the past-the-end iterator of the first source range if all elements of that range are copied or skipped.
- The data member in2 holds an iterator to the first remaining non-skipped element in the second source range, or the past-the-end iterator of the second source range if all elements of that 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.
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_intersection_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_intersection_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)))
++first1;
else if (std::invoke(comp, std::invoke(proj2, *first2),
std::invoke(proj1, *first1)))
++first2;
else
*d_first = *first1, ++first1, ++first2, ++d_first;
}
return {ranges::next(std::move(first1), std::move(last1)),
ranges::next(std::move(first2), std::move(last2)),
std::move(d_first)};
}
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_intersection_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_intersection_fn set_intersection{};
|
Example
Run this code
#include <algorithm>
#include <iterator>
#include <print>
#include <vector>
int main()
{
const auto in1 = {1, 2, 2, 3, 4, 5, 6};
const auto in2 = {2, 2, 3, 3, 5, 7};
std::vector<int> out{};
std::ranges::set_intersection(in1, in2, std::back_inserter(out));
std::print("{} ∩ {} = {}\n", in1, in2, out);
}
Output:
[1, 2, 2, 3, 4, 5, 6] ∩ [2, 2, 3, 3, 5, 7] = [2, 2, 3, 5]