c++ - 无需重新创建匹配 map

Question

假设我有两个 map 。这些 map 的值是相同的并且构建(不是复制)的成本很高。这些 map 的键属于不同类型，但可以相互转换。我需要设置第一个 map 的内容以匹配第二个的内容，但我必须一直循环遍历两个 map。有办法做到这一点吗？

作为这方面的一个例子，我已经将键简化为更容易识别的可转换的东西，并且只使用 int 作为值。在示例中，我想将 foo 的内容设置为与 bar 的内容匹配。但是我找不到不循环遍历两个 map 的方法。

map<int, int> foo = {{1, 100}, {2, 200}, {4, 400}};
map<char, int> bar = {{'1', 200}, {'3', 300}, {'5', 500}};

for(auto i = foo.begin(); i != foo.end(); ++i) {
    if(bar.end() == bar.find(static_cast<decltype(bar)::key_type>(i->first) + '0')){
        foo.erase(i);
    }
}

for(auto i = bar.begin(); i != bar.end(); ++i) {
    const decltype(foo)::key_type key = i->first - '0';

    if(foo.end() == foo.find(key) || foo[key] != i->second) {
        foo[key] = i->second;
    }
}

for(const auto i : foo){
    cout << i.first + 10 << ": " << i.second << endl;
}

这正确输出:

11: 200
13: 300
15: 500

[ Live Example ]

有没有一种不需要循环遍历两个 map 的方法？

Answer 1

如果不检查每个集合的每个元素，就无法同步两个集合。因此，您将不得不迭代这两个集合。

但是如果集合以相同的顺序键入，您可以通过并行迭代两个集合并合并来加快速度。如果您的标准库具有有用的 emplace_hint 实现，这将特别有效。

基本伪代码(意味着它不会编译并且可能无法正常工作:-))。

/* Makes a into a copy of b, assuming that the key types are
 * consistently comparable, and that a key for a can be constructed
 * from a key for b.
 */
void merge(Map1& a, Map2& b) {
  auto it_a = a.begin(), end_a = a.end();
  auto it_b = b.begin(), end_b = b.end();
  for (;;) {
    if (it_a == end_a) {
      /* Add remaining elements from b to a */
      for (; it_b != end_b; ++it_b)
        a.emplace_hint(it_a, it_b->first, it_b->second);
      return;
    } else if (it_b == end_b) {
      /* Remove remaining elements from a */
      while (it_a != end_a)
        it_a = a.erase(it_a);
      return;
    } else if (it_b->first < it_a->first) {
      /* Insert an element from b */
      a.emplace_hint(it_a, it_b->first, it_b->second);
      ++it_b;
    } else if (it_b->first == it_a->first) {
      /* Replace an element from b */
      a->second = b->second;
      ++it_a, ++it_b;
    } else {
      /* Delete element from a */
      it_a = a.erase(it_a);
    }
  }
}

注意:如果上面的代码可以覆盖现有值，则注意不要不必要地构造新值，但它并没有真正避免构造值，因为它可能会破坏与a 中不需要的键，然后构造一个与 a 中不存在的键关联的值。如果复制构造比赋值昂贵得多，那么保留一个构造值池可能是有意义的，代价是向映射值添加一个间接。 shared_ptr 是另一种可能性，尽管它也可能有点矫枉过正。