C++ Bimap 왼쪽 unordered_map 오른쪽 정렬 된 가변 멀티 맵

Question

내 프로젝트에 다음 데이터 구조를 구현해야합니다. 나는 (만 증가 사실에) 시간이 지남에 따라 변경 될 수 있습니다 내가 연결된 카운터를 저장할 때마다 포인터를 들어

uint64_t 

에

const MyClass* 

의 관계를 가지고있다. 이것은 문제가되지 않을 것이며 단순히 std :: map에 저장할 수 있습니다. 문제는 내가 가장 높은 값을 가진 포인터에 빠른 액세스가 필요하다는 것입니다.

그래서 결론에 boost :: bimap을 사용하게되었습니다. 그것이 정의 내 프로젝트에 대해 다음과

typedef boost::bimaps::bimap< 
     boost::bimaps::unordered_set_of< const MyClass* >, 
     boost::bimaps::multiset_of< uint64_t, std::greater<uint64_t> > 
> MyBimap; 
MyBimap bimap; 

한번 삽입 된 한 쌍의 uint64_t을 수정할 수 없습니다 바로 것을이 잘 작동,하지만 내가? 설명서에 따르면 multiset_of는 상수이기 때문에 bimap에서 쌍의 값을 변경할 수는 없습니다.

어떻게해야합니까? 이 bimap에서 하나의 키 값을 변경하는 올바른 방법은 무엇입니까? 아니면이 문제를 해결할 수있는 더 간단한 데이터 구조가 있습니까?

Answer 1

간단한 손으로 만든 솔루션입니다.

내부적으로는 오브젝트 포인터에 의해 인덱싱 된 카운트를 저장하는 맵과 반복적으로 반복되는 반복자를 포인 티 수의 내림차순으로 저장합니다.

개수를 수정할 때마다 색인을 다시 만들어야합니다. 이 작업은 단편적이지만, 요구 사항에 따라 배치 업데이트로 처리 할 수 ​​있습니다.

C++ 17에는 세트 및 맵에 대해 제안 된 splice 조작이 있으므로 매우 빠르게 색인을 다시 작성할 수 있습니다.

#include <map> 
#include <set> 
#include <vector> 

struct MyClass { }; 


struct store 
{ 

    std::uint64_t add_value(MyClass* p, std::uint64_t count = 0) 
    { 
     add_index(_map.emplace(p, count).first); 
     return count; 
    } 

    std::uint64_t increment(MyClass* p) 
    { 
     auto it = _map.find(p); 
     if (it == std::end(_map)) { 
      // in this case, we'll create one - we could throw instead 
      return add_value(p, 1); 
     } 
     else { 
      remove_index(it); 
      ++it->second; 
      add_index(it); 
      return it->second; 
     } 
    } 

    std::uint64_t query(MyClass* p) const { 
     auto it = _map.find(p); 
     if (it == std::end(_map)) { 
      // in this case, we'll create one - we could throw instead 
      return 0; 
     } 
     else { 
      return it->second; 
     } 
    } 

    std::vector<std::pair<MyClass*, std::uint64_t>> top_n(std::size_t n) 
    { 
     std::vector<std::pair<MyClass*, std::uint64_t>> result; 
     result.reserve(n); 
     for (auto idx = _value_index.begin(), idx_end = _value_index.end() ; 
      n && idx != idx_end ; 
      ++idx, --n) { 
      result.emplace_back((*idx)->first, (*idx)->second); 
     } 
     return result; 
    } 

private: 
    using map_type = std::map<MyClass*, std::uint64_t>; 
    struct by_count 
    { 
     bool operator()(map_type::const_iterator l, map_type::const_iterator r) const { 
      // note: greater than orders by descending count 
      return l->second > r->second; 
     } 
    }; 
    using value_index_type = std::multiset<map_type::iterator, by_count>; 

    void add_index(map_type::iterator iter) 
    { 
     _value_index.emplace(iter->second, iter); 
    } 

    void remove_index(map_type::iterator iter) 
    { 
     for(auto range = _value_index.equal_range(iter); 
      range.first != range.second; 
      ++range.first) 
     { 
      if (*range.first == iter) { 
       _value_index.erase(range.first); 
       return; 
      } 
     } 

    } 

    map_type _map; 
    value_index_type _value_index; 
};