Увеличить многоиндексных контейнер против многоуровневого сопоставления контейнер, основанные на СТД::неупорядоченный карту (карту карты)

Недавно я нашел 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;
        ....
    }
}

Я хотел бы знать, что будет

  • наиболее близкая конфигурация boost:: multi_index_container для соответствия моей реализации
  • в самый быстрый способ поиска по первичному и вторичному ключам.

Я пытался настроить шаблон, но я не уверен, что это лучшее решение:

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;
3 7
c++ unordered-map

3 ответа:

Вы можете получить свой торт и съесть его тоже, выбрав упорядоченные (вместо хэшированных) индексы в ИМТ.

Есть хорошее свойство упорядоченных составных индексов, которое позволяет запрашивать по частичным ключам, поэтому вам нужно только определить составной индекс, чтобы иметь возможность запрашивать и по главному индексу: 

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;

Теперь вы можете либо запросить по mainKey: 

range = index.equal_range(10);

Или составным: 

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

Предыстория:

Вот полная демонстрация жить на Колиру:

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

Вывод: 

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!]
8

Контейнер с несколькими индексами должен иметь 3 индекса:

  • индекс для главного ключа: hashed - потому что std::unordered_map хэшируется, non_unique - потому что несколько записей могут иметь один и тот же ключ;
  • индекс для вторичного ключа: такой же, как для основного ключа;
  • индекс для составного ключа: hashed - потому что std::unordered_map хэшируется, unique - потому что кортежи (главный ключ, вторичный ключ) уникальны в карте карт структура.

Контейнер определяется следующим образом: 

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;

Вставка это: 

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

Поиск выглядит следующим образом: 

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

Аналогичная ситуация, но boost не был разрешен в моей группе, поэтому реализован следующим образом, в случае поиска по вторичному ключу требуется только один поиск, а не два: 

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