November 24, 2012 at 01:04O Boost Multi-index Containers
I want to introduce or even remind you of such a wonderful Boost module as multi_index_container. We all know and intensively use standard STL classes for storing and accessing data like lists, vectors, maps ?, hashes. A lot has already 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 to store and access objects using more than one key or their combinations. Usually they start by creating two maps or hashes, then with an increase in their number everything becomes more complicated and there are more complicated code sections for synchronizing these hashes, inserting, deleting and renaming plus it becomes quite difficult to understand the cost of this or that operation. And of course, the creation of such bicycles leads to a large number of bugs, the need for optimizations, and so on.
Of course, everything has already been invented before us and the Boost library already has 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, let's say, difficult to understand, and beginners try to bypass this module. And of course, we can separately say about compiler messages for errors when working with multi_index_container - not everyone can figure out long message about templates.
We will try to fill 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)
Let's say we have a small structure with fields:
multi_index gives a very convenient opportunity to use tags / (tags in the Rus dock) for keys.
We define them directly in Rec so that they do not creep along the code:
We can create the following array:
We accept that our records are unique by name (name), but not unique by address and phone. The uniqueness of the name is also that we cannot add two records with the same name to the array.
For me, this is an important convenience that the array itself will not allow duplicates to appear, and when I access it, I can rely on the correctness of the contents a priori.
Find the entry by name:
If we have several records with phone 022
Then find all entries with phone 022
What if we are interested in searching by combination of phone and address?
We can add a composite index to our array with this block:
(Plus do not forget to add the label 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 permitted keys and their combinations - the array itself will not allow us to add “wrong” objects.
If we want the ability to have access to 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], etc., push_back ().
If we want to use the array as a hash in order to have quick access by the O (1) key, but slower than 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.
About modification of records.
Since the fields of the objects must be synchronized with the indices of the array, you cannot just change only the field of the object. Suppose we have a need to change the phone for one of the entries. For our keys to be synchronized with objects, this change must be done through a functor:
We can do an array search by name, get an iterator by name, use project () to translate it into an iterator by phone and modify the object and array through a 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:
All the rest of the logic remains almost the same (only -> instead of. In a couple of places).
Plus it’s worth adding for example a block
To exclude the addition of duplicate pointers.
As a result, it is possible to construct data structures that are very efficient in access and interconnected, for example by smart pointers, where for each operation it is quite easy to predict the costs of accessing one or another data. In a sense, multi_index_container can be thought of as a very fast in-memory database table for access using predefined keys.
I hope with simple examples I give a hot start to the use of this wonderful tool, since studying the original documentation and trying to parse compiler errors about templates in using multi_index immediately causes great dismay for beginners and attempts to do something different. It turns out as always.
Everything gets complicated when there is a need for a class to store and access objects using more than one key or their combinations. Usually they start by creating two maps or hashes, then with an increase in their number everything becomes more complicated and there are more complicated code sections for synchronizing these hashes, inserting, deleting and renaming plus it becomes quite difficult to understand the cost of this or that operation. And of course, the creation of such bicycles leads to a large number of bugs, the need for optimizations, and so on.
Of course, everything has already been invented before us and the Boost library already has 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, let's say, difficult to understand, and beginners try to bypass this module. And of course, we can separately say about compiler messages for errors when working with multi_index_container - not everyone can figure out long message about templates.
We will try to fill 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)
Let's say we have a small structure with fields:
struct Rec { QString name, phone, addr; };multi_index gives a very convenient opportunity to use tags / (tags in the Rus dock) for keys.
We define them directly in Rec so that they do not creep 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, member
>,
ordered_non_unique<
tag, member
>,
ordered_non_unique<
tag, member
>
>
> Store; We accept that our records are unique by name (name), but not unique by address and phone. The uniqueness of the name is also that we cannot add two records with the same name to the array.
{
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 duplicates to appear, and when I access it, I can rely on the correctness of the contents a priori.
Find the entry by name:
{
QString find_id = "Basilio Pupkinio";
typedef Store::index::type List;
const List & ls = store.get();
List::const_iterator it = ls.find(find_id);
if ( it != ls.end() ) {
qDebug() << (*it).addr; // "Neron st"
}
} If we have several records with 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 entries with phone 022
{
QString find_phone = "022";
Store::index::type::iterator it0, it1;
tie(it0,it1) = store.get().equal_range(find_phone);
while(it0 != it1) { qDebug() << (*it0).name; ++it0; }
} What if we are interested in searching by combination of phone and address?
We can add a composite index to our array with this block:
ordered_non_unique<
tag, composite_key<
Rec,
member,
member
>
>, (Plus do not forget to add the label 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::type::iterator it0, it1;
tie(it0,it1) = store.get().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 permitted keys and their combinations - the array itself will not allow us to add “wrong” objects.
If we want the ability to have access to the array at the same time as a vector, we can easily add random_access:
typedef boost::multi_index_container,
ordered_unique<
tag, member
>,
ordered_non_unique<
tag, member
>
>
> Store; Then we have the ability to access as store [0], etc., push_back ().
If we want to use the array as a hash in order to have quick access by the O (1) key, but slower than 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, member
>,
ordered_non_unique<
tag, member
>
>
> Store;
std::size_t hash_value(QString x) { return qHash(x); } You can also use hashed_uniqie / hashed_non_unique for composite keys.
About modification of records.
Since the fields of the objects must be synchronized with the indices of the array, you cannot just change only the field of the object. Suppose we have a need to change the phone for one of the entries. For our keys to be synchronized with objects, this change must be done through a functor:
struct Rec {
QString name, phone, addr;
struct ByName {};
struct ByPhone {};
struct ByAddr {};
struct PhoneChange : public std::unary_function {
QString p; PhoneChange(const QString &_p) : p(_p) {}
void operator()(Rec & r) { r.phone = p; }
};
}; We can do an array search by name, get an iterator by name, use project () to translate it into an iterator by phone and modify the object and array through a 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::type NList;
typedef Store::index::type PList;
NList & ns = store.get();
PList & ps = store.get();
NList::const_iterator nit = ns.find(find_id);
if ( nit != ns.end() ) {
PList::const_iterator pit = store.project(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, const_mem_fun
>,
ordered_non_unique<
tag, member
>
>
> 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_ptr;
typedef boost::multi_index_container, const_mem_fun
>,
ordered_non_unique<
tag, member
>,
hashed_non_unique<
tag, composite_key<
Rec,
member,
member
>
>,
ordered_non_unique<
tag, member
>
>
> Store; All the rest of the logic remains almost the same (only -> instead of. In a couple of places).
{
QString find_phone = "022";
Store::index::type::iterator it0, it1;
tie(it0,it1) = store.get().equal_range(find_phone);
while(it0 != it1) { qDebug() << (*it0)->name(); ++it0; }
} Plus it’s worth adding for example a block
ordered_unique<
tag, const_mem_fun
>, To exclude the addition of duplicate pointers.
As a result, it is possible to construct data structures that are very efficient in access and interconnected, for example by smart pointers, where for each operation it is quite easy to predict the costs of accessing one or another data. In a sense, multi_index_container can be thought of as a very fast in-memory database table for access using predefined keys.
I hope with simple examples I give a hot start to the use of this wonderful tool, since studying the original documentation and trying to parse compiler errors about templates in using multi_index immediately causes great dismay for beginners and attempts to do something different. It turns out as always.