匹配地圖不重新創建

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