Getting Started with Boost MultiIndex

Note: this is an introduction to / overview of Boost MultiIndex. It is not intended to be in-depth.

So. Containers. In the words of luminaries in the C++ field such as Chandler Caruth, Scott Meyers and plenty of others, reach first for std::vector!

99% of the time this container, 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, false } );
    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:

Vincent Comet (1951)
---------------------

Leave a Reply

Your email address will not be published. Required fields are marked *