匹配地图不重新创建

Question

说我有两个map s。这些map的值是相同的并且构造（不复制）是昂贵的。这些map的键具有不同的类型，但可以相互转换。我需要设置第一个map的内容以匹配第二个的内容，但是我必须循环遍历map s。有没有办法做到这一点？作为这方面的一个例子，我已经简化了一些更可识别的转换键，并且只使用了int s作为值。在示例中，我想设置foo的内容以匹配bar的内容。但我无法找到一种方法来做到这一点，没有循环通过map s。

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 s？

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是另一种可能性，但它也可能是矫枉过正。

Answer 2

与升压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'); } 
};