SHARE
TWEET

Untitled

a guest Feb 16th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <map>
  2.  
  3. #include <iostream>
  4. #include <iterator>
  5. #include <algorithm>
  6. #include <cassert>
  7.  
  8.  
  9.  
  10. namespace dj { namespace utils { namespace details {
  11.  
  12. template <typename T>
  13. struct DefaultResolver
  14. {
  15.     void operator()(T&, const T&) const {}
  16. };
  17.  
  18. }                                                           // namespace details
  19.  
  20. /**
  21.  *  complexity: O(Nlog(N))
  22.  *  exception guarantee: strong (rollback semantic)
  23.  *  conflict_resolver: binary functional object w/ signature like this:
  24.  *
  25.  *      `void conflict_resolver(Value& original, const Value& new)`
  26.  *
  27.  *       it is applied for every mapped_type element w/ same key (in terms
  28.  *       of target map, ordered by C1 comparator)
  29.  *
  30.  *  @todo Consider the case when a way to resolve conflicts depends on
  31.  *  keys. Also correct resolving could change the key of result element.
  32.  *
  33.  *  @todo Potentially, the algo could be generalized for using w/ iterators
  34.  *  But there are some conceptual problems to be solved, like:
  35.  *    - what is value_type of iterators? If the pair of iterators represents
  36.  *    ordered range of single values, then conflict resolver can't change
  37.  *    them (because it can affect an ordering). In such case the alog turns
  38.  *    to the fabfik version of std::merge.
  39.  *    - If value_type is a key/value pair, it's too specific (not very general)
  40.  *    solution, isn't it? An external template ad hoc free function interface
  41.  *    to extract key and value fron any value_type could be a proper solution
  42.  *    (like boost::property_map based boost::bgl approach)
  43.  *
  44.  *  @todo Is it OK to allow to mix maps w/ different allocators in the algo?
  45.  */
  46. template<
  47.     typename Key
  48.   , typename Value
  49.   , typename Allocator
  50.   , typename C1
  51.   , typename C2
  52.   , typename F = details::DefaultResolver<Value>
  53. >
  54. inline void merge_to(
  55.     std::map<Key, Value, C1, Allocator>& target
  56.   , const std::map<Key, Value, C2, Allocator>& source
  57.   , F conflict_resolver = details::DefaultResolver<Value>{}
  58. )
  59. {
  60.     auto tmp(target);
  61.     for (const auto& pr : source)
  62.     {
  63.         auto it = tmp.find(pr.first);
  64.         if (end(tmp) == it)
  65.             tmp.emplace(pr);
  66.         else
  67.             conflict_resolver(it->second, pr.second);
  68.     }
  69.     target = std::move(tmp);
  70. }
  71.  
  72. /**
  73.  *  complexity: O(N)
  74.  *  exception guarantee: strong (rollback semantic)
  75.  */
  76. template<
  77.     typename Key
  78.   , typename Value
  79.   , typename C1
  80.   , typename Allocator
  81.   , typename F = details::DefaultResolver<Value>
  82. >
  83. inline void merge_to(
  84.     std::map<Key, Value, C1, Allocator>& target
  85.   , const std::map<Key, Value, C1, Allocator>& source
  86.   , F conflict_resolver = details::DefaultResolver<Value>{}
  87. )
  88. {
  89.     using map_type = typename std::remove_cv<
  90.         typename std::remove_reference<decltype(target)>::type
  91.     >::type;
  92.     using value_type = typename map_type::value_type;
  93.  
  94.     auto tmp(target);
  95.     auto it = begin(tmp);
  96.     for (const auto& src_mapped : source)
  97.     {
  98.         // find first element of target sequence not intented to be placed before current element of source sequence
  99.         it = std::find_if(
  100.             it
  101.           , end(tmp)
  102.           , [src_key = src_mapped.first] (const value_type& tgt_mapped) {
  103.               const auto& tgt_key = tgt_mapped.first;
  104.               return ! C1()(tgt_key, src_key);
  105.           }
  106.         );
  107.         const auto& src_key = src_mapped.first;
  108.         // if element found and it has same key (ordered at same place)
  109.         if (end(tmp) != it && !C1()(src_key, it->first /*tgt_key*/))
  110.         {
  111.             // resolve conflict
  112.             const auto& src_val = src_mapped.second;
  113.             auto& tgt_val = it->second;
  114.             conflict_resolver(tgt_val, src_val);
  115.         }
  116.         else
  117.             it = tmp.emplace_hint(it, src_mapped);
  118.  
  119.         ++it;
  120.     }
  121.     target = std::move(tmp);
  122. }
  123.  
  124. }}                                                          // namespace utils, dj
  125.  
  126. namespace std {
  127.  
  128. template <typename First, typename Second>
  129. inline std::ostream& operator<<(std::ostream& os, const std::pair<First, Second>& pr)
  130. {
  131.     return os << "{" << pr.first << " ," << pr.second << "}";
  132. }
  133.  
  134. }                                                           // namespace std
  135.  
  136.  
  137. int main(int argc, char* argv[])
  138. {
  139.     {
  140.     std::map<int, int> to {{1,1}, {3,3}, {5,5}, {7,7}, {42,42}};
  141.     std::map<int, int, std::greater<int>> from{{2,2}, {4,4}, {6,6}, {42, 375}};
  142.     dj::utils::merge_to(to, from);
  143.     std::copy(begin(to), end(to), std::ostream_iterator<std::pair<const int, int>>(std::cout, " "));
  144.     std::cout << std::endl;
  145.     assert((to == std::map<int, int>{{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{42,42}}));
  146.     }
  147.     {
  148.     std::map<int, int> to {{1,1}, {3,3}, {5,5}, {7,7}, {42,42}};
  149.     std::map<int, int> from{{2,2}, {4,4}, {6,6}};
  150.     std::map<int, int> result;
  151.     std::merge(begin(to), end(to), begin(from), end(from), std::inserter(result, result.end()));
  152.     std::copy(begin(result), end(result), std::ostream_iterator<std::pair<const int, int>>(std::cout, " "));
  153.     std::cout << std::endl;
  154.     assert((result == std::map<int, int>{{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{42,42}}));
  155.     }
  156.     {
  157.     std::map<int, int> to {{1,1}, {3,3}, {5,5}, {7,7}, {42,42}};
  158.     std::map<int, int, std::greater<int>> from{{2,2}, {4,4}, {6,6}, {42, 735}};
  159.     dj::utils::merge_to(to, from, [](int& orig, int rhv) { orig += rhv; });
  160.     std::copy(begin(to), end(to), std::ostream_iterator<std::pair<const int, int>>(std::cout, " "));
  161.     std::cout << std::endl;
  162.     assert((to == std::map<int, int>{{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{42,777}}));
  163.     }
  164.     {
  165.     // UB actually
  166.     std::map<int, int> from {{1,1}, {3,3}, {5,5}, {7,7}, {42,42}};
  167.     std::map<int, int, std::greater<int>> to{{2,2}, {4,4}, {6,6}, {42, 735}};
  168.     std::map<int, int> result;
  169.     std::merge(begin(to), end(to), begin(from), end(from), std::inserter(result, result.end()));
  170.     std::copy(begin(result), end(result), std::ostream_iterator<std::pair<const int, int>>(std::cout, " "));
  171.     std::cout << std::endl;
  172.     }
  173.  
  174.     {
  175.     std::map<int, int> to {{1,1}, {3,3}, {5,5}, {7,7}, {42,42}};
  176.     std::map<int, int> from{{2,2}, {4,4}, {6,6}, {42, 375}};
  177.     dj::utils::merge_to(to, from);
  178.     std::copy(begin(to), end(to), std::ostream_iterator<std::pair<const int, int>>(std::cout, " "));
  179.     std::cout << std::endl;
  180.     assert((to == std::map<int, int>{{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{42,42}}));
  181.     }
  182.     {
  183.     std::map<int, int> to {{1,1}, {3,3}, {5,5}, {7,7}, {42,42}};
  184.     std::map<int, int> from{{2,2}, {4,4}, {6,6}, {42, 735}};
  185.     dj::utils::merge_to(to, from, [](int& orig, int rhv) { orig += rhv; });
  186.     std::copy(begin(to), end(to), std::ostream_iterator<std::pair<const int, int>>(std::cout, " "));
  187.     std::cout << std::endl;
  188.     assert((to == std::map<int, int>{{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{42,777}}));
  189.     }
  190.     return 0;
  191. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top