CODEWITHSUNDEEP
c++boostmulti-index
Kiko
Kiko

Reputation: 359

The order value index in boost::multi_index_container

I have a multi_index_container, and index - ordered_unique. I know that my values will be sorted somehow ( by default using less ). What I want is to find the exact ordered index of the value, without using some O(n) algorithm, like std::distance.

typedef multi_index_container<
MyStruct,
indexed_by<
    ordered_unique<member< MyStruct, int, &MyStruct::id> >,
    ordered_non_unique<member< MyStruct, int, &MyStruct::salary> >
>
> MyStructsContainer;

....

MyStructsContainer myStructsContainer;

MyStructsContainer::iterator it1 = myStructsContainer.emplace(MyStruct{ 3, 20 }).first;
MyStructsContainer::iterator it2 = myStructsContainer.emplace(MyStruct{ 1, 100 }).first;
MyStructsContainer::iterator it3 = myStructsContainer.emplace(MyStruct{ 2, 20 }).first;

Here it1, it2 and it3 are not RandomAccessIts. Therefore the only way to find the index is: 

size_t idx = distance(myStructsContainer.begin(), it1); <--- is there any other and smarter way to find the ordered index??
assert(idx == 2);

Is there any other approach to do that?

Thanks, Kalin

Upvotes: 1

Views: 359

Answers (1)

sehe
sehe

Reputation: 394044

You want to have the insertion order?

In that case, just add a random_access index (perhaps making it the default).

You can have O(1) std::distance on random-access iterators.

UPDATE To the comment:

If you want a more efficient order-lookup you can either store the ordinal/rank inside the element, or use a dedicated random access index.

You can easily rearrange such an index to match the order you wish:

Live On Coliru

#include <iostream>
#include <string>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/member.hpp>

struct MyStruct {
    int id, salary;
};

namespace bmi = boost::multi_index;
typedef boost::multi_index_container<
    MyStruct, bmi::indexed_by<
        bmi::ordered_unique<bmi::tag<struct ById>, bmi::member<MyStruct, int, &MyStruct::id>>,
        bmi::ordered_non_unique<bmi::tag<struct BySalary>, bmi::member<MyStruct, int, &MyStruct::salary>>,
        bmi::random_access<bmi::tag<struct RandomAccess> >
    > > MyStructsContainer;


int main()
{
    MyStructsContainer c;
    auto it3 = c.emplace(MyStruct{ 3, 20  }).first;
    auto it1 = c.emplace(MyStruct{ 1, 100 }).first;
    auto it2 = c.emplace(MyStruct{ 2, 20  }).first;

    auto& ra = c.get<RandomAccess>();

    // reorder RandomAccess index to match the ById
    {
        auto const& idx = c.get<ById>();
        std::vector<boost::reference_wrapper<MyStruct const> > tmp(idx.begin(), idx.end());
        ra.rearrange(tmp.begin());
    }

    // now you can say:
    std::cout << "Index of " << (it1->id) << " is " << (std::distance(ra.begin(), bmi::project<RandomAccess>(c, it1))) << "\n";
    std::cout << "Index of " << (it2->id) << " is " << (std::distance(ra.begin(), bmi::project<RandomAccess>(c, it2))) << "\n";
    std::cout << "Index of " << (it3->id) << " is " << (std::distance(ra.begin(), bmi::project<RandomAccess>(c, it3))) << "\n";
}

Prints

Index of 1 is 0
Index of 2 is 1
Index of 3 is 2

The efficience of std::distance on this index is O(1)

Upvotes: 2

Related Questions