All geek questions in one place

Boost multi-index container vs std :: unordered_map (map map) multi-level display container

I recently found boost :: multi_index_container, and I'm interested in its performance compared to my own implementation of a similar container based on multi-level mapping and is 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;

Ordering keys is not important. A quick search is important, and for this I use 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; .... } }

I would like to know what will be

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

I tried to customize 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;
+5
source share
3 answers

A multi-index container must have 3 indexes:

  • index for the main key: hashed - since std::unordered_map hashed, non_unique - because several records can have the same key;
  • index for the secondary key: the same as for the primary key;
  • for a composite key: hashed - because std::unordered_map hashed, unique - because tuples (primary key, secondary key) are unique on the map map structure.

A container is defined as:

 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;

Insert:

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

Search:

 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
source

You can get your cake and eat it by selecting ordered (rather than hashed) indexes in BMI.

There is a nice property of ordered composite indexes that allows you to query partial keys, so you only need to define a composite index to be able to query on the main 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;

Now you can request mainKey :

 range = index.equal_range(10);

Or composite:

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

Background:

Here's the full demo of 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"; } }

Conclusion:

 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!]
+6
source

A similar situation, but boost was not allowed in my group, therefore it is implemented as follows: in the case of a search by a secondary key, only one search is required, and not two:

  #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
source

Source: https://habr.com/ru/post/1205096/

More articles:


All Articles