Search code examples
c++boostboost-multi-index

get the rank of an element of a boost::multi_index container


The code below shows a multi_index container which is indexed by sequence and order.

In my use case elements will be mainly searched by index, and if existing, the next element (by order) is obtained.

My question is, how to get the rank (by order) of obtained next element?

#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/ranked_index.hpp>
#include <boost/multi_index/identity.hpp>

using namespace boost::multi_index;

typedef multi_index_container <
    int
  , indexed_by<
        sequenced<>
      , ordered_non_unique<identity<int>>
      , ranked_non_unique<identity<int>>
    >
> Ints;

int main() {
    Ints ints;

    auto & sequence=ints.get<0>();
    auto & order=ints.get<1>();

    sequence.push_back(2);
    sequence.push_back(-1);
    sequence.push_back(5);
    sequence.push_back(6);

    auto it = order.find(2);
    if (it!=order.end()) {
        std::cout
            << "next to "
            << *it
            << " by sequence is "
            << *(++(ints.project<0>(it)))
            << std::endl
        ;
        std::cout
            << "next to "
            << *it
            << " by order is "
            << *(++(ints.project<1>(it))) //++it is good too
            << std::endl
        ;
        std::cout
            << "rank of next by sequence is "
            // << ??? ints.rank<???>(???)
            << std::endl
        ;
        std::cout
            << "rank of next by order is "
            // << ??? ints.rank<???>(???)
            << std::endl
        ;
    }
}

Solution

  • @sehe's answer is perfectly valid but runs in linear time. If you want better performance, consider defining your index #0 as random_access and #1 as ranked_non_unique (index #2 is redundant):

    typedef multi_index_container <
        int
      , indexed_by<
            random_access<>
          , ranked_non_unique<identity<int>>
        >
    > Ints;
    

    so that you can write:

    std::cout
        << "rank of next by sequence is "
        << ints.project<0>(it)-sequence.begin()+1 // O(1)
        << std::endl
    ;
    std::cout
        << "rank of next by order is "
        << order.rank(it)+1 // O(log n)
        << std::endl
    ;