#include <map>

#include <iostream>
#include <iterator>
#include <algorithm>
#include <cassert>



namespace dj { namespace utils { namespace details {

template <typename T>
struct DefaultResolver
{
    void operator()(T&, const T&) const {}
};

}                                                           // namespace details

/**
 *  complexity: O(Nlog(N))
 *  exception guarantee: strong (rollback semantic)
 *  conflict_resolver: binary functional object w/ signature like this:
 *
 *      `void conflict_resolver(Value& original, const Value& new)`
 *
 *       it is applied for every mapped_type element w/ same key (in terms
 *       of target map, ordered by C1 comparator)
 *
 *  @todo Consider the case when a way to resolve conflicts depends on
 *  keys. Also correct resolving could change the key of result element.
 *
 *  @todo Potentially, the algo could be generalized for using w/ iterators
 *  But there are some conceptual problems to be solved, like:
 *    - what is value_type of iterators? If the pair of iterators represents
 *    ordered range of single values, then conflict resolver can't change
 *    them (because it can affect an ordering). In such case the alog turns
 *    to the fabfik version of std::merge.
 *    - If value_type is a key/value pair, it's too specific (not very general)
 *    solution, isn't it? An external template ad hoc free function interface
 *    to extract key and value fron any value_type could be a proper solution
 *    (like boost::property_map based boost::bgl approach)
 *
 *  @todo Is it OK to allow to mix maps w/ different allocators in the algo?
 */
template<
    typename Key
  , typename Value
  , typename Allocator
  , typename C1
  , typename C2
  , typename F = details::DefaultResolver<Value>
>
inline void merge_to(
    std::map<Key, Value, C1, Allocator>& target
  , const std::map<Key, Value, C2, Allocator>& source
  , F conflict_resolver = details::DefaultResolver<Value>{}
)
{
    auto tmp(target);
    for (const auto& pr : source)
    {
        auto it = tmp.find(pr.first);
        if (end(tmp) == it)
            tmp.emplace(pr);
        else
            conflict_resolver(it->second, pr.second);
    }
    target = std::move(tmp);
}

/**
 *  complexity: O(N)
 *  exception guarantee: strong (rollback semantic)
 */
template<
    typename Key
  , typename Value
  , typename C1
  , typename Allocator
  , typename F = details::DefaultResolver<Value>
>
inline void merge_to(
    std::map<Key, Value, C1, Allocator>& target
  , const std::map<Key, Value, C1, Allocator>& source
  , F conflict_resolver = details::DefaultResolver<Value>{}
)
{
    using map_type = typename std::remove_cv<
        typename std::remove_reference<decltype(target)>::type
    >::type;
    using value_type = typename map_type::value_type;

    auto tmp(target);
    auto it = begin(tmp);
    for (const auto& src_mapped : source)
    {
        // find first element of target sequence not intented to be placed before current element of source sequence
        it = std::find_if(
            it
          , end(tmp)
          , [src_key = src_mapped.first] (const value_type& tgt_mapped) {
              const auto& tgt_key = tgt_mapped.first;
              return ! C1()(tgt_key, src_key);
          }
        );
        const auto& src_key = src_mapped.first;
        // if element found and it has same key (ordered at same place)
        if (end(tmp) != it && !C1()(src_key, it->first /*tgt_key*/))
        {
            // resolve conflict
            const auto& src_val = src_mapped.second;
            auto& tgt_val = it->second;
            conflict_resolver(tgt_val, src_val);
        }
        else
            it = tmp.emplace_hint(it, src_mapped);

        ++it;
    }
    target = std::move(tmp);
}

}}                                                          // namespace utils, dj

namespace std {

template <typename First, typename Second>
inline std::ostream& operator<<(std::ostream& os, const std::pair<First, Second>& pr)
{
    return os << "{" << pr.first << " ," << pr.second << "}";
}

}                                                           // namespace std


int main(int argc, char* argv[])
{
    {
    std::map<int, int> to {{1,1}, {3,3}, {5,5}, {7,7}, {42,42}};
    std::map<int, int, std::greater<int>> from{{2,2}, {4,4}, {6,6}, {42, 375}};
    dj::utils::merge_to(to, from);
    std::copy(begin(to), end(to), std::ostream_iterator<std::pair<const int, int>>(std::cout, " "));
    std::cout << std::endl;
    assert((to == std::map<int, int>{{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{42,42}}));
    }
    {
    std::map<int, int> to {{1,1}, {3,3}, {5,5}, {7,7}, {42,42}};
    std::map<int, int> from{{2,2}, {4,4}, {6,6}};
    std::map<int, int> result;
    std::merge(begin(to), end(to), begin(from), end(from), std::inserter(result, result.end()));
    std::copy(begin(result), end(result), std::ostream_iterator<std::pair<const int, int>>(std::cout, " "));
    std::cout << std::endl;
    assert((result == std::map<int, int>{{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{42,42}}));
    }
    {
    std::map<int, int> to {{1,1}, {3,3}, {5,5}, {7,7}, {42,42}};
    std::map<int, int, std::greater<int>> from{{2,2}, {4,4}, {6,6}, {42, 735}};
    dj::utils::merge_to(to, from, [](int& orig, int rhv) { orig += rhv; });
    std::copy(begin(to), end(to), std::ostream_iterator<std::pair<const int, int>>(std::cout, " "));
    std::cout << std::endl;
    assert((to == std::map<int, int>{{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{42,777}}));
    }
    {
    // UB actually
    std::map<int, int> from {{1,1}, {3,3}, {5,5}, {7,7}, {42,42}};
    std::map<int, int, std::greater<int>> to{{2,2}, {4,4}, {6,6}, {42, 735}};
    std::map<int, int> result;
    std::merge(begin(to), end(to), begin(from), end(from), std::inserter(result, result.end()));
    std::copy(begin(result), end(result), std::ostream_iterator<std::pair<const int, int>>(std::cout, " "));
    std::cout << std::endl;
    }

    {
    std::map<int, int> to {{1,1}, {3,3}, {5,5}, {7,7}, {42,42}};
    std::map<int, int> from{{2,2}, {4,4}, {6,6}, {42, 375}};
    dj::utils::merge_to(to, from);
    std::copy(begin(to), end(to), std::ostream_iterator<std::pair<const int, int>>(std::cout, " "));
    std::cout << std::endl;
    assert((to == std::map<int, int>{{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{42,42}}));
    }
    {
    std::map<int, int> to {{1,1}, {3,3}, {5,5}, {7,7}, {42,42}};
    std::map<int, int> from{{2,2}, {4,4}, {6,6}, {42, 735}};
    dj::utils::merge_to(to, from, [](int& orig, int rhv) { orig += rhv; });
    std::copy(begin(to), end(to), std::ostream_iterator<std::pair<const int, int>>(std::cout, " "));
    std::cout << std::endl;
    assert((to == std::map<int, int>{{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{42,777}}));
    }
    return 0;
}