0

我试图通过使用 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没有按预期工作吗？我是否也必须给出 to 的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     }
4

4 回答 4

4

From how your iterators are defined, it appears you are not creating the map with your custom-defined comparator.

I believe the map should be created as:

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;

If you don't specify CmpTabletKey as the type, your map will use the default comparator.

于 2013-08-01T22:32:36.427 回答
3

地图容器最多保留每个键的一个副本，我认为您要做的是擦除 TableID 相同的所有元素，但是您已经使用一对对元素进行了排序，因此您必须迭代所有地图并选择满足谓词的元素。

如果可以，您应该使用 std::multimap 并创建一个只涉及 TableID 的比较器。

编辑：

好吧，所以您想删除具有特定 ID 的所有元素。但实际上，您的地图正在寻找的是具有特定 tableID 和特定 keyHash 的元素。

您有几种解决方案，其中之一是 O(n)（您拥有的解决方案），另一种选择是使用另一种满足您要求的数据结构。我认为您应该使用 multimap 或 unordered_multimap (hast_table)。

于 2013-08-01T22:52:28.300 回答
1

这是一个简化的示例，可以帮助您实现目标。

让我们用一对键制作一张地图：

#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;              }
}
于 2013-08-01T23:16:53.030 回答
0

取 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);and TabletKey key(tableId, keyHash);，但键值key不是专门在您的地图中。您的比较运算符过于具体，因此它不会仅评估值的等价性.first。

同时，比较有必要那么严格，因为我相信地图搜索基本上是说“如果 A ！< B 和 B ！< A，那么 A == B”。这意味着您将无法正确插入值，因为等价也不关心.second. 由于这些冲突的定义，我认为您当前的实现不会起作用。

编辑：德普。尝试这个：

 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是最大值。使用您当前的比较结构。

于 2013-08-01T23:37:56.823 回答