c++ - boost::multi_index_container，对容器内 std::set 的操作

Question

我在容器类上创建了一个 boost::multi_index_container ( containerSet ) 并索引了 containerSet通过 std::string和 std::set<int> .是否有可能获得在其集合中存储特定 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;
}

搭配套装:
c3 = {2, 3, 9, 10, 65, 75, 91}
c2 = {2, 4, 5, 21, 36, 88, 99}
c1 = {5, 6, 7, 18, 61, 77}
我希望能够调用 ...find(5);并至少获得 c2 ，甚至可能是c1在下一次调用时。这可能可以通过正确的比较函数来实现，但我想不出一种方法来制作 operator() 函数 compatible .
此外在 ...lower_bounds(70) 之后和 ...upper_bounds(80)我应该得到 c3和 c1 .由于 std::set 的顺序，这个要求似乎无法通过 boost 实现。

我错过了什么吗？提前致谢!

---

我知道我可以对所有容器及其集合进行线性搜索来实现我的目标，但这会抵消 multi_index_container 的性能优势。如果 boost 是这项工作的错误工具，我将不得不求助于个人 class containerSet .

Answer 1

Andrew 非常准确地诊断了这个问题。

为了帮助您，让我为 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 ]