c++ - 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。

---

更新评论:

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

您可以轻松地重新排列这样的索引以匹配您希望的顺序:

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)