부스트 :: multi_index_container, 운영 :: 컨테이너

Question

안에 설정 나는 컨테이너 클래스를 통해 부스트 :: multi_index_container (containerSet)를 생성 std::string 및 std::set<int>하여 containerSet 색인했습니다. 특정의 int를 세트 내에 포함하고있는 컨테이너를 취득 할 수 있을지 어떨지 또한 int1과 int2 사이에 적어도 하나의 값을 저장하는 모든 컨테이너를 얻을 수 있습니까? 세트와

#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/member.hpp> 
#include <boost/multi_index/ordered_index.hpp> 
#include <boost/multi_index/hashed_index.hpp> 
#include <boost/format.hpp> 
#include <boost/lambda/core.hpp> 
#include <iostream> 

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

class Container { 
public: 
    std::set<int> set; 
    std::string name; 

    Container(std::string name, std::set<int> set); 
    ~Container(); 

    friend std::ostream& operator<<(std::ostream& os,const Container& c) { 
     os << c.name << ", [ "; 
     for (int i : c.set) { 
      os << i << " "; 
     } 
     os << "]"; 
     return os; 
    } 
}; 

Container::Container(std::string name = "noName", std::set<int> set = {}) : name{name} ,set{set} {} 
Container::~Container() {} 

struct setTag{}; 
struct nameTag{}; 

typedef multi_index_container<Container, indexed_by< 
     ordered_unique<tag<nameTag>, BOOST_MULTI_INDEX_MEMBER(Comp, std::string, name)>, 
     ordered_unique<tag<setTag>, BOOST_MULTI_INDEX_MEMBER(Comp, std::set<int>, set)> 
>> ContainerSet; 

//don't see how I could get the compare structs to work, because 
//a) can't fullfill the strict weak odering requirements and 
//b) because of the setTag ordering, not all set's get called 
struct compSetRange { 
     bool operator()(int x,const std::set<int> &c) const {} 
     bool operator()(const std::set<int> &c, int x) const {} 
}; 
struct compSetFind { 
    bool operator()(int x,const std::set<int> &c) const {} 
    bool operator()(const std::set<int> &c, int x) const {} 
}; 

int main() { 
    Container c1{"c1", {5, 6, 7, 18, 61, 77}}; 
    Container c2{"c2", {2, 4, 5, 21, 36, 88, 99}}; 
    Container c3{"c3", {2, 3, 9, 10, 65, 75, 91}}; 
    ContainerSet cs; 
    cs.insert(c1); 
    cs.insert(c2); 
    cs.insert(c3); 

    std::cout << "print by name (ordered)" << std::endl; 
    for (auto e : cs.get<nameTag>()) { 
     std::cout << e << std::endl; 
    } 
    std::cout << std::endl; 

    std::cout << "print by set (ordered)" << std::endl; 
    for (auto e : cs.get<setTag>()) { 
     std::cout << e << std::endl; 
    } 
    std::cout << std::endl; 

    typedef ContainerSet::index<setTag>::type compBySetIndex; 
    //find(std::set) works but isn't useful in my case 
    compBySetIndex::iterator it1 = cs.get<setTag>().find(std::set<int>{2, 4, 5, 21, 36, 88, 99}); 
    //TODO: find all comps with int 5 -> c1 and c2 
// compBySetIndex::iterator it1 = cs.get<setTag>().find(200, compSetFind()); 
    if (it1 !=cs.get<setTag>().end()) { 
     std::cout << *it1 << std::endl; 
    } 

    //TODO: find all container with values between 70 and 80 -> c1 and c3 
// compBySetIndex::iterator it1_low = cs.get<setTag>().lower_bound(70, compSetRange()); 
// compBySetIndex::iterator it1_upp = cs.get<setTag>().upper_bound(80, compSetRange()); 

    //.range() also not applicable 

    return 0; 
} 

:
내가 ...find(5);를 호출하고 다음의 호출에 적어도 c2, 어쩌면 c1를 얻을 수 있기를 원하는 c3 = {2, 3, 9, 10, 65, 75, 91}
c2 = {2, 4, 5, 21, 36, 88, 99}
c1 = {5, 6, 7, 18, 61, 77}
. 이것은 오른쪽 Compare 함수로 수행 할 수 있지만 operator() 함수를 만드는 방법을 생각할 수 없다. compatible.
...lower_bounds(70) 및 ...upper_bounds(80) 이후에 나는 c3과 c1을 얻어야합니다. std :: set의 순서로 인해이 요구 사항은 부스트와 함께 달성 할 수없는 것처럼 보입니다.

내가 누락 된 항목이 있습니까? 미리 감사드립니다!

---

