boost multi_index_container搜索落在两个字段定义的间隔内的记录 [英] boost multi_index_container search for records that fall within intervals defined by two fields

问题描述

请考虑下表:

id F1 F2    
0 0 10    
1 5 20    
2 20 30    
3 8 13    
4 13 17    
5 50 65    
6 15 26    
7 8 15

搜索具有x的记录，其中F1< = x&& x ＜＝ F2. 例如，搜索x = 10的记录将产生id为0、1、3、7的记录.

Search for records that have x, where F1 <= x && x <= F2. For example, searching for records with x = 10 would yield records with id's 0,1,3,7.

如何在C ++中使用boost multi_index_container来避免线性搜索?

How do you implement this in C++ using boost multi_index_container to avoid linear searching?

推荐答案

您将需要很多数据才能使之有价值，但我认为这是您要的:

You're going to need a lot of data to make this worthwhile, but I think this is what you're asking for:

#include <utility>
#include <vector>
#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/indexed_by.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/tag.hpp>
#include <boost/multi_index/member.hpp>

struct record
{
    int id;
    int f1, f2;
};

struct record_fs_extractor
{
    using result_type = std::pair<int, int>;

    constexpr result_type operator ()(record const& r) const noexcept
    {
        return {r.f1, r.f2};
    }
};

namespace bmi = boost::multi_index;
using records_t = bmi::multi_index_container<
    record,
    bmi::indexed_by<
        bmi::ordered_unique<bmi::member<record, int, &record::id>>,
        bmi::ordered_non_unique<bmi::tag<struct record_fs_tag>, record_fs_extractor>
    >
>;

std::vector<int> find_ids(records_t const& records, int const x)
{
    // second index's interface is like std::map<std::pair<int, int>, record>,
    // except that duplicate keys are allowed           f1--^    ^--f2
    auto const& f_idx = records.get<record_fs_tag>();
    auto it = f_idx.lower_bound(std::make_pair(f_idx.cbegin()->f1, x));
    auto const it_end = f_idx.cend();

    std::vector<int> ret;
    while (it != it_end && it->f1 <= x)
    {
        if (x <= it->f2)
            ret.push_back(it++->id);
        else
            it = f_idx.lower_bound(std::make_pair(it->f1, x));
    }
    return ret;
}

int main()
{
    records_t const records
    {
        { 0, 0,  10 },
        { 1, 5,  20 },
        { 2, 20, 30 },
        { 3, 8,  13 },
        { 4, 13, 17 },
        { 5, 50, 65 },
        { 6, 15, 26 },
        { 7, 8,  15 }
    };

    // default index's interface is like std::map<int, record>
    std::cout << "all, ordered by id:\n"; //   id--^
    for (auto const& r : records)
        std::cout << '\t' << r.id << ": " << r.f1 << ", " << r.f2 << '\n';

    std::cout << "\nreturned by find_ids(10):";
    for (auto const& id : find_ids(records, 10))
        std::cout << ' ' << id;
    std::cout << '\n';
}

在线演示

输出:

all, ordered by id:
        0: 0, 10
        1: 5, 20
        2: 20, 30
        3: 8, 13
        4: 13, 17
        5: 50, 65
        6: 15, 26
        7: 8, 15

returned by find_ids(10): 0 1 3 7

IFF 查找 first 记录正好是一个瓶颈，因此值得第三索引的内存开销，然后

IFF finding the first record happens to be so much of a bottleneck that it's worth the memory-cost of a third index, then here is an alternative implementation to address that.

这篇关于boost multi_index_container搜索落在两个字段定义的间隔内的记录的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！