tr1 :: unordered_map에서 요소를 효율적으로 지우기

Question

tr1 :: unordered_map을 실험 중이므로 요소를 효율적으로 삭제하는 방법에 문제가 발생했습니다. '지우기'메서드는 반복기를 사용하여 키 또는 중 하나를 삭제할 수 있습니다. 전 은 아마도 암시 적 찾기 작업을 포함하기 때문에 후자가 더 효율적이라고 가정합니다. 반면에 인터넷에서 내 조사 은 insert() 메서드를 호출 한 후 반복자가 유효하지 않게 될 수 있음을 보여주었습니다.

내가 해시 테이블 에 넣어 물체가 충분히 같은 삽입 호출 그 긴 수명을 가지고 일반적인 실제 상황에 관심이 있어요()이 수명 동안 발생합니다. 따라서 이러한 상황에서 키에 의한 삭제는 유일한 옵션이라고 결론 내릴 수 있습니까? 어떤 방법으로 개체를보다 효율적으로 삭제할 수 있습니까? 나는 이 자주 발생하는 응용 프로그램에서만 질문이 중요하다는 것을 충분히 알고 있습니다. . 현재 진행중인 프로젝트에 적용 할 것인지 여부는 아직 알 수 없지만 이미 많은 코드가있는 경우보다 내 프로젝트를 설계하는 동안 이러한 문제에 대해 배우고 싶습니다.

Answer 1

예, insert()은 모든 반복기를 무효화 할 수 있습니다. 따라서 (암시 적) 조회를 피할 수있는 방법이 있다고 생각하지 않습니다. 희소식은 후자가 싸게 할 수있다이다.

Answer 2

순서가 지정되지 않은 컨테이너의 전체 점은 가능한 가장 빠른 검색 시간을 가져야합니다. 키로 요소를 지우는 데 걸리는 시간에 대해 걱정하는 것은 조기 최적화의 고전적인 예처럼 들립니다.

Answer 3

그것은 당신에게 좋은 거래를 중요한 경우에는 다른 이유로 반복자를 유지하고 있기 때문에, 다음 C++ 0X가 23.2.5/11,합니다 (FDIS에서 인용) std::unordered_map의 말한다 :

삽입 조작 이전에 컨테이너의 요소 수가 N 인 경우 (N + n) < z * B 인 경우 삽입 및 작업 영역 멤버는 반복기의 유효성과 관련이 없어야합니다. n은 요소 수입니다. 이 삽입되고 B는 컨테이너의 버킷 수이며 z는 컨테이너의 최대 부하 계수 입니다.

나는 tr1 사양이 동일한 보장이 있는지 여부를 확인하지 않은,하지만 예상 된 구현을 기반으로 매우 논리적입니다.

이 보증을 사용할 수 있다면 반복자를 보호 할 수 있습니다. Mark가 말했듯이, unordered_map에서 조회가 빠르다고합니다. 반복기보다는 키를 유지하는 것이 반복자가 아닌 vector에 색인을 유지하는 것보다 나쁘지 만 map에 해당하는 것보다 낫습니다.