在boost intrusive中使用向量作为存储桶

Question

如何使用std::vector管理boost::intrusive::unordered_set的存储桶？下面的代码让我做了噩梦：

#include <boost/intrusive/unordered_set.hpp>
#include <vector>
#include <cstdint>

namespace BI = boost::intrusive;

struct ValuableData : public BI::unordered_set_base_hook<>
{
    int  x;
    int  y;
    char c;
};

typedef BI::base_hook<BI::unordered_set_base_hook<>> Options;
typedef BI::unordered_bucket<Options>::type     BucketType;
typedef BI::unordered_bucket_ptr<Options>::type BucketPtr;

struct VectorTraits{

    std::vector<BucketType> v;

    BucketPtr bucket_begin(){
        return v.data();
    }

    uint32_t bucket_count() const {
        return v.capacity();
    }
};

struct dumhash{
    uint32_t operator()(const ValuableData &data) const {
        return data.x;
    }
};

struct dumcomp{
    bool operator()(const ValuableData &data, const ValuableData &datb)     const {
    return true;
}
};

typedef BI::unordered_set<ValuableData, 
        BI::hash<dumhash>, 
        BI::equal<dumcomp>,
        BI::bucket_traits<VectorTraits>> MySet;

int main(){

    VectorTraits tr;

    tr.v.reserve(100);
    tr.v.push_back(BucketType()); //.data() may return null is vector is empty.

    MySet set(tr);
    set.rehash(tr);

    return 0;
}

该错误消息指示违反了const限定符。我的boost版本是1.73.0，我的编译器是g++ 10.2.0。我必须使用c++17。

boost intrusive手册提到了const_bucket_ptr，但没有指出如何使用该类型。我怀疑这就是我的bug的来源，请参阅：https://www.boost.org/doc/libs/1_74_0/doc/html/intrusive/unordered_set_unordered_multiset.html#intrusive.unordered_set_unordered_multiset.custom_bucket_traits

编辑:我用一个更简单的例子替换了之前我实际使用的代码，你可以在家里完全编译。以下是我的完整错误消息：

In file included from include/boost/intrusive/unordered_set.hpp:18,
                 from src/BoostIntrusiveSet.cpp:9:
include/boost/intrusive/hashtable.hpp: In instantiation of 'void boost::intrusive::hashtable_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags>::rehash_impl(const bucket_traits&, bool) [with ValueTraits = boost::intrusive::bhtraits<ValuableData, boost::intrusive::slist_node_traits<void*>, boost::intrusive::safe_link, boost::intrusive::dft_tag, 4>; VoidOrKeyOfValue = void; VoidOrKeyHash = dumhash; VoidOrKeyEqual = dumcomp; BucketTraits = VectorTraits; SizeType = long long unsigned int; long long unsigned int BoolFlags = 3; boost::intrusive::hashtable_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags>::bucket_traits = VectorTraits]':
include/boost/intrusive/hashtable.hpp:2944:13:   required from 'void boost::intrusive::hashtable_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags>::rehash(const bucket_traits&) [with ValueTraits = boost::intrusive::bhtraits<ValuableData, boost::intrusive::slist_node_traits<void*>, boost::intrusive::safe_link, boost::intrusive::dft_tag, 4>; VoidOrKeyOfValue = void; VoidOrKeyHash = dumhash; VoidOrKeyEqual = dumcomp; BucketTraits = VectorTraits; SizeType = long long unsigned int; long long unsigned int BoolFlags = 3; boost::intrusive::hashtable_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags>::bucket_traits = VectorTraits]'
src/BoostIntrusiveSet.cpp:64:15:   required from here
include/boost/intrusive/hashtable.hpp:3153:73: error: passing 'const bucket_traits' {aka 'const VectorTraits'} as 'this' argument discards qualifiers [-fpermissive]
 3153 |       const bucket_ptr new_buckets      = new_bucket_traits.bucket_begin();
      |                                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
compilation terminated due to -Wfatal-errors.

Answer 1

documentation声明需要bucket_begin()的常量重载：

用户自定义存储桶特征必须满足以下接口：

类my_bucket_traits { bucket_ptr bucket_begin()；const_bucket_ptr bucket_begin() const；std::size_t bucket_count() const；}；

我不知道为什么你认为你可以安全地使桶特征拥有一个桶容器。该示例所做的是存储指向存储桶的指针。这就解决了问题：

• 存储桶特征是可廉价复制的
• 存储桶的生命周期与特征的副本无关(因为没有所有权)
• 即使特征实例是

，存储桶数据自然也不是恒定的

修复

在这里应用相同的方法：

#include <boost/intrusive/unordered_set.hpp>
#include <vector>
#include <iostream>

namespace BI = boost::intrusive;
struct ValuableData : public BI::unordered_set_base_hook<> {
    int  x = 0;
    int  y = 0;
    char c = 0;
};

using Options    = BI::base_hook<BI::unordered_set_base_hook<> >;
using BucketType = BI::unordered_bucket<Options>::type;
using BucketPtr  = BI::unordered_bucket_ptr<Options>::type;

struct VectorTraits {
    std::vector<BucketType>* v;
    BucketPtr bucket_begin() const { return v->data(); }
    [[nodiscard]] uint32_t bucket_count() const { return v->capacity(); }
};

struct dumhash {
    uint32_t operator()(const ValuableData& data) const { return data.x; }
};

struct dumcomp {
    bool operator()(const ValuableData& data, const ValuableData& datb) const {
        return data.x == datb.x;
    }
};
typedef BI::unordered_set<ValuableData, BI::hash<dumhash>, BI::equal<dumcomp>,
                          BI::bucket_traits<VectorTraits>>
    MySet;

int main() {
    std::vector<BucketType> buckets(13);
    VectorTraits tr { &buckets };

    MySet set(tr);
    set.rehash(tr);

    std::cout << buckets.size() << "\n";
    buckets.resize(57);
    set.rehash(tr);

    std::cout << buckets.size() << "\n";
}

打印

13
57