Merge two Boost Fusion maps based on keys

Question

I have two boost::fusion::maps that I want to merge in a certain way. For the two maps I want to generate a third that has all the keys present in both maps and the values are added if both a present. For example:

#include <boost/fusion/container/map.hpp>
namespace bfn = boost::fusion;
using namespace boost::fusion;

struct x{};
struct y{};
struct z{};

int main(){

    auto m = make_map<x, y>(2, 4.3);
    auto n = make_map<x>(2.);
    auto l = accumulate_merge(m, n); // how this function should look like?
}

After that l will be equivalent to make_map<x, y>(2 + 2., 4.3).

I have no clue where to start. I tried to begin with join (and the eliminate duplicates but I got complicated pretty fast).

Is there a tool in Boost Fusion that can help me?

(There are lots of subtleties like what to do if for the same key the two corresponding types are different --but still addable--. But any first version will help).

Answer 1

I managed to come up with this version using boost::fusion::fold twice. I am not sure if it is (compile-time) optimal.

Basically, I iterate first over the first map. If the key is not in the second map the element is pushed to the result. If the key is in the second map the elements are added and the result (whatever the type is pushed to the result).

Finally, I iterate in the second map. If the key is in the first map I ignore it (because it was added in the first pass). If the key is not in the second the element is pushed to the result.

(The result is that the first map has precedence for the ordering of the key types)

There are some open issues or doubts:

1) there is a more efficient/compact way of doing this

2) I wasn't sure about the use of forward basically I used it everywhere (just in case)

3) not sure about the auto vs. decltype(auto) in the function returns.

4) The functions are not SFINAE friendly, I could add guards to generate soft errors. (For example if values cannot be added).

5) The result doesn't have any natural order, I don't know if this is a problem with the algorithm or with fold or because map don't specify an order with push_back (after all it is a map).

Comments are welcome.

Now the code:

namespace boost{
namespace fusion{
namespace detail{
template<class Map2>
struct merge1{
    Map2 m2_;
    template<typename MapOut, typename Pair1>
    auto operator()(MapOut&& mo, Pair1&& p1) const{
        return conditional_push_back(std::forward<MapOut>(mo), std::forward<Pair1>(p1), has_key<typename std::decay_t<Pair1>::first_type>(m2_));
    }
    template<typename MapOut, typename Pair1> 
    auto conditional_push_back(MapOut&& mo, Pair1&& p1, mpl_::bool_<false>) const{
        return push_back(std::forward<MapOut>(mo), std::forward<Pair1>(p1));
    }
    template<typename MapOut, typename Pair1>
    auto conditional_push_back(MapOut&& mo, Pair1&& p1, mpl_::bool_<true>) const{
        return push_back(std::forward<MapOut>(mo), make_pair<typename std::decay_t<Pair1>::first_type>(p1.second + at_key<typename std::decay_t<Pair1>::first_type>(m2_)));
    }
};
template<class Map2>
merge1<Map2> make_merge1(Map2&& m2){return {std::forward<Map2>(m2)};}

template<class Map1>
struct merge2{
    Map1 m1_;
    template<typename MapOut, typename Pair2>
    auto operator()(MapOut&& mo, Pair2&& p2) const{
        return conditional_push_back(std::forward<MapOut>(mo), std::forward<Pair2>(p2), has_key<typename std::decay_t<Pair2>::first_type>(m1_));
    }
    template<typename MapOut, typename Pair2>
    auto conditional_push_back(MapOut&& mo, Pair2&& p2, mpl_::bool_<false>) const{
        return push_back(std::forward<MapOut>(mo), std::forward<Pair2>(p2));
    }
    template<typename MapOut, typename Pair2>
    auto conditional_push_back(MapOut&& mo, Pair2&&   , mpl_::bool_<true>) const{
        return mo;
    }
};
template<class Map1> 
merge2<Map1> make_merge2(Map1&& m){return {std::forward<Map1>(m)};}
}

template<class Map1, class Map2>
inline auto accumulate_merge(Map1&& m1, Map2&& m2){
    return 
        as_map( // not completely sure this is a good idea
            fold( // second map2 is checked for unpaired elements
                std::forward<Map1>(m1), 
                fold( // first map1 takes the lead
                    std::forward<Map2>(m2), 
                    make_map<>(), 
                    detail::make_merge1(std::forward<Map1>(m1))
                ), 
                detail::make_merge2(std::forward<Map2>(m2))
            )
        );
}
}}

namespace bfn = boost::fusion;
using namespace boost::fusion;

struct x{};
struct y{};
struct z{};

int main(){

    auto m = make_map<x, y   >(2, 4.3    );
    auto n = make_map<   y, z>(   2  , 8.);
    auto l = accumulate_merge(m, n);
    assert( at_key<x>(l) == at_key<x>(m) );
    assert( at_key<y>(l) == at_key<y>(m) + at_key<y>(n) );
    assert( typeid(at_key<y>(l)) == typeid(at_key<y>(m) + at_key<y>(n)) );
    assert( at_key<z>(l) == at_key<z>(n) );
}