如何獲得一個boost :: multi_index容器的交集

Question

我想要以最快的方式獲得類型爲ordered_non_unique的4個索引的交集。這樣的一個multi_index -intersection比4倍嵌套std::map更快？是否有可能使用類似std :: map（）。emplace（）的東西。

這是我的代碼。

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

using boost::multi_index_container; 
using namespace boost::multi_index; 

struct Kpt { 
    Kpt(float _x0, float _x1, float _y0, float _y1) 
     : x0_(_x0),x1_(_x1),y0_(_y0),y1_(_y1) { 
    } 
    friend std::ostream& operator<<(std::ostream & _os, Kpt const & _kpt) { 
     _os 
      << "\nx0 " << _kpt.x0_ << "," 
      << " y0 " << _kpt.y0_ << "," 
      << " x1 " << _kpt.x1_ << "," 
      << " y1 " << _kpt.y1_ << std::endl 
     ; 
     return _os; 
    } 
    float x0_; 
    float x1_; 
    float y0_; 
    float y1_; 
}; 

struct x0_{}; 
struct x1_{}; 
struct y0_{}; 
struct y1_{}; 

typedef multi_index_container < 
    Kpt 
    , indexed_by < 
     ordered_non_unique < 
      tag<x0_>,BOOST_MULTI_INDEX_MEMBER(Kpt,float,x0_) 
     > 
     , ordered_non_unique < 
      tag<x1_>,BOOST_MULTI_INDEX_MEMBER(Kpt,float,x1_) 
     > 
     , ordered_non_unique < 
       tag<y0_>,BOOST_MULTI_INDEX_MEMBER(Kpt,float,y0_) 
      > 
     , ordered_non_unique < 
       tag<y1_>,BOOST_MULTI_INDEX_MEMBER(Kpt,float,y1_) 
      > 
    > 
> Kpts; 

int main() { 
    Kpts kpts; 
    for (int i=0; i<1000000; ++i) { 
     if (i%10000==0) std::cout << "." << std::flush; 
     kpts.insert(Kpt(0.1,0.1,0.1,0.1)); 
    } 
} 

Answer 1

好了，現在我明白你想在該地區[x0,x0+d]×[x1,x1+d]×[y0,y0+d]×[y1,y1+d]搜索4維穴，對不對？

嗯，我不敢說Boost.MultiIndex不是正確的工具，因爲獲取索引＃0，＃1，＃2，＃3中的交集範圍只能通過掃描其中一個範圍（例如＃0）並手動驗證遍歷點的剩餘座標(x1, y0, y1)是否位於感興趣區域內（std::set_intersection），因爲它要求比較範圍按照相同的標準排序，所以在此不一定適用，但情況並非如此我們的指數）。

boost::geometry::index::rtree或者某些類似的空間數據結構很可能，正如你所指出的，更適合這項工作。