Boost multi-index container vs un contenitore di mappatura multi-livello basato su std :: unordered_map (mappa delle mappe)

Question

Recentemente ho trovato boost :: multi_index_container e sono curioso delle sue prestazioni rispetto alla mia implementazione di un contenitore simile basato su mappatura multi-livello e definito come:

typedef int  Data; 
typedef uint64_t MainKey; 
typedef uint64_t SecondaryKey; 

typedef std::unordered_map<SecondaryKey, Data>  SecondaryMap; 
typedef std::unordered_map<PrimaryKey, SecondaryMap> PrimaryMap; 

L'ordine delle chiavi non è importante. La ricerca rapida è importante e per questo sto usando qualcosa come:

// find primaryKey=10 and secondaryKey=30 
PrimaryMap m; 
.... 
auto i1 = m.find(10); 
if (i1 != m.end()) 
{ 
    auto& secondary = i1->second; 
    auto i2 = secondary.find(30); 
    if (i2 != secondary.end()) 
    { 
     found = true; 
     .... 
    } 
} 

Mi piacerebbe sapere che cosa sarebbe

• la configurazione più vicina di boost :: multi_index_container per abbinare il mio implementazione
• il modo più veloce per eseguire la ricerca per chiave primaria e secondaria.

Ho provato a configurare il modello, ma non sono sicuro se questa è la soluzione migliore:

struct RecordKey 
{ 
    MainKey   mainKey; 
    SecondaryKey secondaryKey; 

    RecordKey(const MainKey mainKey, SecondaryKey secondaryKey): 
     mainKey(mainKey), 
     secondaryKey(secondaryKey) 
    {} 
}; 

struct Record: public RecordKey 
{ 
    Data data; 

    Record(const MainKey mainKey = 0, const SecondaryKey secondaryKey = 0, const Data& data = 0): 
     RecordKey(mainKey, secondaryKey), 
     data(data) 
    {} 
}; 


struct MainKeyTag {}; 
struct SecondaryKeyTag {}; 
struct CompositeKeyTag {}; 

using boost::multi_index_container; 
using namespace boost::multi_index; 

typedef boost::multi_index_container<Record, 
    indexed_by < /*random_access<>,*/ 
        hashed_non_unique<tag<MainKeyTag>,  BOOST_MULTI_INDEX_MEMBER(RecordKey, MainKey, mainKey) >, 
        hashed_non_unique<tag<SecondaryKeyTag>, BOOST_MULTI_INDEX_MEMBER(RecordKey, SecondaryKey, secondaryKey) >, 
        hashed_unique<tag<CompositeKeyTag>,  composite_key<Record, member<RecordKey, MainKey, &RecordKey::mainKey>, 
                        member<RecordKey, SecondaryKey, &RecordKey::secondaryKey> > > > > RecordContainer; 

Answer 1

Il contenitore multi-indice deve avere 3 indici:

• indice per la chiave principale: hashed - perché std::unordered_map viene assegnata, non_unique - perché più record potrebbe avere stessa chiave;
indice
• per chiave secondaria: come per la chiave principale;
• indice per chiave composta: hashed - perché std::unordered_map è sottoposto a hash, unique - perché le tuple (chiave principale, chiave secondaria) sono univoche nella struttura della mappa delle mappe .

Il contenitore è definita come:

typedef boost::multi_index_container<Record, indexed_by < 
    hashed_non_unique<tag<MainKeyTag>,  BOOST_MULTI_INDEX_MEMBER(RecordKey, MainKey, mainKey) >, 
    hashed_non_unique<tag<SecondaryKeyTag>, BOOST_MULTI_INDEX_MEMBER(RecordKey, SecondaryKey, secondaryKey) >, 
    hashed_unique<tag<CompositeKeyTag>,  
    composite_key<Record, 
     member<RecordKey, MainKey, &RecordKey::mainKey>, 
     member<RecordKey, SecondaryKey, &RecordKey::secondaryKey> > > > > RecordContainer; 

L'inserimento è:

RecordContainer c; 
c.insert(Record(10, 20, 0)); 
c.insert(Record(10, 30, 1)); 
c.insert(Record(10, 40, 2)); 

La ricerca è:

auto& index = c.get<CompositeKeyTag>(); 
auto pos = index.find(boost::make_tuple(10, 30)); // don't use std::make_tuple! 
if (pos != index.end()) 
{ 
    found = true; 
    data = pos->data; 
} 

Answer 2

