{"id":633,"date":"2017-03-29T10:55:33","date_gmt":"2017-03-29T09:55:33","guid":{"rendered":"http:\/\/www.martyndavis.com\/?p=633"},"modified":"2021-08-24T06:17:37","modified_gmt":"2021-08-24T05:17:37","slug":"getting-started-with-boost-multiindex","status":"publish","type":"post","link":"https:\/\/www.martyndavis.com\/?p=633","title":{"rendered":"Getting Started with Boost MultiIndex"},"content":{"rendered":"\n

Note: this is an introduction to \/ overview of Boost MultiIndex. It is not intended to be in-depth.<\/em><\/p>\n\n\n\n

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<\/code> 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<\/code> 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<\/code>) as opposed to O(n) time for an unsorted std::vector. (Obviously these are theoretical complexities – see a previous post<\/a> which advocates actual benchmarking, as processor cache and branch prediction can have a huge effect).
<\/p>\n\n\n\n\n\n\n\n

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”?<\/p>\n\n\n\n

Imagine you’ve got a struct like this:<\/p>\n\n\n

\nstruct Person\n{\n    std::string  Name,\n    unsigned int Age,\n    std::string  PostCode \/\/ \"Zip\" code\n};\n<\/pre>\n\n\n\n
<\/p>\n\n\n\n
If you created a std::map<\/code> 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.<\/p>\n\n\n\n
This is when you need Boost MultiIndex. It’s helpful to think of your collection (when implemented with Boost MultiIndex) as a database table.<\/strong> 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.<\/p>\n\n\n
\n#include <boost\/multi_index_container.hpp>\n#include <boost\/multi_index\/ordered_index.hpp>\n#include <boost\/multi_index\/member.hpp>\n#include <boost\/multi_index\/composite_key.hpp>\n\n#include <string>\n#include <iostream>\n#include <functional>\n\nstruct Vehicle\n{\n    size_t       Id;\n    std::string  Make;\n    std::string  Model;\n    unsigned int YearMade;\n    bool         SingleCylinder;\n};\n\n\/\/ Index "tags" used by Boost MultiIndex.\n\/\/ Only purpose is to allow us to refer to indices\n\/\/ by name rather than a "magic" positional number\nstruct IdxPrimaryKey{};\nstruct IdxYearMade{};\nstruct IdxMakeModel{};\nstruct IdxSingleCylinder{};\n\ntemplate<typename Tidx, typename Trecord>\nvoid IterateOver(\n    const Tidx& idx,\n    std::function<void(const Trecord& rec)> func\n    )\n{\n    auto it = idx.begin();\n    while ( it != idx.end() )\n    {\n        func(*it++);\n    }\n}\n\nint main()\n{\n    namespace bmi = boost::multi_index;\n\n    \/\/ Definition of our "database" format:\n    bmi::multi_index_container<\n        Vehicle,\n        bmi::indexed_by<\n            \/\/ The "primary key"\n            bmi::ordered_unique<\n                bmi::tag<IdxPrimaryKey>,\n                bmi::member<\n                    Vehicle, size_t, &Vehicle::Id\n                >\n            >,\n            \/\/ A simple key\n            bmi::ordered_non_unique<\n                bmi::tag<IdxYearMade>,\n                bmi::member<\n                    Vehicle, unsigned int, &Vehicle::YearMade\n                >\n            >,\n            \/\/ Another simple key\n            bmi::ordered_non_unique<\n                bmi::tag<IdxSingleCylinder>,\n                bmi::member<\n                    Vehicle, bool, &Vehicle::SingleCylinder\n                >\n            >,\n            \/\/ A composite key:\n            bmi::ordered_non_unique<\n                bmi::tag<IdxMakeModel>,\n                bmi::composite_key<\n                    Vehicle,\n                    bmi::member<\n                        Vehicle, std::string, &Vehicle::Make\n                    >,\n                    bmi::member<\n                        Vehicle, std::string, &Vehicle::Model\n                    >\n                >\n            >\n        >\n    > vehicles;\n\n    vehicles.insert( { 1, "Vincent", "Rapide",    1950, false } );\n    vehicles.insert( { 2, "BSA",     "Gold Star", 1958, true  } );\n    vehicles.insert( { 3, "Triumph", "Thruxton",  2010, false } );\n    vehicles.insert( { 4, "Ariel",   "Square 4",  1959, false } );\n    vehicles.insert( { 5, "Brough",  "Superior",  1925, false } );\n    vehicles.insert( { 6, "Vincent", "Comet",     1951, true  } );\n    vehicles.insert( { 7, "Norton",  "Commando",  1973, false } );\n\n    \/\/ Iterate using "primary key" (ID) as index\n    auto& idxId = vehicles.get<IdxPrimaryKey>();\n    std::cout << "---------------------\\n"\n              << "Ordered by ID:\\n" << std::endl;\n    IterateOver<decltype(idxId), Vehicle>(\n            idxId,\n            [](const Vehicle& vec\n        )\n        {\n            std::cout   << vec.Id << ": " << vec.Make\n                        << " " << vec.Model << std::endl;\n        }\n    );\n\n    std::cout << "---------------------\\n"\n              << "Ordered by year of manufacture:\\n" << std::endl;\n    \/\/ Iterate using year of manufacture as our index:\n    auto& idxSimple = vehicles.get<IdxYearMade>();\n    IterateOver<decltype(idxSimple), Vehicle>(\n            idxSimple,\n            [](const Vehicle& vec\n        )\n        {\n            std::cout   << vec.YearMade << ": " << vec.Make\n                        << " " << vec.Model << std::endl;\n        }\n    );\n\n    std::cout << "---------------------\\n"\n              << "Ordered by marque then model:\\n" << std::endl;\n    \/\/ Iterate using our composite key (make\/model):\n    auto& idxComposite = vehicles.get<IdxMakeModel>();\n    IterateOver<decltype(idxComposite), Vehicle>(\n        idxComposite, [](const Vehicle& vec)\n        {\n            std::cout << vec.Make << " "\n                      << vec.Model << std::endl;\n        }\n    );\n    std::cout << "---------------------" << std::endl;\n\n    {\n        \/\/ Find a specific item:\n        auto it = idxId.find(5); \/\/ should check result IRL!\n        std::cout << "Item 5 is " << it->Make << " " << it->Model\n                  << std::endl;\n    }\n    std::cout << "---------------------\\n"\n              << "Bikes made in the fifties:\\n" << std::endl;\n\n    {\n        \/\/ Find a range of items -- bikes made in the 50s:\n        auto it    = idxSimple.lower_bound( 1950 );\n        auto itEnd = idxSimple.upper_bound( 1959 );\n        while ( it != itEnd )\n        {\n            std::cout << it->Make << " " << it->Model << " ("\n                      << it->YearMade << ")" << std::endl;\n            ++it;\n        }\n    }\n    std::cout << "---------------------\\n"\n              << "Single-cylinder bikes:\\n" << std::endl;\n    {\n        \/\/ Find a range of items -- bikes with just one pot\n        auto& idxSinglePot = vehicles.get<IdxSingleCylinder>();\n        auto pr = idxSinglePot.equal_range( true );\n        auto it = pr.first;\n        auto itEnd = pr.second;\n        while ( it != itEnd )\n        {\n            std::cout << it->Make << " " << it->Model << " ("\n                      << it->YearMade << ")" << std::endl;\n            ++it;\n        }\n    }\n    std::cout << "---------------------" << std::endl;\n\n    return 0;\n}    \n<\/pre><\/div>\n\n\n
You can compile it (assuming you have Boost installed) with a simple g++ -std=c++14 -Wall -Wextra -pedantic main.cpp<\/code> (and assuming you saved the code as main.cpp)<\/p>\n\n\n\n
Output should be:<\/p>\n\n\n\n
\n---------------------\nOrdered by ID:\n\n1: Vincent Rapide\n2: BSA Gold Star\n3: Triumph Thruxton\n4: Ariel Square 4\n5: Brough Superior\n6: Vincent Comet\n7: Norton Commando\n---------------------\nOrdered by year of manufacture:\n\n1925: Brough Superior\n1950: Vincent Rapide\n1951: Vincent Comet\n1958: BSA Gold Star\n1959: Ariel Square 4\n1973: Norton Commando\n2010: Triumph Thruxton\n---------------------\nOrdered by marque then model:\n\nAriel Square 4\nBSA Gold Star\nBrough Superior\nNorton Commando\nTriumph Thruxton\nVincent Comet\nVincent Rapide\n---------------------\nItem 5 is Brough Superior\n---------------------\nBikes made in the fifties:\n\nVincent Rapide (1950)\nVincent Comet (1951)\nBSA Gold Star (1958)\nAriel Square 4 (1959)\n---------------------\nSingle-cylinder bikes:\n\nBSA Gold Star (1958)\nVincent Comet (1951)\n---------------------\n<\/pre><\/pre>\n","protected":false},"excerpt":{"rendered":"
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 … <\/p>\n
Continue reading “Getting Started with Boost MultiIndex”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17,1],"tags":[],"_links":{"self":[{"href":"https:\/\/www.martyndavis.com\/index.php?rest_route=\/wp\/v2\/posts\/633"}],"collection":[{"href":"https:\/\/www.martyndavis.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.martyndavis.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.martyndavis.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.martyndavis.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=633"}],"version-history":[{"count":24,"href":"https:\/\/www.martyndavis.com\/index.php?rest_route=\/wp\/v2\/posts\/633\/revisions"}],"predecessor-version":[{"id":826,"href":"https:\/\/www.martyndavis.com\/index.php?rest_route=\/wp\/v2\/posts\/633\/revisions\/826"}],"wp:attachment":[{"href":"https:\/\/www.martyndavis.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=633"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.martyndavis.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=633"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.martyndavis.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=633"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}