C++ map 지우기 (시작, 끝) 작동하지 않음

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

방법에서을 반복자가 정의되어 있으면 사용자 정의 콤퍼레이터를 사용하여 맵을 생성하지 않는 것처럼 보입니다. 당신이 유형으로 CmpTabletKey을 지정하지 않으면

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; 

,지도 기본 비교기를 사용합니다 :

나는대로지도를 생성 할 전망이다.

Answer 2

맵 컨테이너는 각 키의 복사본을 하나만 사용하므로 TableID가 같은 모든 요소를 ​​지우지만 쌍을 사용하여 요소를 정렬했기 때문에 모든 요소를 ​​지우는 것이 좋습니다. 술어를 충족시키는 요소를 선택하고 맵핑하십시오.

가능한 경우 std :: multimap을 사용하고 TableID 만 포함 된 비교자를 만들어야합니다.

편집 : 그럼 당신이 특정 ID를 가진 모든 요소를 ​​지울 수 있도록

. 그러나 실제로 맵에서 찾고자하는 것은 특정 tableID와 특정 keyHash가있는 요소입니다.

몇 가지 솔루션이 있습니다. 하나는 O (n) (솔루션)이며 다른 옵션은 사용자의 요구 사항을 충족하는 다른 데이터 구조를 사용하는 것입니다. 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 } }; 

이제 우리는 그 처음 핵심 5 같다 mymap에서 모든 요소를 ​​제거한다고 가정합니다.여기에 하나의 해결책 : 원래 심지어 key.second 값을 고려하지 않기 때문에

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

Answer 4

이 난 문제가 CmpTabletKey에 있다고 생각 ... (2)를 가지고 있지만, 다른 이유는이 시간. 원래 구현에 기능적으로 동등한 비교 연산자는 다음과 같습니다

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, 다음 ==의 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 가장 낮은 키 해시 값의 const 정적 인

하고 KeyHash::MAXIMUM가 최대입니다. 현재 비교 구조체를 사용하십시오.