Using vector for buckets in boost intrusive

Question

How does one manage the buckets of boost::intrusive::unordered_set with std::vector? The following code gives me nightmares:

#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;
}

The error message indicates a violation of const qualifiers. my boost version is 1.73.0, my compiler g++ 10.2.0. I must used c++17.

The boost intrusive manual mentions the const_bucket_ptr but does not indicate how to reach to that type. I suspect this is the source of my bug, see: 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

EDIT: I replaced the previous code I was actually using with a simpler example you can fully compile at home. Here is my full error message:

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

The documentation states that a const overload for bucket_begin() is required:

A user-defined bucket-traits must fulfill the following interface:

class my_bucket_traits
{
   bucket_ptr        bucket_begin();
   const_bucket_ptr  bucket_begin() const;
   std::size_t bucket_count() const;
};

I'm not sure why you think you can safely make the bucket traits own a bucket container. What the example does is store a pointer to the bucket. This solves the issues:

• the bucket traits is cheaply copyable
• the lifetime of the bucket is not tied to a copy of the traits (because the ownership is not held)
• the bucket data is naturally not const even if the trait instance is

Fixing

Applying the same approach here:

Live On Coliru

#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";
}

Prints

13
57