2016-07-13 12 views
1

Ich muss die folgende Datenstruktur für mein Projekt implementieren. Ich habe eine Beziehung vonC++ Bimap Left unordered_map Richtig sortierte veränderbare Multimap

const MyClass* 

zu

uint64_t 

Für jeden Zeiger ich mit ihm verbunden einen Zähler speichern möchten, die im Laufe der Zeit geändert werden kann (in der Tat nur erhöht). Das wäre kein Problem, ich könnte es einfach in einer std :: map speichern. Das Problem ist, dass ich schnellen Zugriff auf die Zeiger benötige, die die höchsten Werte haben.

Deshalb kam ich zu dem Schluss, einen boost :: bimap zu verwenden. Es definiert ist, folgt für mein Projekt:

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

Dies würde funktionieren, aber bin ich richtig, dass ich nicht die uint64_t auf Paar ändern kann, die einmal eingeführt wurden? Die Dokumentation besagt, dass multiset_of konstant ist und daher kann ich den Wert eines Paares im Bimap nicht ändern.

Was kann ich tun? Was wäre der richtige Weg, um den Wert eines Schlüssels in diesem Bimap zu ändern? Oder ist für dieses Problem eine einfachere Datenstruktur möglich?

+0

Klingt wie eine Prioritätswarteschlange. –

+0

Stellen Sie sich den Code vor, der zur Aufrechterhaltung der Indexintegrität erforderlich wäre, wenn der Schlüssel der rechten Seite veränderbar wäre ... –

+0

können Sie die Prioritäten in einer Prioritätswarteschlange ändern? und ist es möglich, auf die ersten N-Werte zuzugreifen? –

Antwort

0

Hier ist eine einfache handgemachte Lösung.

Intern speichert es eine Karte, um die durch den Objektzeiger indizierten Zählerstände zu speichern, und eine weitere Mehrfachgruppe von Iteratoren, geordnet nach absteigender Zählung ihrer Spitzen.

Wenn Sie eine Zählung ändern, müssen Sie sie erneut indizieren. Ich habe dies stückchenweise gemacht, aber Sie könnten es je nach Bedarf als Batch-Update durchführen.

Beachten Sie, dass in C++ 17 eine Operation splice für Sätze und Karten vorgeschlagen wird, die die Neuindizierung extrem schnell machen würde.

#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; 
};