boost::multi_index_container中的订单价值指数

Question

我有一个 multi_index_container 和索引 - ordered_unique。我知道我的值会以某种方式排序（默认情况下使用 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);

还有其他方法吗？

谢谢，卡林

Answer 1

您想要广告订单吗？

在这种情况下，只需添加一个 random_access 索引（也许将其设置为默认索引）。

随机访问迭代器的复杂度为 O(1) std::distance。

更新评论:

如果您想要更高效的顺序查找，您可以将 ordinal/rank 存储在元素内，或者使用专用的随机访问索引。

您可以轻松地rearrange这样的索引来匹配您希望的顺序：

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

版画

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

std::distance在这个指数上的效率是O(1)

boost::multi_index_container中的订单价值指数

The order value index in boost::multi_index_container

c++

boost

multi-index