O Boost Multi-index Containers
I want to introduce or even remind of such a wonderful Boost module as multi_index_container. We all know and intensively use standard STL classes for storing and accessing data as lists, vectors, maps ?, hashes. A lot has been said about them and all the features of their applications have been investigated.
Everything gets complicated when there is a need for a class for storing and accessing objects by more than one key or their combinations. Usually, starting with creating two maps or hashes, then as their number grows, everything becomes more complicated and complicated code sections arise to synchronize these hashes, inserts, deletes and renames plus it becomes quite difficult to understand the cost of a particular operation. And of course the creation of such bikes leads to a lot of bugs, the need for optimizations and so on.
Of course, everything is already invented before us and in the Boost library there is already a module for solving these problems - boost :: multi_index. A huge advantage is speed, multi_index is very fast. However, the documentation of this module is difficult to understand, for example, and newbies try to bypass this module. And of course, you can separately tell about compiler messages in case of errors when working with multi_index_container - to disassemble a long message about templates not everyone can do.
')
We will try to eliminate this gap and show simple examples for a hot start and use of this powerful tool. I will use a little along with Qt in the examples. (Just in Qt with their own template system, I often lack a primitive comparable to multi_index)
Suppose we have a small structure with fields:
multi_index provides a very convenient way to use tags / (tags in the Russian dock) for keys.
We define them directly in Rec so that we don’t crawl along the code:
We can create the following array:
We accept that our records are unique by name (name), but non-unique by address and telephone. The uniqueness of the name is also in the fact that we can not add to the array two records with the same name.
For me, this is an important convenience that the array itself will not allow the appearance of duplicates, and when accessing it I can rely on the content a priori.
Find a record by name:
If we have several entries with the phone 022
Then find all the entries with the phone 022
What if we are interested in searching by a combination of phone and address?
We can add a composite index to our array with such a block:
(Plus, don't forget to add a struct ByKey {};)
Again, we understand that for composite keys, we can use both ordered_non_unique and ordered_unique.
In this way it is very convenient to impose some additional conditions on the contents of the allowed keys and their combinations - the array itself will not allow us to add "wrong" objects.
If we want to be able to access the array at the same time as a vector, we can easily add random_access:
Then we have the ability to access as store [0] and so on, push_back ().
If we want to use an array as a hash to have quick access using the O (1) key, but slower O (log (n)) by insert / remove, then we can use hashed_unique / hashed_non_unique instead of ordered_unique / ordered_non_uniue:
You can also use hashed_uniqie / hashed_non_unique for composite keys.
On the modification of records.
Since the fields of the objects must be synchronized with the indices of the array, you cannot simply change only the field of the object. Suppose we have a need to change the phone for one of the entries. In order for our keys to be synchronized with objects, this change must be made through the functor:
We can do a search in an array by name, get an iterator by name, use project () to translate it into an iterator by phone and modify the object and array through the functor:
The use of indexes is not limited to fields - you can also use class methods, for example:
We should also mention the use of pointers:
The rest of the logic remains almost the same (only -> instead of. In a couple of places).
Plus it is worth adding for example a block
To exclude the addition of duplicate pointers.
As a result, it is possible to build very efficient data structures with interconnected information, such as smart pointers, where for each operation it is fairly easy to predict the cost of access to certain data. In a sense, multi_index_container can be viewed as a very fast database table in memory for access by predefined keys.
I hope with simple examples I give the possibility of a “hot start” to use this wonderful tool, since studying the original documentation and trying to make out compiler errors about patterns in using multi_index immediately cause great dismay for beginners and attempts to make something of their own. It turns out as always.
Everything gets complicated when there is a need for a class for storing and accessing objects by more than one key or their combinations. Usually, starting with creating two maps or hashes, then as their number grows, everything becomes more complicated and complicated code sections arise to synchronize these hashes, inserts, deletes and renames plus it becomes quite difficult to understand the cost of a particular operation. And of course the creation of such bikes leads to a lot of bugs, the need for optimizations and so on.
Of course, everything is already invented before us and in the Boost library there is already a module for solving these problems - boost :: multi_index. A huge advantage is speed, multi_index is very fast. However, the documentation of this module is difficult to understand, for example, and newbies try to bypass this module. And of course, you can separately tell about compiler messages in case of errors when working with multi_index_container - to disassemble a long message about templates not everyone can do.
')
We will try to eliminate this gap and show simple examples for a hot start and use of this powerful tool. I will use a little along with Qt in the examples. (Just in Qt with their own template system, I often lack a primitive comparable to multi_index)
Suppose we have a small structure with fields:
struct Rec { QString name, phone, addr; }; multi_index provides a very convenient way to use tags / (tags in the Russian dock) for keys.
We define them directly in Rec so that we don’t crawl along the code:
struct Rec { QString name, phone, addr; struct ByName {}; struct ByPhone {}; struct ByAddr {}; };
We can create the following array:
typedef boost::multi_index_container<Rec, indexed_by< ordered_unique< tag<Rec::ByName>, member<Rec,QString,&Rec::name> >, ordered_non_unique< tag<Rec::ByPhone>, member<Rec,QString,&Rec::phone> >, ordered_non_unique< tag<Rec::ByAddr>, member<Rec,QString,&Rec::addr> > > > Store;
We accept that our records are unique by name (name), but non-unique by address and telephone. The uniqueness of the name is also in the fact that we can not add to the array two records with the same name.
{ Store store; Rec r1 = { "Basilio Pupkinio", "022", "Neron st" }; qDebug() << "ok1" << store.insert(r1).second; // ok1 true qDebug() << "ok2" << store.insert(r1).second; // ok2 false }
For me, this is an important convenience that the array itself will not allow the appearance of duplicates, and when accessing it I can rely on the content a priori.
Find a record by name:
{ QString find_id = "Basilio Pupkinio"; typedef Store::index<Rec::ByName>::type List; const List & ls = store.get<Rec::ByName>(); List::const_iterator it = ls.find(find_id); if ( it != ls.end() ) { qDebug() << (*it).addr; // "Neron st" } }
If we have several entries with the phone 022
{ Store store; Rec r1 = { "Basilio Pupkinio", "022", "Pushkina st" }; Rec r2 = { "Vasya Pupkin", "022", "Around st" }; store.insert(r1) store.insert(r2) }
Then find all the entries with the phone 022
{ QString find_phone = "022"; Store::index<Rec::ByPhone>::type::iterator it0, it1; tie(it0,it1) = store.get<Rec::ByPhone>().equal_range(find_phone); while(it0 != it1) { qDebug() << (*it0).name; ++it0; } }
What if we are interested in searching by a combination of phone and address?
We can add a composite index to our array with such a block:
ordered_non_unique< tag<Rec::ByKey>, composite_key< Rec, member<Rec,QString,&Rec::phone>, member<Rec,QString,&Rec::addr> > >,
(Plus, don't forget to add a struct ByKey {};)
{ Rec r1 = { "Basilio Pupkinio", "022", "Pushkina st" }; Rec r2 = { "Vasya Pupkin", "022", "Around st" }; Rec r3 = { "Vasilisa Pupkina", "022", "Around st" }; store.insert(r1); store.insert(r2); store.insert(r3); { QString find_phone = "022"; QString find_addr = "Around st"; Store::index<Rec::ByKey>::type::iterator it0, it1; tie(it0,it1) = store.get<Rec::ByKey>().equal_range(make_tuple(find_phone, find_addr)); while(it0 != it1) { qDebug() << (*it0).name; ++it0; } } }
Again, we understand that for composite keys, we can use both ordered_non_unique and ordered_unique.
In this way it is very convenient to impose some additional conditions on the contents of the allowed keys and their combinations - the array itself will not allow us to add "wrong" objects.
If we want to be able to access the array at the same time as a vector, we can easily add random_access:
typedef boost::multi_index_container<Rec, indexed_by< random_access<>, ordered_unique< tag<Rec::ByName>, member<Rec,QString,&Rec::name> >, ordered_non_unique< tag<Rec::ByPhone>, member<Rec,QString,&Rec::phone> > > > Store;
Then we have the ability to access as store [0] and so on, push_back ().
If we want to use an array as a hash to have quick access using the O (1) key, but slower O (log (n)) by insert / remove, then we can use hashed_unique / hashed_non_unique instead of ordered_unique / ordered_non_uniue:
typedef boost::multi_index_container<Rec, indexed_by< hashed_non_unique< tag<Rec::ByName>, member<Rec,QString,&Rec::name> >, ordered_non_unique< tag<Rec::ByPhone>, member<Rec,QString,&Rec::phone> > > > Store; std::size_t hash_value(QString x) { return qHash(x); }
You can also use hashed_uniqie / hashed_non_unique for composite keys.
On the modification of records.
Since the fields of the objects must be synchronized with the indices of the array, you cannot simply change only the field of the object. Suppose we have a need to change the phone for one of the entries. In order for our keys to be synchronized with objects, this change must be made through the functor:
struct Rec { QString name, phone, addr; struct ByName {}; struct ByPhone {}; struct ByAddr {}; struct PhoneChange : public std::unary_function<Rec,void> { QString p; PhoneChange(const QString &_p) : p(_p) {} void operator()(Rec & r) { r.phone = p; } }; };
We can do a search in an array by name, get an iterator by name, use project () to translate it into an iterator by phone and modify the object and array through the functor:
{ Store store; Rec r1 = { "Basilio Pupkinio", "021", "Around st" }; Rec r2 = { "Vasya Pupkin", "022", "Around st" }; Rec r3 = { "Vasilisa Pupkina", "022", "Around st" }; store.insert(r1); store.insert(r2); store.insert(r3); QString find_id = "Basilio Pupkinio"; typedef Store::index<Rec::ByName>::type NList; typedef Store::index<Rec::ByPhone>::type PList; NList & ns = store.get<Rec::ByName>(); PList & ps = store.get<Rec::ByPhone>(); NList::const_iterator nit = ns.find(find_id); if ( nit != ns.end() ) { PList::const_iterator pit = store.project<Rec::ByPhone>(nit); ps.modify(pit, Rec::PhoneChange("022")); } }
The use of indexes is not limited to fields - you can also use class methods, for example:
struct Rec { QString n, phone, addr; QString name() const { return n; } struct ByName {}; struct ByPhone {}; }; typedef boost::multi_index_container<Rec, indexed_by< hashed_unique< tag<Rec::ByName>, const_mem_fun<Rec,QString,&Rec::name> >, ordered_non_unique< tag<Rec::ByPhone>, member<Rec,QString,&Rec::phone> > > > Store;
We should also mention the use of pointers:
struct Rec { QString n, phone, addr; QString name() const { return n; } struct ByName {}; struct ByPhone {}; }; typedef boost::shared_ptr<Rec> Rec_ptr; typedef boost::multi_index_container<Rec_ptr, indexed_by< hashed_non_unique< tag<Rec::ByName>, const_mem_fun<Rec,QString,&Rec::name> >, ordered_non_unique< tag<Rec::ByPhone>, member<Rec,QString,&Rec::phone> >, hashed_non_unique< tag<Rec::ByKey>, composite_key< Rec, member<Rec,QString,&Rec::phone>, member<Rec,QString,&Rec::addr> > >, ordered_non_unique< tag<Rec::ByAddr>, member<Rec,QString,&Rec::addr> > > > Store;
The rest of the logic remains almost the same (only -> instead of. In a couple of places).
{ QString find_phone = "022"; Store::index<Rec::ByPhone>::type::iterator it0, it1; tie(it0,it1) = store.get<Rec::ByPhone>().equal_range(find_phone); while(it0 != it1) { qDebug() << (*it0)->name(); ++it0; } }
Plus it is worth adding for example a block
ordered_unique< tag<Rec::ByPtr>, const_mem_fun<Rec_ptr,Rec *,&Rec_ptr::get> >,
To exclude the addition of duplicate pointers.
As a result, it is possible to build very efficient data structures with interconnected information, such as smart pointers, where for each operation it is fairly easy to predict the cost of access to certain data. In a sense, multi_index_container can be viewed as a very fast database table in memory for access by predefined keys.
I hope with simple examples I give the possibility of a “hot start” to use this wonderful tool, since studying the original documentation and trying to make out compiler errors about patterns in using multi_index immediately cause great dismay for beginners and attempts to make something of their own. It turns out as always.
Source: https://habr.com/ru/post/160009/
All Articles