Индекс стоимости заказа в boost::multi_index_container

У меня мульти_индексный_контейнер, а индексный — упорядоченный_уникальный. Я знаю, что мои значения будут каким-то образом отсортированы (по умолчанию используется less). Я хочу найти точный упорядоченный индекс значения без использования какого-либо алгоритма O (n), например 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;

Здесь it1, it2 и it3 не являются RandomAccessIts. Поэтому единственный способ найти индекс:

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

Есть ли другой подход для этого?

Спасибо, Калин


c++ boost multi-index
person Kiko    schedule 05.02.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вы хотите иметь порядок размещения?

В этом случае просто добавьте индекс random_access (возможно, сделав его индексом по умолчанию).

Вы можете иметь O(1) std::distance на итераторах с произвольным доступом.

ОБНОВЛЕНИЕ К комментарию:

Если вам нужен более эффективный поиск по порядку, вы можете либо сохранить порядковый номер/ранг внутри элемента, либо использовать специальный индекс произвольного доступа.

Вы можете легко rearrange такой индекс соответствовать желаемому порядку:

Жить на 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";
}

Отпечатки

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

Эффективность std::distance по этому индексу равна O(1)

person sehe    schedule 05.02.2015
comment
Неа. Я только что отредактировал вопрос, чтобы сделать его чистым. Мне нужен упорядоченный индекс. для него1 это 2 для него2 это 1 .... - person Kiko; 05.02.2015
comment
@KalliMan Обновил мой ответ :) - person sehe; 05.02.2015
comment
Спасибо, это будет работать для одной части моей задачи. Но, к сожалению, я также хочу получить индекс сразу после emplase.... Я могу комбинировать оба подхода, чтобы получить одинаковую оптимизацию, но решение не будет идеальным. - person Kiko; 05.02.2015
comment
@KalliMan Прости. Этого не существует. Упорядоченные контейнеры основаны на узлах, поэтому у них нет произвольного доступа. Просто как тот. - person sehe; 05.02.2015
comment
Возможно, есть вариант с boost::flat_(multi)set. . Скорее всего, он не раскрывает детали реализации, но может дать вам расстояние O(1). В любом случае, это не использование multi_index_container - person sehe; 05.02.2015
comment
Только что проверил, хотя документы не упоминают об этом, итераторы flat_set действительно имеют произвольный доступ: Прямой эфир на Coliru. На всякий случай, если вам любопытно (как мне). Я бы согласился на явное int rank; в MyStruct - person sehe; 05.02.2015
comment
Но мне нужно, чтобы он был multi_set. Также я не думаю, что это хорошая идея использовать что-то, что плохо документировано. Что, если в один прекрасный солнечный день Boost решит его изменить? - person Kiko; 05.02.2015
comment
@KalliMan В этом нет смысла. Как вы думаете, почему я вообще подумал о flat(_multi)_set? Он определен как непрерывно хранящиеся элементы (по сути, просто вектор). Он хорошо задокументирован, просто категория итератора явно не упоминается на этой странице. Однако это произвольный доступ, поскольку код компилируется. Это общедоступный интерфейс. - person sehe; 05.02.2015
comment
О, извините, я имел в виду multi_index. Мне нужно что-то проиндексировать по нескольким индексам. Вот почему я не могу использовать xxxx_set. Я действительно не читал документы flat_set. Просто прочитайте, что вы упомянули, хотя в документах об этом не упоминается.... - person Kiko; 05.02.2015
comment
Ok. Спасибо за разъяснения :). Желаю вам удачи в реализации того, что вам нужно реализовать. Это все работа в конце концов. Просто разница в том, сколько уже реализовано для вас... И, как я уже сказал: Я бы согласился на явный ранг int; в MyStruct. Это боль, чтобы оставаться последовательным, конечно. Но проверка простых чисел также является проблемой. Или преобразование набора символов. И все это неизбежно - person sehe; 05.02.2015