Si può avere la botte piena e la moglie ubriaca, scegliendo ordinata (invece di hash indici in BMI.

C'è una bella proprietà di ordinate indici compositi che permette di interrogare dalle chiavi parziali, quindi è necessario definire solo l'indice composito di essere in grado di interrogare dal indice principale troppo:

typedef boost::multi_index_container< 
    Record, 
    indexed_by< 
     ordered_non_unique< tag<CompositeKeyTag>, 
     composite_key<Record, 
        member<RecordKey, MainKey, &RecordKey::mainKey>, 
        member<RecordKey, SecondaryKey, &RecordKey::secondaryKey> 
    > > > > RecordContainer; 

Ora è possibile sia query mainKey:

range = index.equal_range(10); 

o per composito:

range = index.equal_range(boost::make_tuple(10,30)); 

Background:

• boost::multi_index composite keys efficiency
• http://www.boost.org/doc/libs/1_56_0/libs/multi_index/doc/tutorial/key_extraction.html#composite_keys

Ecco una demo completa Live On Coliru:

#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/composite_key.hpp> 
#include <boost/multi_index/hashed_index.hpp> 
#include <boost/multi_index/ordered_index.hpp> 
#include <boost/multi_index/member.hpp> 
#include <boost/range/iterator_range.hpp> 
#include <iostream> 

using MainKey  = uint64_t; 
using SecondaryKey = uint64_t; 
using Data   = std::string; 

struct RecordKey 
{ 
    MainKey   mainKey; 
    SecondaryKey secondaryKey; 

    RecordKey(const MainKey mainKey, SecondaryKey secondaryKey): 
     mainKey(mainKey), 
     secondaryKey(secondaryKey) 
    {} 
}; 

struct Record: public RecordKey 
{ 
    Data data; 

    Record(const MainKey mainKey = 0, const SecondaryKey secondaryKey = 0, const Data& data = 0): 
     RecordKey(mainKey, secondaryKey), 
     data(data) 
    {} 

    friend std::ostream& operator<<(std::ostream& os, Record const& r) { 
     return os << " Record[" << r.mainKey << ", " << r.secondaryKey << ", " << r.data << "]"; 
    } 
}; 

struct MainKeyTag {}; 
struct SecondaryKeyTag {}; 
struct CompositeKeyTag {}; 

using boost::multi_index_container; 
using namespace boost::multi_index; 

typedef boost::multi_index_container< 
    Record, 
    indexed_by< 
     ordered_non_unique< tag<CompositeKeyTag>, 
     composite_key<Record, 
        member<RecordKey, MainKey, &RecordKey::mainKey>, 
        member<RecordKey, SecondaryKey, &RecordKey::secondaryKey> 
    > > > > RecordContainer; 


int main() 
{ 
    RecordContainer records; 
    records.insert(Record(10, 20, "12")); 
    records.insert(Record(10, 30, "13")); 
    records.insert(Record(10, 30, "13 - need not be unique!")); 
    records.insert(Record(30, 40, "34")); 
    records.insert(Record(30, 50, "35")); 
    records.insert(Record(50, 60, "56")); 
    records.insert(Record(50, 70, "57")); 
    records.insert(Record(70, 80, "78")); 

    std::cout << "\nAll records:\n----------------------------------------------------------------------\n"; 
    for (auto const& r : records) 
     std::cout << r << "\n"; 

    { 
     std::cout << "\nAll records with (main) == (10):\n----------------------------------------------------------------------\n"; 
     auto& index = records.get<0>(); 
     auto range = index.equal_range(10); 
     for (auto const& r : boost::make_iterator_range(range.first, range.second)) 
      std::cout << r << "\n"; 
    } 

    { 
     std::cout << "\nAll records with (main,secondary) == (10,30):\n----------------------------------------------------------------------\n"; 
     auto& index = records.get<0>(); 
     auto range = index.equal_range(boost::make_tuple(10,30)); 
     for (auto const& r : boost::make_iterator_range(range.first, range.second)) 
      std::cout << r << "\n"; 
    } 
} 

uscita:

All records: 
---------------------------------------------------------------------- 
Record[10, 20, 12] 
Record[10, 30, 13] 
Record[10, 30, 13 - need not be unique!] 
Record[30, 40, 34] 
Record[30, 50, 35] 
Record[50, 60, 56] 
Record[50, 70, 57] 
Record[70, 80, 78] 

All records with (main) == (10): 
---------------------------------------------------------------------- 
Record[10, 20, 12] 
Record[10, 30, 13] 
Record[10, 30, 13 - need not be unique!] 

All records with (main,secondary) == (10,30): 
---------------------------------------------------------------------- 
Record[10, 30, 13] 
Record[10, 30, 13 - need not be unique!] 

Answer 3

situazione simile, ma spinta non era permesso in il mio gruppo è così implementato nel modo seguente, in caso di ricerca per s econdary key, solo una ricerca è richiesta non due:

#include<map> 
    using namespace std; 

    template<class PrimaryKey, class SecondaryKey, class Data> 
    class MyMultiIndexedMap 
    { 
     private: 
     typedef map<PrimaryKey, Data*> PT; 
     typedef map<SecondaryKey, Data*> ST; 

     PT pri_data_; 
     ST sec_data_; 

     public: 
     bool insert(PrimaryKey pk, SecondaryKey sk, Data *data); 
     Data* findBySecondaryKey(SecondaryKey sk);  
     Data* findByPrimaryKey(PrimaryKey pk);  
    };