C++ Multimap操作

Question

我已經創建了一個multimap，因爲我有重複鍵。但是我想要做一個有效的操作，這樣我就可以生成一個新的multimap，並且隨後有更高的鍵對齊。這就是我的意思是：

這是我有：

key  values 
11   qwer 
11   mfiri 
21   iernr 
21   ghfnfjf 
43   dnvfrf 

這是我想才達到

key  values 
11   qwer,iernr 
11   mfiri,iernr 
21   iernr,dnvfrf 
21   ghfnfjf,dnvfrf 
43   dnvfrf 

我有大約10萬個條目是什麼，所以我尋找的東西有效。

上面的值「qwer，iernr」是一個字符串。

Answer 1

看起來像直接的方式將工作正常。地圖元素將按升序排列（假設比較運算符適合您）。因此，只需經過相同的範圍並在範圍之後使用元素的值修改它們即可完成您想要的操作。

克隆映射（如果您需要原始的），取第一個元素，獲取equal_range()作爲其鍵值，修改值爲第二個迭代器的值（除非它是最後一個）。獲取equal_range()作爲第二個迭代器的關鍵字。重複。

Answer 2

這裏有一個簡單的方法來做到這一點：

auto cur = map.begin(); 
auto next = map.upper_bound(cur->first); 

for(; next != map.end(); next = map.upper_bound(cur->first)) 
{ 
    for(; cur != next; ++cur) 
    { 
     cur->second += ", "; 
     cur->second += next->second; 
    } 
} 

...給出std::multimap<int, std::string> map;

然而，任何操作轉換1,000萬名以上的元素不會是超級快。

Answer 3

同意尤金！關於equal_range（）的信息，請參閱以下參考資料 stl::multimap - how do i get groups of data?

Answer 4

要做到這一點，您需要簡單地遍歷地圖，同時按順序構建新地圖。

可以在兩個層面做到這一點：

for (auto it=map.cbegin(); it != map.cend();) 
{ 
    // The inner loop is over all entries having the same key 
    auto next_key_it=find_next_key_after(it); 
    for (; it != next_key_it; ++it) { 
     new_map.emplace_hint(new_map.end(), it->first, new_value(it->second, next_key_it)); 
    } 
} 

的NEW_VALUE功能（或lambda）確實值轉換（或沒有，如果第二個參數是map.end（））。

find_next_key_after（it）函數返回與map.upper_bound（it-> first）相同的值，但也可以作爲具有不同鍵的第一個條目的線性搜索來實現。

這取決於您的（預期的）密鑰分配，要使用 - 如果密鑰重複次數有限，線性搜索更好;如果不同密鑰的數量有限，並且密鑰範圍大，那麼upper_bound可能會更好。對於保證的複雜度，線性搜索更好：整個算法具有O（n）複雜度。這是一樣有效的，你可以得到。