나는 내 목표를 달성하기 위해 모든 컨테이너과 세트를 통해 선형 검색을 할 수있는 알고 있지만, 그것은 multi_index_container의 성능 이점을 부정하는 것입니다. 부스트가이 직업에 대한 잘못된 도구 인 경우 개별 번호 class containerSet에 의지해야합니다.

Answer 1

앤드류는 문제를 아주 정확하게 진단했습니다.

도움을 받으려면 Boost : Boost Interval Container에 널리 사용되지 않는 라이브러리를 광고하십시오.

이 데모가 Boost ICL이 얼마나 유용 할 수 있는지에 대해 알 수 있기를 바랍니다.

Live On Coliru

#include <boost/icl/separate_interval_set.hpp> 
#include <boost/icl/interval_map.hpp> 

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

#include <iostream> 
#include <numeric> 
#include <vector> 

using Set = std::set<int>; 

struct io_wrap { Set const& ref; }; 
static std::ostream& operator<<(std::ostream& os,const io_wrap& s) { os << "[ "; for (auto i : s.ref) os << i << " "; return os << ']'; } 

namespace icl = boost::icl; 
namespace bmi = boost::multi_index; 

struct Record { 
    std::string name; 
    Set set; 

    Record(std::string name = "noName", Set set = {}) : name{name}, set{set} {} 

    friend std::ostream& operator<<(std::ostream& os,const Record& c) { return os << c.name << ", " << io_wrap{c.set}; } 
}; 

using Map  = icl::interval_map<int, std::set<Record const*> >; 
using Interval = Map::interval_type; 
using Table = bmi::multi_index_container< 
     std::reference_wrapper<Record>, 
     bmi::indexed_by< 
      bmi::ordered_unique< 
       bmi::tag<struct byName>, 
       bmi::member<Record, std::string, &Record::name> 
      > 
     > 
    >; 

auto interval_set(Set const& is) { return std::accumulate(is.begin(), is.end(), icl::interval_set<int> { }); } 
auto envelope(Record const& r) { return hull(interval_set(r.set)); } 

void insert(Map& into, Set const& is, std::set<Record const*> const& rs = {}) { 
    for (auto i : interval_set(is)) 
     into += Map::value_type { i, rs }; 
} 

int main() { 

    //////////////////////////////// 
    // Prepare data 
    std::vector<Record> backing_storage { 
     {"c3", {2, 3, 9, 10, 65, 75, 91}}, 
     {"c1", {5, 6, 7, 18, 61, 77}}, 
     {"c2", {2, 4, 5, 21, 36, 88, 99}}, 
     // outliers 
     {"c4", {0}}, 
     {"c5", {200}}, 
    }; 

    Table const byname(backing_storage.begin(), backing_storage.end()); 
    Map cs; 
    for (auto& r : backing_storage) 
     insert(cs, r.set, { &r }); 

    //////////////////////////////// 
    // Usage demos 
    std::cout << "print by name (ordered)\n"; 
    for (auto const& e : byname) { std::cout << " - " << e << " - envelope: " << envelope(e) << "\n"; } 
    std::cout << "\n"; 

    auto perform_match = [&cs](auto key) { 
     Map::codomain_type matches; 
     Map::codomain_combine combine; 

     for (auto p : cs & key) 
      combine(matches, p.second); 

     std::cout << "matching " << key << ":\n"; 
     for (auto const* r : matches) 
      std::cout << " - " << *r << "\n"; 
     std::cout << "\n"; 
    }; 

    for (auto key : { Set{2}, {99}, {2,99}, {2,99,5} }) { 
     perform_match(interval_set(key)); 
    } 

    perform_match(Interval::right_open(70, 81)); 
} 

인쇄 :

print by name (ordered) 
- c1, [ 5 6 7 18 61 77 ] - envelope: [5,77] 
- c2, [ 2 4 5 21 36 88 99 ] - envelope: [2,99] 
- c3, [ 2 3 9 10 65 75 91 ] - envelope: [2,91] 
- c4, [ 0 ] - envelope: [0,0] 
- c5, [ 200 ] - envelope: [200,200] 

matching {[2,2]}: 
- c3, [ 2 3 9 10 65 75 91 ] 
- c2, [ 2 4 5 21 36 88 99 ] 

matching {[99,99]}: 
- c2, [ 2 4 5 21 36 88 99 ] 

matching {[2,2][99,99]}: 
- c3, [ 2 3 9 10 65 75 91 ] 
- c2, [ 2 4 5 21 36 88 99 ] 

matching {[2,2][5,5][99,99]}: 
- c3, [ 2 3 9 10 65 75 91 ] 
- c1, [ 5 6 7 18 61 77 ] 
- c2, [ 2 4 5 21 36 88 99 ] 

matching [70,81): 
- c3, [ 2 3 9 10 65 75 91 ] 
- c1, [ 5 6 7 18 61 77 ]