Получить ранг элемента контейнера boost::multi_index

Код ниже показывает контейнер multi_index, который индексируется по последовательности и порядку.

В моем сценарии использования элементы будут в основном искать по индексу, и, если он существует, будет получен следующий элемент (по порядку).

У меня вопрос, как получить ранг (по порядку) полученного следующего элемента?

#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
        ;
    }
}

2 ответа

Решение

Ответ @sehe совершенно верный, но работает за линейное время. Если вы хотите повысить производительность, определите индекс № 0 как random_access и № 1 как ranked_non_unique (индекс № 2 является избыточным):

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

так что вы можете написать:

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
;

Предполагая, что вы хотите какой-то "индекс в" или "смещение от начала" в последовательном индексе:

if (it!=order.end()) {
    auto rank_of = [&](auto it) {
        return std::distance(sequence.begin(), ints.project<0>(it));
    };

    auto seq_next = std::next(seq_it);
    auto ord_next = std::next(it);

    if (seq_next!=sequence.end())
    {
        std::cout << "next to                     " << *it << " by sequence is " << *seq_next << std::endl;
        std::cout << "rank of next by sequence is " << rank_of(seq_next) << std::endl;
    }

    if (ord_next!=order.end())
    {
        std::cout << "next to                     " << *it << " by order is " << *ord_next << std::endl ;
        std::cout << "rank of next by order is    " << rank_of(ord_next) << std::endl;
    }
}

Без полиморфных лямбд вы должны выписать это

Другие вопросы по тегам