Note: this is an introduction to / overview of Boost MultiIndex. It is not intended to be in-depth.
So. Containers. 99% of the time, std::vector, out of all the choices you have in the STL, is the right choice. The next most obvious is std::map if you need to “index” access to data: for example if you store 1,000,000 phone numbers and you want to quickly find one given a name, a std:map will give you “indexed” access – you look up your data in O(log n) time (or potentially quicker if you’re using a std::unordered_map) as opposed to O(n) time for an unsorted std::vector. (Obviously these are theoretical complexities – see a previous post which advocates actual benchmarking, as processor cache and branch prediction can have a huge effect).
But what if you want to treat your collection a bit more like a database table, with perhaps one “primary key” and several other indexed “fields”?
Imagine you’ve got a struct like this:
struct Person
{
std::string Name,
unsigned int Age,
std::string PostCode // "Zip" code
};
If you created a std::map of Person, “indexed” by, say, an arbitrary ID value, you’d be able to find them quickly by that ID. But what if you wanted then to find everyone over the age of 50? You might consider creating a secondary “index” structure, a std::multimap that keys on age and its data is the ID, i.e. the key into your main structure. This will work, of course, but you now have two data structures to worry about, and to keep synchronised. And control access to in the presence of multiple threads. If you then find you want other “indices” it just gets even more complicated.
This is when you need Boost MultiIndex. It’s helpful to think of your collection (when implemented with Boost MultiIndex) as a database table. You can specify multiple indices (even using “composite keys” of more than one member) into one set of data, and query it in multiple ways. Hopefully the following code is self-explanatory, sufficiently to get you started.
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <string>
#include <iostream>
#include <functional>
struct Vehicle
{
size_t Id;
std::string Make;
std::string Model;
unsigned int YearMade;
bool SingleCylinder;
};
// Index "tags" used by Boost MultiIndex.
// Only purpose is to allow us to refer to indices
// by name rather than a "magic" positional number
struct IdxPrimaryKey{};
struct IdxYearMade{};
struct IdxMakeModel{};
struct IdxSingleCylinder{};
template<typename Tidx, typename Trecord>
void IterateOver(
const Tidx& idx,
std::function<void(const Trecord& rec)> func
)
{
auto it = idx.begin();
while ( it != idx.end() )
{
func(*it++);
}
}
int main()
{
namespace bmi = boost::multi_index;
// Definition of our "database" format:
bmi::multi_index_container<
Vehicle,
bmi::indexed_by<
// The "primary key"
bmi::ordered_unique<
bmi::tag<IdxPrimaryKey>,
bmi::member<
Vehicle, size_t, &Vehicle::Id
>
>,
// A simple key
bmi::ordered_non_unique<
bmi::tag<IdxYearMade>,
bmi::member<
Vehicle, unsigned int, &Vehicle::YearMade
>
>,
// Another simple key
bmi::ordered_non_unique<
bmi::tag<IdxSingleCylinder>,
bmi::member<
Vehicle, bool, &Vehicle::SingleCylinder
>
>,
// A composite key:
bmi::ordered_non_unique<
bmi::tag<IdxMakeModel>,
bmi::composite_key<
Vehicle,
bmi::member<
Vehicle, std::string, &Vehicle::Make
>,
bmi::member<
Vehicle, std::string, &Vehicle::Model
>
>
>
>
> vehicles;
vehicles.insert( { 1, "Vincent", "Rapide", 1950, false } );
vehicles.insert( { 2, "BSA", "Gold Star", 1958, true } );
vehicles.insert( { 3, "Triumph", "Thruxton", 2010, false } );
vehicles.insert( { 4, "Ariel", "Square 4", 1959, false } );
vehicles.insert( { 5, "Brough", "Superior", 1925, false } );
vehicles.insert( { 6, "Vincent", "Comet", 1951, true } );
vehicles.insert( { 7, "Norton", "Commando", 1973, false } );
// Iterate using "primary key" (ID) as index
auto& idxId = vehicles.get<IdxPrimaryKey>();
std::cout << "---------------------\n"
<< "Ordered by ID:\n" << std::endl;
IterateOver<decltype(idxId), Vehicle>(
idxId,
[](const Vehicle& vec
)
{
std::cout << vec.Id << ": " << vec.Make
<< " " << vec.Model << std::endl;
}
);
std::cout << "---------------------\n"
<< "Ordered by year of manufacture:\n" << std::endl;
// Iterate using year of manufacture as our index:
auto& idxSimple = vehicles.get<IdxYearMade>();
IterateOver<decltype(idxSimple), Vehicle>(
idxSimple,
[](const Vehicle& vec
)
{
std::cout << vec.YearMade << ": " << vec.Make
<< " " << vec.Model << std::endl;
}
);
std::cout << "---------------------\n"
<< "Ordered by marque then model:\n" << std::endl;
// Iterate using our composite key (make/model):
auto& idxComposite = vehicles.get<IdxMakeModel>();
IterateOver<decltype(idxComposite), Vehicle>(
idxComposite, [](const Vehicle& vec)
{
std::cout << vec.Make << " "
<< vec.Model << std::endl;
}
);
std::cout << "---------------------" << std::endl;
{
// Find a specific item:
auto it = idxId.find(5); // should check result IRL!
std::cout << "Item 5 is " << it->Make << " " << it->Model
<< std::endl;
}
std::cout << "---------------------\n"
<< "Bikes made in the fifties:\n" << std::endl;
{
// Find a range of items -- bikes made in the 50s:
auto it = idxSimple.lower_bound( 1950 );
auto itEnd = idxSimple.upper_bound( 1959 );
while ( it != itEnd )
{
std::cout << it->Make << " " << it->Model << " ("
<< it->YearMade << ")" << std::endl;
++it;
}
}
std::cout << "---------------------\n"
<< "Single-cylinder bikes:\n" << std::endl;
{
// Find a range of items -- bikes with just one pot
auto& idxSinglePot = vehicles.get<IdxSingleCylinder>();
auto pr = idxSinglePot.equal_range( true );
auto it = pr.first;
auto itEnd = pr.second;
while ( it != itEnd )
{
std::cout << it->Make << " " << it->Model << " ("
<< it->YearMade << ")" << std::endl;
++it;
}
}
std::cout << "---------------------" << std::endl;
return 0;
}
You can compile it (assuming you have Boost installed) with a simple g++ -std=c++14 -Wall -Wextra -pedantic main.cpp (and assuming you saved the code as main.cpp)
Output should be:
--------------------- Ordered by ID: 1: Vincent Rapide 2: BSA Gold Star 3: Triumph Thruxton 4: Ariel Square 4 5: Brough Superior 6: Vincent Comet 7: Norton Commando --------------------- Ordered by year of manufacture: 1925: Brough Superior 1950: Vincent Rapide 1951: Vincent Comet 1958: BSA Gold Star 1959: Ariel Square 4 1973: Norton Commando 2010: Triumph Thruxton --------------------- Ordered by marque then model: Ariel Square 4 BSA Gold Star Brough Superior Norton Commando Triumph Thruxton Vincent Comet Vincent Rapide --------------------- Item 5 is Brough Superior --------------------- Bikes made in the fifties: Vincent Rapide (1950) Vincent Comet (1951) BSA Gold Star (1958) Ariel Square 4 (1959) --------------------- Single-cylinder bikes: BSA Gold Star (1958) Vincent Comet (1951) ---------------------
Great Post. I was studying Boost Multi-index containers and also restore Classic British Motorcycles so this post was made for me!
One minor mistake is that the BSA Gold Star is a single so its single cylinder field should be true.
Hey James, well spotted! I’ve updated it, thanks : )