无需重新创建匹配地图

Question

假设我有两个 map。这些 map 的值是相同的并且构建起来（不是复制）是昂贵的。这些 map 的密钥类型不同，但可以相互转换。我需要将第一个 map 的内容设置为与第二个 map 的内容匹配，但我必须一直循环遍历两个 map。有办法吗？

作为这方面的一个例子，我将键简化为更容易识别的可转换的东西，并且只使用 ints 作为值。在这个例子中，我想设置 foo 的内容来匹配 bar 的内容。但是如果不循环遍历 maps.

，我找不到一种方法来做到这一点

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

使用 boost transformed 适配器，您可以简单地使用带有两个迭代器的 std::map 构造函数，并以更不易出错、更直接的方式实现相同的目的：

using namespace boost::adaptors;
auto transformed_map = 
    bar | transformed([](const std::pair<const char, int>& p) {
        return std::make_pair(p.first - '0', p.second);
    });

foo = std::map<int, int>(std::begin(transformed_map),
                         std::end(transformed_map));

我觉得以上更容易理解。

现在如果你发现自己经常这样做，而且建设成本太高，这可能表明设计问题更大。也许您想存储 shared_ptr<value_type> 而不是 value_type。或者您可能只想做类似的事情：

struct two_maps {
    std::map<int, int> foo;

    auto from_foo(int k) { return foo.find(k); }
    auto from_bar(char k) { return foo.find(k - '0'); }
};

Answer 2

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

但是如果集合以相同的顺序键入，您可以通过并行迭代两个集合并合并来加快速度。如果您的标准库具有 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 是另一种可能性，尽管它也可能有点矫枉过正。

无需重新创建匹配地图

Matching Map without Recreating

c++

dictionary

key

assignment-operator