boost.intrusive 및 unordered_map

Question

나는 침입 UNORDERED_MAP를 사용하려고합니다. 어떤 이유로 든 라이브러리에는 UnordeD_SET 만 있습니다. 침입 해시 테이블이 있지만 동일한 기능을 가지고 있는지 확실하지 않으며 동일한 인터페이스가 없습니다.
내가 틀렸고 unordered_map 링크를 놓쳤습니까?
내가 없다면 내가 하나를 구현하는 데 도움이되는 자습서가 있습니까?

Answer 1

흥미로운 질문입니다. boost.intrusive는 주문 또는 순서가없는 맵 인터페이스를 제공하지 않는 것 같습니다. 순서 (레드 블랙 나무, AVL 나무, 스플레이 트리) 및 변수 (해시 타이블)로 잘 작동하는 구현 유형이 많이 있습니다. 그러나지도는없고 왜 그런지 말할 수 없었습니다.

내가 볼 수있는 두 가지 선택이 있습니다.

1. 그냥 사용하십시오 hashtable: 변절되지 않은 컨테이너는 해시 테이블로 구현됩니다 (그리고 그들이 그렇지 않은 유일한 이유 ~라고 불리는 hash_map 이미 해당 이름을 사용하여 기존 라이브러리와의 이름 충돌을 피하는 것입니다). 일을 끝내고 싶다면 작동합니다.
2. 당신이 정말로 자신의 구현을 원한다면, 당신은 boost.intrusive 's의 인터페이스 설명을 살펴보고 싶습니다. UNORDERED_SET. 나는 구현을 보지 않았지만 하나 이상의 트리 유형 주위에 래퍼입니다. std::set 그리고 std::map 둘 다 일반적으로 레드 블랙 트리 주변의 포장지로 구현됩니다 (GCC, MSVC 및 Apache의 STDCXX에서 본 모든 표준 라이브러리 구현에서). 또한 libstdc ++가 자신의 트리 구현을 어떻게 감싸는지를 취하십시오. <map> 그리고에서 <set>. 그것은 많은 보일러 플레이트이며, 많은 것이 지루하지만 두 가지 유형은 거의 모든 작업을 나무에 연기합니다. Boost.intrusive 's에서 거의 확실하게 일어나고 있습니다 unordered_set. 맵과 설정 인터페이스의 차이점을 살펴보고 수정의 기초로 사용해야합니다. unordered_set ~ 안으로 unordered_map.

나는 후자를했다. 그것은 지루한 측면에 약간이며, 나는 그것을 위해 단위 테스트를 작성하는 것이 좋습니다 (또는 libstdc ++ 또는 boost.intrusive와 함께 제공되는 것들을 훔치는 것이 좋습니다). 그러나 가능합니다. 또한 SGI에서 세트 및 맵에 대한 요구 사항 문서를 읽는 것이 좋습니다.세트, 지도) 또는 libstdc ++

업데이트: 그들이 맵을 수행하지 않는 이유를 깨달았습니다. 침입 컨테이너는 저장하는 값 유형에 데이터 구조에 대한 노드 정보를 포함시켜야합니다. 지도의 경우 두 값 모두에 대해이 작업을 수행해야합니다. 그리고 열쇠. 이것이 불가능한 것이 아니라 map 사용 같은 내부 유형 sets do. 그러나 이러한 내부 유형은 단지 가지고 있습니다 하나 value_type 변수 : 키와 값을 저장하려면 키와 값을 해당 변수에 복사하고 노드에 저장합니다. 침입 유형 (즉, 복사없이)으로이를 수행하려면 해당 구현 유형을 세트와 호환되지 않도록 수정해야합니다. 키와 값에 대한 참조를 저장해야합니다. 갈라져. 따라서 사용하려면 사용하는 구현도 수정해야합니다 (아마도 hashtable). 다시 불가능하지는 않지만 도서관 디자이너는 심각한 코드 복제를 피하려고 노력할 가능성이 높으므로 간단한 구현 방법이 없으면지도를 남겨두기로 결정했을 가능성이 높습니다.

말이 돼?

Answer 2

이 질문이 요청 된 지 오래되었지만 여기에 오는 사람들은 사용 방법에 관심이 있어야한다고 생각합니다. unordered_set 지도로. 해결책은 사용하는 것입니다 고급 삽입 방법: 하나는 키와 그 가치를 동일하게 저장해야합니다. value_type, 사용하여 삽입하십시오 insert_check 그리고 insert_commit.