std::ranges::set_intersection, std::ranges::set_intersection_result

Constructs a sorted range beginning at result consisting of elements that are found in both sorted input ranges [first1, last1) and [first2, last2). If some element is found m times in [first1, last1) and n times in [first2, last2), the first min(m, n) elements will be copied from the first range to result. The order of equivalent elements is preserved.

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.

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.

[edit] Parameters

[edit] Return value

{last1, last2, result_last}, where result_last is the end of the constructed range.

[edit] Complexity

At most \(\scriptsize 2\cdot(N_1+N_2)-1\)2·(N1+N2)-1 comparisons and applications of each projection, where \(\scriptsize N_1\)N1 and \(\scriptsize N_2\)N2 are ranges::distance (first1, last1) and ranges::distance (first2, last2), respectively.

[edit] 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 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)))
 ++first1;
 else if (std::invoke (comp, std::invoke (proj2, *first2),
 std::invoke (proj1, *first1)))
 ++first2;
 else
 *result = *first1, ++first1, ++first2, ++result;
 }
 return {ranges::next (std::move(first1), std::move(last1)),
 ranges::next (std::move(first2), std::move(last2)),
 std::move(result)};
 }
 
 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 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_intersection_fn set_intersection {};

[edit] Example

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
void print(const auto& v, const auto& rem)
{
 std::cout << "{ ";
 for (const auto& e : v)
 std::cout << e << ' ';
 std::cout << '}' << rem;
}
 
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));
 
 print(in1, " ∩ "), print(in2, " = "), print(out, "\n");
}

{ 1 2 2 3 4 5 6 } ∩ { 2 2 3 3 5 7 } = { 2 2 3 5 }

[edit] See also

• In other languages

• Deutsch
• Español
• Français
• Italiano
• 日本語
• Português
• Русский
• 中文