Boost C++ Libraries

The size overhead for a hashed container is moderate: 1 pointer per value plus a bucket array per container. The size of an element of the bucket array is usually one pointer. To obtain a good performance hashed container, the bucket length is usually the same as the number of elements that the container contains, so a well-balanced hashed container (bucket_count() is equal to size() ) will have an equivalent overhead of two pointers per element.

An empty, non constant-time size unordered_set or unordered_multiset has also the size of bucket_count() pointers.

Insertions, erasures, and searches, have amortized constant-time complexity in hashed containers. However, some worst-case guarantees are linear. See unordered_set or unordered_multiset for complexity guarantees of each operation.

Be careful with non constant-time size hashed containers: some operations, like empty(), have linear complexity, unlike other Boost.Intrusive containers.

unordered_set and unordered_multiset share the same hooks. This is an advantage, because the same user type can be inserted first in a unordered_multiset and after that in unordered_set without changing the definition of the user class.

template <class ...Options>
class unordered_set_base_hook;

template <class ...Options>
class unordered_set_member_hook;

unordered_set_base_hook and unordered_set_member_hook receive the same options explained in the section How to use Boost.Intrusive:

Apart from them, these hooks offer additional options:

template<class T, class ...Options>
class unordered_set;

template<class T, class ...Options>
class unordered_multiset;

As mentioned, unordered containers need an auxiliary array to work. Boost.Intrusive unordered containers receive this auxiliary array packed in a type called bucket_traits (which can be also customized by a container option). All unordered containers receive a bucket_traits object in their constructors. The default bucket_traits class is initialized with a pointer to an array of buckets and its size:

#include <boost/intrusive/unordered_set.hpp>

using namespace boost::intrusive;

struct MyClass : public unordered_set_base_hook<>
{};

typedef unordered_set<MyClass>::bucket_type     bucket_type;
typedef unordered_set<MyClass>::bucket_traits   bucket_traits;

int main()
{
   bucket_type buckets[100];
   unordered_set<MyClass> uset(bucket_traits(buckets, 100));
   return 0;
}

Each hashed container needs its own bucket traits, that is, its own bucket vector. Two hashed containers can't share the same bucket_type elements. The bucket array must be destroyed after the container using it is destroyed, otherwise, the result is undefined.

unordered_set and unordered_multiset receive the same options explained in the section How to use Boost.Intrusive:

And they also can receive additional options:

Now let's see a small example using both hooks and both containers:

#include <boost/intrusive/unordered_set.hpp>
#include <vector>
#include <algorithm>
#include <boost/functional/hash.hpp>

using namespace boost::intrusive;

class MyClass : public unordered_set_base_hook<>
{               //This is a derivation hook
   int int_;

   public:
   unordered_set_member_hook<> member_hook_; //This is a member hook

   MyClass(int i)
      :  int_(i)
   {}

   friend bool operator== (const MyClass &a, const MyClass &b)
   {  return a.int_ == b.int_;  }

   friend std::size_t hash_value(const MyClass &value)
   {  return std::size_t(value.int_); }
};

//Define an unordered_set that will store MyClass objects using the base hook
typedef unordered_set<MyClass>    BaseSet;

//Define an unordered_multiset that will store MyClass using the member hook
typedef member_hook<MyClass, unordered_set_member_hook<>, &MyClass::member_hook_>
   MemberOption;
typedef unordered_multiset< MyClass, MemberOption>  MemberMultiSet;

int main()
{
   typedef std::vector<MyClass>::iterator VectIt;
   typedef std::vector<MyClass>::reverse_iterator VectRit;

   //Create a vector with 100 different MyClass objects
   std::vector<MyClass> values;
   for(int i = 0; i < 100; ++i)  values.push_back(MyClass(i));

   //Create a copy of the vector
   std::vector<MyClass> values2(values);

   //Create a bucket array for base_set
   BaseSet::bucket_type base_buckets[100];

   //Create a bucket array for member_multi_set
   MemberMultiSet::bucket_type member_buckets[200];

   //Create unordered containers taking buckets as arguments
   BaseSet base_set(BaseSet::bucket_traits(base_buckets, 100));
   MemberMultiSet member_multi_set
      (MemberMultiSet::bucket_traits(member_buckets, 200));

   //Now insert values's elements in the unordered_set
   for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it)
      base_set.insert(*it);

   //Now insert values's and values2's elements in the unordered_multiset
   for(VectIt it(values.begin()), itend(values.end()),
             it2(values2.begin()),itend2(values2.end())
      ; it != itend; ++it, ++it2){
      member_multi_set.insert(*it);
      member_multi_set.insert(*it2);
   }

   //Now find every element
   {
      VectIt it(values.begin()), itend(values.end());

      for(; it != itend; ++it){
         //base_set should contain one element for each key
         if(base_set.count(*it) != 1)           return 1;
         //member_multi_set should contain two elements for each key
         if(member_multi_set.count(*it) != 2)   return 1;
      }
   }
   return 0;
}

Instead of using the default bucket_traits class to store the bucket array, a user can define his own class to store the bucket array using the bucket_traits<> option. 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;
};

The following bucket traits just stores a pointer to the bucket array but the size is a compile-time constant. Note the use of the auxiliary unordered_bucket and unordered_bucket_ptr utilities to obtain the type of the bucket and its pointer before defining the unordered container:

#include <boost/intrusive/unordered_set.hpp>
#include <boost/functional/hash.hpp>
#include <vector>

using namespace boost::intrusive;

//A class to be inserted in an unordered_set
class MyClass : public unordered_set_base_hook<>
{
   int int_;

   public:
   MyClass(int i = 0) : int_(i)
   {}

   friend bool operator==(const MyClass &l, const MyClass &r)
      {  return l.int_ == r.int_;   }
   friend std::size_t hash_value(const MyClass &v)
      {  return boost::hash_value(v.int_); }
};

//Define the base hook option
typedef base_hook< unordered_set_base_hook<> >     BaseHookOption;

//Obtain the types of the bucket and the bucket pointer
typedef unordered_bucket<BaseHookOption>::type     BucketType;
typedef unordered_bucket_ptr<BaseHookOption>::type BucketPtr;

//The custom bucket traits.
class custom_bucket_traits
{
   public:
   static const int NumBuckets = 100;

   custom_bucket_traits(BucketPtr buckets)
      :  buckets_(buckets)
   {}

   //Functions to be implemented by custom bucket traits
   BucketPtr   bucket_begin() const {  return buckets_;  }
   std::size_t bucket_count() const {  return NumBuckets;}

   private:
   BucketPtr buckets_;
};

//Define the container using the custom bucket traits
typedef unordered_set<MyClass, bucket_traits<custom_bucket_traits> > BucketTraitsUset;

int main()
{
   typedef std::vector<MyClass>::iterator VectIt;
   std::vector<MyClass> values;

   //Fill values
   for(int i = 0; i < 100; ++i)  values.push_back(MyClass(i));

   //Now create the bucket array and the custom bucket traits object
   BucketType buckets[custom_bucket_traits::NumBuckets];
   custom_bucket_traits btraits(buckets);

   //Now create the unordered set
   BucketTraitsUset uset(btraits);

   //Insert the values in the unordered set
   for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it)
      uset.insert(*it);

   return 0;
}