How to make the equal_range iterator sorted by a different index in Boost Multi-index?

Question

I have a boost multi-index container on the employee class (taken from boost official documentation):

typedef multi_index_container<
        employee,
        indexed_by<
                ordered_unique<
                        tag<id>,  BOOST_MULTI_INDEX_MEMBER(employee,int,id)>,
                ordered_non_unique<
                        tag<name>,BOOST_MULTI_INDEX_MEMBER(employee,std::string,name)>,
                ordered_non_unique<
                        tag<age>, BOOST_MULTI_INDEX_MEMBER(employee,int,age)> >
> employee_set;

Here is an example of data in the container printed by (id, name, age):

0 Joe 31
1 Robert 27
2 John 40
3 Albert 20
4 John 57
5 John 58
6 John 22

I would like to have an iterator of all items whose name is John sorted by age (last field). I tried to the equal_range method:

auto iter1 = boost::make_iterator_range(es.get<name>().equal_range("John"));

Which returns an iterator with all records whose name is John. How can I make this iterator to be sorted by the third index (i.e. age)?

The output should be:

6 John 22
2 John 40
4 John 57
5 John 58

It's sad that you didn't include fully working code. I'll make one myself now, but I might not have time to answer the question as a consequence — sehe, Jun 22 '18 at 11:11
@sehe Sorry, next time I will add the code to the question. The code was from the first example of the boost documentation. (https://www.boost.org/doc/libs/1_62_0/libs/multi_index/example/basic.cpp) — motam79, Jun 22 '18 at 12:47
Yeah, a link to the document would have been a good start. I knew the documentation contains more than one example :) — sehe, Jun 22 '18 at 12:48

sehe · Accepted Answer · 2018-06-22T13:39:10.753

Okay. Here's the reproducer Live On Coliru

Output is indeed

2 "John" 40
4 "John" 57
5 "John" 58
6 "John" 22

Now to have it also (note the choice of words) ordered by age, you can use a composite key. So instead of:

    bmi::ordered_non_unique<
        bmi::tag<struct name>,
        bmi::member<employee, std::string, &employee::name>
    >,

Use

    bmi::ordered_non_unique<
        bmi::tag<struct name_age>,
        bmi::composite_key<employee,
            bmi::member<employee, std::string, &employee::name>,
            bmi::member<employee, int, &employee::age>
        >
    >,

And now you can

for (employee const& emp : boost::make_iterator_range(es.get<name_age>().equal_range("John"))) {
    std::cout << emp.id << " " << std::quoted(emp.name) << " " << emp.age << "\n";
}

Prints

6 "John" 22
2 "John" 40
4 "John" 57
5 "John" 58

Full sample

Live On Coliru

#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/range/iterator_range.hpp>

namespace bmi = boost::multi_index;

struct employee {
    int id;
    std::string name;
    int age;
};

typedef bmi::multi_index_container<
    employee,
    bmi::indexed_by<
        bmi::ordered_unique<
            bmi::tag<struct id>,
            bmi::member<employee, int, &employee::id>
        >,
        bmi::ordered_non_unique<
            bmi::tag<struct name>,
            bmi::member<employee, std::string, &employee::name>
        >,
        bmi::ordered_non_unique<
            bmi::tag<struct name_age>,
            bmi::composite_key<employee,
                bmi::member<employee, std::string, &employee::name>,
                bmi::member<employee, int, &employee::age>
            >
        >,
        bmi::ordered_non_unique<
            bmi::tag<struct age>,
            bmi::member<employee, int, &employee::age>
        >
    > > employee_set;

#include <iostream>
#include <iomanip>

int main() {
    employee_set es {
        {0, "Joe",    31},
        {1, "Robert", 27},
        {2, "John",   40},
        {3, "Albert", 20},
        {4, "John",   57},
        {5, "John",   58},
        {6, "John",   22},
    };

    std::cout << "name index:\n";
    for (employee const& emp : boost::make_iterator_range(es.get<name>().equal_range("John"))) {
        std::cout << emp.id << " " << std::quoted(emp.name) << " " << emp.age << "\n";
    }

    std::cout << "name_age index:\n";
    for (employee const& emp : boost::make_iterator_range(es.get<name_age>().equal_range("John"))) {
        std::cout << emp.id << " " << std::quoted(emp.name) << " " << emp.age << "\n";
    }
}

Prints

name index:
2 "John" 40
4 "John" 57
5 "John" 58
6 "John" 22
name_age index:
6 "John" 22
2 "John" 40
4 "John" 57
5 "John" 58

Thanks! The concept of composite keys is very powerful. You can implement a SQL database with boost multi-index. — motam79, Jun 22 '18 at 12:52
@motam79 Yeah. There are some constraints (a.k.a.: there is no silver bullet). You can't expect to get magically optimized indexes and you'll _always_ have to devise your own "explain plan" manually. Most importantly, queries across multiple indices will require a RANGE SCAN (sql terminology) on one index. Databases perform many non-trivial optimizations and profile-guided choices here. As long as you know your data really well (w.r.t. index density) you can get a lot of mileage out of Boost MultiIndex though. (Oh and there's non-trivial insertion cost) — sehe, Jun 22 '18 at 12:55

How to make the equal_range iterator sorted by a different index in Boost Multi-index?

1 Answers1

Full sample