C++地圖擦除（開始，結束）不起作用

Question

我想通過使用C++ API來實現我的生活。通過map.erase(begin, end)方法，我希望刪除[begin, end)之間的所有條目。所以我的方法實現了，下面定義了 TabletKey。

79 void 
80 ObjectFinder::flush(uint64_t tableId) { 
81 
82  RAMCLOUD_TEST_LOG("flushing object map"); 
83  std::map<TabletKey, ProtoBuf::Tablets::Tablet>::iterator lower; 
84  std::map<TabletKey, ProtoBuf::Tablets::Tablet>::iterator upper; 
85  std::map<TabletKey, ProtoBuf::Tablets::Tablet>::iterator it; 
86  KeyHash keyHash = Key::getHash(tableId, "", 0); 
87  TabletKey key(tableId, keyHash); 
88 
89  std::cout << "before the loop" << std::endl; 
90  for (it = tableMap.begin(); it != tableMap.end(); it++) { 
91   std::cout << it->first.first << std::endl; 
92  } 
93  lower = tableMap.lower_bound(key); 
94  upper = tableMap.upper_bound(key); 
95  
108  tableMap.erase(lower, upper); 
109  std::cout << "After the erase" << std::endl; 
110  for (it = tableMap.begin(); it != tableMap.end(); it++) { 
111   std::cout << it->first.first << std::endl; 
112  } 
    } 

然而，id值不會被刪除：

id = 99 
before the loop 
1 
99 
After the erase 
1 
99 

我寫我自己的comparison功能，重載默認的方法：

35 typedef std::pair<uint64_t, KeyHash> TabletKey; 
36 
37 /* 
38 * The object CmpTabletKey is used to override the default comparison 
39 * definition from the C++ Map. 
40 */ 
41 struct CmpTabletKey { 
42  bool operator()(const TabletKey& key1, const TabletKey& key2) const { 
43   return ((key1.first < key2.first) || 
44     (key1.first == key2.first && key1.second < key2.second)); 
     } 
    } 

可能有人給我一個線索爲什麼erase無法按預期工作？我是否也必須將CmpTabletKey的定義也定義爲iterator？ 更新 這是我的舊的實現：它工作得很好，做我想做什麼： 然而，這是一個O（n）的方法，我希望有一個更快的實現：

117  std::map<TabletKey, ProtoBuf::Tablets::Tablet>::iterator it; 
118  for (it = tableMap.begin(); it != tableMap.end();) { 
119   if (tableId == it->first.first) { 
120    tableMap.erase((it++)->first); 
121   } else { 
122    ++it; 
123   } 
124  } 

Answer 1

從如何你的迭代器被定義了，看起來你並沒有用自定義的比較器來創建映射。

我認爲地圖應該創建爲：

std::map<TabletKey, ProtoBuf::Tablets::Tablet, CmpTabletKey > tableMap; //CmpTabletKey is passed as the comparator type 

And your iterators become: 
std::map<TabletKey, ProtoBuf::Tablets::Tablet, CmpTabletKey>::iterator lower; 
std::map<TabletKey, ProtoBuf::Tablets::Tablet, CmpTabletKey>::iterator upper; 
std::map<TabletKey, ProtoBuf::Tablets::Tablet, CmpTabletKey>::iterator it; 

如果不指定CmpTabletKey作爲類型，你的地圖將使用默認的比較。

Answer 2

映射容器最多隻能保存每個鍵的一個副本，我認爲你想要做的是擦除TableID相同的所有元素，但是你已經使用一個對來排列元素，所以你必須迭代所有元素地圖並選擇符合謂詞的元素。

如果可以的話，你應該使用std :: multimap中創造只有表格ID是涉及到比較器。

編輯：

，所以你要刪除具有特定ID的所有元素。但實際上你的地圖所尋找的是一個具有特定tableID和特定keyHash的元素。

你有幾種解決方案，其中之一是O（n）（你有解決方案），另一種選擇，就是用另一種數據結構，能夠滿足您的requiriments。我認爲你應該使用multimap或unordered_multimap（hast_table）。

Answer 3

這裏有一個簡單的例子，應該幫助你實現你的目標。

讓我們做一個地圖有一對密鑰：

#include <map> 
#include <utility> 

typedef std::pair<int, int> key_type; 

std::map<key_type, void *> mymap = { { { 1, 2}, NULL } 
            , { { 5, 0}, NULL } 
            , { { 5, 7}, NULL } 
            , { { 6, 3}, &mymap } }; 

現在假設我們想從mymap其第一關鍵部分是等於5刪除所有元素。這裏有一個解決方案：

for (auto it = mymap.begin(); it != mymap.end();) 
{ 
    if (it->first.first == 5) { mymap.erase(it++); } 
    else      { ++it;    } 
} 

Answer 4

取2 ...因爲你原來的甚至不考慮key.second價值，我想這個問題是在CmpTabletKey，但這次不同的原因。在功能上等同比較運營商原來的實施：

35 typedef std::pair<uint64_t, KeyHash> TabletKey; 
36 
37 /* 
38 * The object CmpTabletKey is used to override the default comparison 
39 * definition from the C++ Map. 
40 */ 
41 struct CmpTabletKey { 
42  bool operator()(const TabletKey& key1, const TabletKey& key2) const { 
43   return (key1.first < key2.first); 
     } 
    } 

我懷疑，因爲當前的實現還考慮到了.second值，然後從原來的改變的功能。清除同一個異議的下限和上限之間的所有內容基本上會清除所有與該對象等效的鍵，但是您有KeyHash keyHash = Key::getHash(tableId, "", 0);和TabletKey key(tableId, keyHash);，但是key的鍵值並不在您的映射中。您的比較運算符也是，因此它不會評估.first值的等價性。

同時，有必要比較中是嚴格的，因爲我相信的地圖搜索基本上說「如果一個！< B和B！< A，則A == B」。這意味着你將無法正確插入值，因爲等價也不會在乎.second。由於這些相互矛盾的定義，我認爲您目前的實施不會奏效。

編輯：Derp。試試這個：

79 void 
80 ObjectFinder::flush(uint64_t tableId) { 
81 
82  RAMCLOUD_TEST_LOG("flushing object map"); 
83  std::map<TabletKey, ProtoBuf::Tablets::Tablet>::iterator lower; 
84  std::map<TabletKey, ProtoBuf::Tablets::Tablet>::iterator upper; 
85  std::map<TabletKey, ProtoBuf::Tablets::Tablet>::iterator it; 
86  //KeyHash keyHash = Key::getHash(tableId, "", 0); 
     TabletKey keylower(tableId, KeyHash::MINIMUM); 
     TabletKey keyupper(tableId, KeyHash::MAXIMUM); 
87  //TabletKey key(tableId, keyHash); 
88 
89  std::cout << "before the loop" << std::endl; 
90  for (it = tableMap.begin(); it != tableMap.end(); it++) { 
91   std::cout << it->first.first << std::endl; 
92  } 
93  lower = tableMap.lower_bound(keylower); 
94  upper = tableMap.upper_bound(keyupper); 
95  
108  tableMap.erase(lower, upper); 
109  std::cout << "After the erase" << std::endl; 
110  for (it = tableMap.begin(); it != tableMap.end(); it++) { 
111   std::cout << it->first.first << std::endl; 
112  } 
    } 

哪裏KeyHash::MINIMUM是最低的密鑰散列值的靜態常量和KeyHash::MAXIMUM爲最大。使用你當前的比較結構。