获取元素在 boost::multi_index_container 的有序索引中的位置

Question

（不遍历容器）

我正在尝试用单个 boost::multi_index_container 替换多个 std 容器。

下面的boost::multi_index_container有两个索引

using Boxes = boost::multi_index_container<
    Box,
    indexed_by<
        sequenced<
            tag<ordered_by_insertion>
        >,
        ordered_unique<
            tag<ordered_by_id>,
            const_mem_fun<Box, set_id_type_const_reference, &Box::id>
        >
    >
>;

元素添加到容器的顺序需要保留，所以第一个索引是插入序列（ordered_by_insertion）。

元素由 id 唯一标识，所以第二个索引在唯一 ID (ordered_by_id) 上。

如何使用唯一标识有效地检索元素的插入顺序位置。

有没有办法把ordered_by_insertion变成从对象到位置的双向映射？或者创建从 Box::id 到 position?

的第三个索引

Answer 1

以下 projects 从索引 #1 到索引 #0 的迭代器：

Boxes b=...;
auto it1=b.get<1>().find(id);
auto it0=b.project<0>(it1);

从中您可以获得索引 #0 中的位置，但在 线性时间 中很遗憾，因为顺序索引迭代器仅是双向的：

auto pos=std::distance(b.begin(),it0);

好消息是，如果您使用 random_access 索引而不是 sequenced，那么计算 pos 就是 constant-time；你甚至可以简单地写成：

auto pos=it0-b.begin();

Answer 2

你可以这样做：

Live On Coliru

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

namespace  bmi = boost::multi_index;

using set_id_type_const_reference = int const&;

struct Box {
    int _id;
    std::string name;

    set_id_type_const_reference id() const { return _id; }
};

using Boxes = boost::multi_index_container<
    Box,
    bmi::indexed_by<
        bmi::sequenced<bmi::tag<struct ordered_by_insertion> >,
        bmi::ordered_unique<
            bmi::tag<struct ordered_by_id>,
            bmi::const_mem_fun<Box, set_id_type_const_reference, &Box::id>
        >
    >
>;

int main() {
    Boxes boxes { {1,"One"}, {17,"Seventeen"}, {8,"Eight"}, {3,"Three"} };

    auto& by_ins = boxes.get<ordered_by_insertion>();
    auto& by_id  = boxes.get<ordered_by_id>();

    for (auto i : { 8,17,1,3 }) {
        auto it = by_id.find(i);
        auto position = distance(by_ins.begin(), bmi::project<0>(boxes, it));

        std::cout << "Found " << it->name << " with insertion-order position " << position << "\n";
    }

}

打印：

Found Eight with insertion-order position 2
Found Seventeen with insertion-order position 1
Found One with insertion-order position 0
Found Three with insertion-order position 3

考虑使用 random_access 提高 distance 调用的效率：http://www.boost.org/doc/libs/1_60_0/libs/multi_index/doc/reference/rnd_indices.html

获取元素在 boost::multi_index_container 的有序索引中的位置

get the position of an element in a sequenced index of boost::multi_index_container

c++

boost

boost-multi-index