8

私は最近、boost::multi_index_container を見つけました。マルチレベル マッピングに基づいて次のように定義された同様のコンテナーの私自身の実装と比較して、彼のパフォーマンスに興味があります。

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;

キーの順序は重要ではありません。高速ルックアップは重要であり、このために私は次のようなものを使用しています:

// 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;
        ....
    }
}

どうなるか知りたい

  • the most closest configuration of boost::multi_index_container to match my implementation
  • the fastest way to search by primary key and secondary key.

I have tried to configure the template but I'm not sure if this is the best solution:

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;
4

3 に答える 3

1

同様の状況ですが、私のグループではブーストが許可されていなかったため、次の方法で実装されました。セカンダリ キーによる検索の場合、2 つではなく 1 つの検索のみが必要です。

    #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);    
    };
于 2015-07-23T06:12:40.923 に答える