Boost 多索引容器与基于 std::unordered_map(映射映射)的多级映射容器 [英] Boost multi-index container vs a multi-level mapping container based on std::unordered_map (map of maps)

问题描述

我最近发现了 boost::multi_index_container，我很好奇他的性能与我自己的基于多级映射的类似容器的实现相比，并定义为:

I recently found boost::multi_index_container and I'm curious about his performance compared to my own implementation of a similar container based on multi-level mapping and defined as:

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;

键的顺序并不重要.快速查找很重要，为此我使用了类似的东西:

The key ordering is not important. The fast lookup is important and for this I'm using something like:

// 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 配置以匹配我的实现
• 按主键和辅助键进行搜索的最快方法.

我已尝试配置模板，但我不确定这是否是最佳解决方案:

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;

推荐答案

多索引容器必须有3个索引:

The multi-index container must have 3 indexes:

• 主键的索引:hashed - 因为 std::unordered_map 是散列的，non_unique - 因为多个记录可以有相同的键；
• 次键索引:与主键相同；
• 复合键的索引:hashed - 因为 std::unordered_map 是散列的，unique - 因为元组(主键，辅助键) 在地图中是唯一的结构.

• index for main key: hashed - because std::unordered_map is hashed, non_unique - because multiple records could have same key;
• index for secondary key: same as for the main key;
• index for composite key: hashed - because std::unordered_map is hashed, unique - because the tuples (main key, secondary key) are unique in the map of maps structure.

容器定义为:

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

这篇关于Boost 多索引容器与基于 std::unordered_map(映射映射)的多级映射容器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！