Assume we have two maps with some common keys but different values, I would like to iterate over the "intersection" of two maps, where the key are the same. Then I would like to perform a transform function f(key, value_in_map1, value_in_map2).
I would like to do it using range views, so that I can pipeline further. I tried ranges::views::set_intersection in range-v3, but it does not work as expected:
#include <map>
#include <iostream>
#include <range/v3/all.hpp>
int main () {
std::map<int, int> m1 {{0, 0}, {1, 1}, {2, 2}};
std::map<int, int> m2 {{0, 0}, {2, 1}, {3, 2}};
auto res = ranges::views::set_intersection(m1, m2);
for(auto&& p : res) {
std::cout << p.first << ' ' << p.second << '\n';
// output: 0 0
}
/* Here is what I expect for the desired view
auto res = map_intersection(m1, m2);
for(auto&& [key, value_in_m1, value_in_m2] : res) {
std::cout << p.first << ' ' << p.second << '\n';
// expected output:
// 0 0 0
// 2 2 1
}
// my desired syntax
map_intersection(m1, m2)
| ranges::views::transform([](int key, int value_in_m1, int value_in_m2) {
// use the values here
})
| more_views
*/
return 0;
}
https://godbolt.org/z/3cbMY9n7b shows the above code.
If such a view (map_intersection in the above commented code) does not exist in range-v3, how to implement it?
Update (Jan 05, 2024)
I followed @fdan's suggestion (thanks) and used the implementation of views::set_intersection to create a new view views::set_intersection_return_both, which returns both iterators' values instead of only the first one.
The main implementation idea is:
set_intersection_return_both_cursor based on set_intersection_cursor using public inheritance.using value_type = std::pair<range_value_t<R1>, range_value_t<R2>>;read function: auto CPP_auto_fun(read)()(const)
(
return value_type{*it1_, *it2_}
)
See https://godbolt.org/z/s9b7d4h1n for the implementation and example usages.
The view works well in for-loop and binding back pipeline syntax. However, it still has issues to pipeline further with views::transform.
Update (Jan 08, 2024)
After further understanding the zip_view, I make my implementation work for pipeline now, see
https://godbolt.org/z/bexEvan7M (I change my view's name to set_intersection_zip)
The main change is to add a move function and the rvalue_type.
Here is the major part of the implementation (the rest can be found in https://godbolt.org/z/bexEvan7M)
/// \cond
namespace detail {
template<bool IsConst, typename Rng1, typename Rng2, typename C, typename P1,
typename P2>
struct set_intersection_zip_cursor
: public set_intersection_cursor<IsConst, Rng1, Rng2, C, P1, P2>
{
private:
friend struct set_intersection_cursor_return_both<!IsConst, Rng1, Rng2, C, P1, P2>;
using set_intersection_cursor<IsConst, Rng1, Rng2, C, P1, P2>::it1_;
using set_intersection_cursor<IsConst, Rng1, Rng2, C, P1, P2>::it2_;
using pred_ref_ = typename set_intersection_cursor<IsConst, Rng1, Rng2, C, P1, P2>::pred_ref_;
using proj1_ref_ = typename set_intersection_cursor<IsConst, Rng1, Rng2, C, P1, P2>::proj1_ref_;
using proj2_ref_ = typename set_intersection_cursor<IsConst, Rng1, Rng2, C, P1, P2>::proj2_ref_;
using R1 = typename set_intersection_cursor<IsConst, Rng1, Rng2, C, P1, P2>::R1;
using R2 = typename set_intersection_cursor<IsConst, Rng1, Rng2, C, P1, P2>::R2;
public:
using value_type = common_pair<iter_reference_t<decltype(it1_)>, iter_reference_t<decltype(it2_)>>;
using rvalue_type = common_pair<iter_rvalue_reference_t<decltype(it1_)>, iter_rvalue_reference_t<decltype(it2_)>>;
using single_pass = meta::or_c<single_pass_iterator_<iterator_t<R1>>,
single_pass_iterator_<iterator_t<R2>>>;
set_intersection_zip_cursor() = default;
set_intersection_zip_cursor(pred_ref_ pred, proj1_ref_ proj1, proj2_ref_ proj2,
iterator_t<R1> it1, sentinel_t<R1> end1,
iterator_t<R2> it2, sentinel_t<R2> end2)
: set_intersection_cursor<IsConst, Rng1, Rng2, C, P1, P2>(pred, proj1, proj2, it1, end1, it2, end2) {}
// clang-format off
auto CPP_auto_fun(read)()(const)
(
return value_type{*it1_, *it2_}
)
auto CPP_auto_fun(move)()(const)
(
return rvalue_type{iter_move(it1_), iter_move(it2_)}
)
// clang-format on
};
} // namespace detail
/// \endcond
There is no view or algorithm available in v3 or the STL for this. The main problem is that all set_* functions only return the value from the first range. In your example, you're comparing the pair of the map, so you only get 0 0 as a result. You can fix this by using custom projectors or a custom comparator, but then you would get 0 0 and 2 2 (from the first range) with 2 1 (from the second range) missing.
What you need is something like set_intersection_transform, which transforms both iterators before returning the result. Writing such a view with v3 is difficult, you can look at the existing source and the manual on how to write custom views. Implementing such a a view is probably out of scope for SO.
As an alternative you can calculate the intersection twice and then zip both results (and eventually transform them further). This is redundant work, but equal in terms of time complexity.
std::map<int, int> m1{{0, 0}, {1, 1}, {2, 2}};
std::map<int, int> m2{{0, 0}, {2, 1}, {3, 2}};
auto proj = &std::map<int, int>::value_type::first;
auto v1 = ranges::views::set_intersection(m1, m2, {}, proj, proj);
auto v2 = ranges::views::set_intersection(m2, m1, {}, proj, proj);
// 0 0 0
// 2 2 1
for (const auto& [m1_pair, m2_pair] : ranges::views::zip(v1, v2)) {
std::cout << m1_pair.first << " " << m1_pair.second << " " << m2_pair.second << std::endl;
}