Iterate through boost multi_index with custom ordering

Question

I have a boost multi_index container with multiple indices. How can I iterate through the elements with a custom comparison specified when iterating.

For example, given that Element::name and Element::index are indexed by the multi_index container

bool myCompare(const Element &lhs, const Element &rhs)
{
    if(lhs.name == rhs.name)
    {
        return lhs.index < rhs.index;
    }
    else
    {
        return lhs.name < rhs.name;
    }
}

However, the iteration should not be limited to the case above but allowing any kind of order according to the indexed members of Element similar to the SQL SELECT ordering.

sehe · Accepted Answer

That's not a feature of the multi-index container.

However, you can easily create an extra temporary index:

std::vector > temporary(table.begin(), table.end());

Now you can sort that index named ordering by your custom comparison:

std::sort(temporary.begin(), temporary.end(), myCompare);

// iterate table in that order:
for(Element const& e: temporary)
    std::cout << e.index << "	" << e.name << "
";

Bonus: You easily persist that ordering in a multi_index::random_accesss index using rearrange:
table.get().rearrange(temporary.begin());
(where external tags a random access index).

More notes:

your predicate doesn't define a proper weak total ordering. It seems you might want to do this instead:

#include 
bool myCompare(const Element &lhs, const Element &rhs) {
    return std::tie(lhs.name, lhs.index) < std::tie(rhs.name, rhs.index);
}

DEMO

Live On Coliru

#include 
#include 

struct Element {
    int index;
    std::string name;
};

#include 
bool myCompare(const Element &lhs, const Element &rhs) {
    return std::tie(lhs.name, lhs.index) < std::tie(rhs.name, rhs.index);
}

namespace bmi = boost::multi_index;

using Table = boost::multi_index_container >
      > >;

#include 
#include  // for the temporary index

int main() {
    Table table;

    // generate 30 random records...
    std::generate_n(back_inserter(table), 30,
            []{ return Element { rand()%100, std::string(1, 'a'+rand()%26) }; }
        );

    {
        // temporary index:
        std::vector > temporary(table.begin(), table.end());

        // iterate table in the order specified by myCompare:
        std::sort(temporary.begin(), temporary.end(), myCompare);

        for(Element const& e: temporary)
            std::cout << e.index << "	" << e.name << "
";

        // now to rearrange a random-access index on the multi-index container:
        table.get().rearrange(temporary.begin());
    }
}

Prints (e.g.)

You can see, where names are equal, the lower index comes first.

UPDATE To the comment:

Hmm? Are you asking for magic fairy dust?

Are you asking for magic fairy dust? There's no magic.

DBMS's don't use anything out of the ordinary. They typically use BTrees, very similar to the datastructures that underly your garden variety std::map, or indeed the bmi::ordered_[non_]unique indices. So in this respect Boost MultiIndex is (close to) what you want, already.

The main addition thing RDBMS-es bring to the table is persistency. With that, everything becomes more useful, more scalable and ... less efficient.

So, don't look at DBMS-es for the holy grail of efficiency.

There's a reason that in-memory key-value data-stores are widely employed for performance. Another important note is that retrieving an ordered resultset in SQL does not perform well at all, unless the indexes already exist.

Now, if you want the best possible performance, you might want to devise your own data structures (perhaps with the help of Boost Intrusive), but seeing the level at which you pose these questions, I'd play with Boost Multi Index for an extended period of time before you do. Just create the indexes you may sometimes need to combine, and write some "loopy code" ¹ that combines them as required.

IDEAS

Now thinking out of the box, you might be wondering how you would "easily" implement the two-level ordering in a way that a DBMS engine might.

Like the DBMS engine, the easiest thing would be to have an always-uptodate index at the ready: Demo

using Table = boost::multi_index_container >,
        // ready made index for traversal in composite order
        bmi::ordered_non_unique, 
            bmi::composite_key,
                bmi::member 
            >
        >
    > >;

int main() {
    // generate 30 random records...
    Table table;
    std::generate_n(back_inserter(table), 30, []{ return Element { rand()%100, std::string(1, 'a'+rand()%26) }; });

    // effectively "zero" cost iteration there:
    for(Element const& e: table.get())
        std::cout << e.index << "	" << e.name << "
";
}

Note that you can use ordered composite indices in Boost MultiIndex partially, too:

    for(Element const& e: boost::make_iterator_range(table.get().equal_range("y")))
        std::cout << e.index << "	" << e.name << "
";

prints (for the same random seed as above):

11  y
13  y
72  y

Alternatively, you could have separate indexes defined, and use them with your own algorithm to achieve the two-level ordering:

using Table = boost::multi_index_container >,

        // separate indices that we might combine in some way later::
        bmi::ordered_non_unique, bmi::member >,
        bmi::ordered_non_unique,  bmi::member >
    > >;

Now combining the indexes becomes the job of the "engine" or, in this case your algorithm. Here's an idea:

template 
    void SelectOrderBy2(Table const& table, Function function) {

        using T = typename Table::value_type const;
        auto& idx1 = table.template get();
        auto& idx2 = table.template get();

        auto it = idx1.begin(), end = idx1.end();

        while (it!=end) {
            auto next = idx1.upper_bound(idx1.key_extractor()(*it));

            std::set, typename Table::template index::type::value_compare>
                set(idx2.value_comp());

            while (it != next)
                set.insert(set.end(), boost::cref(*it++));

            for (auto& e: set)
                function(e);
        }
    }

That's some pretty high-falluting template code, but you can use it quite simply:

SelectOrderBy2(
        table, 
        [](Element const& e) { std::cout << e.index << "	" << e.name << "
"; }
    );

See it Live On Coliru too

¹ perhaps better referred to as generic/special-purpose algorithms ... :)

Iterate through boost multi_index with custom ordering

Answers (2)

DEMO

IDEAS

Related Questions