Boost logo

Boost :

Subject: Re: [boost] [Intrusive] [MultiIndex] Random Access mental model?
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2008-11-01 15:39:20

David Abrahams wrote:
> on Sat Nov 01 2008, JOAQUIN M. LOPEZ MUÑOZ <> wrote:
>>> Actually, MultiIndex could give me *almost* everything I need by
>>> threading a singly-linked list through the hash nodes (instead of
>>> doubly-linked). That's enough for a FIFO queue.
>> You can do that with Boost.Intrusive, and that will indeed save you
>> one pointer per node as compared with the Boost.MultiIndex-based
>> solution. If you're resorting to manually combining a hash_map and
>> a slist<pointer> then you'd begaining nothing, as in the hash_map+
>> deque<pointer> case described in my previous post.
>>> Turns out I need a little more than that; I essentially need a bool that
>>> tells me whether the node is in the FIFO queue yet. Since I can use a
>>> NULL queue pointer for that purpose, it looks like I'll be rolling my
>>> own.
> I handn't looked at Boost.Intrusive before. While it looks interesting,
> it seems pretty complicated and I can't quite see any point in using it
> when I could just use Boost.Unordered with a value_type that holds an
> additional pointer. Maybe I'm missing something; I don't know.

The point of using Intrusive is that you only allocate once instead of
one for every container. When we use two STL-like containers we are
allocating dynamic memory so we have a size payload for each allocation
from the memory allocator (usually 1 or 2 pointers). I haven't followed
the thread but in your first post you say you need an unordered map and
a list of values to obtain fast access to the first element. Intrusive
is a bit low-level, because you need to allocate values yourself and
then insert them in intrusive containers (and there are no maps only
sets) but this offers some advantages as can allocate several values
(burst allocation) in a vector to minimize any memory payload and speed
up the insertion. With Intrusive a combination of a hash multiset and a
singly linked list might seem like this:

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

using namespace boost::intrusive;

template<class Key, class Value>
class MyClass
    : public unordered_set_base_hook<>
    , public slist_base_hook<>
    typedef Key key_type;
    typedef Value value_type;

    Key key_;
    Value value_;

       : key_(), value_()

    MyClass(const Key &k, const Value &v)
       : key_(k), value_(v)

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

    friend std::size_t hash_value(const MyClass &value)
       using boost::hash_value;
       return hash_value(value.key_);

//Comparison functor to search a value from a key
template<class MyClass>
struct key_value_compare
    typedef typename MyClass::key_type key_type;

    bool operator()(const key_type &k, const MyClass &v) const
    { return k == v.key_; }

    bool operator()(const MyClass &v, const key_type &k) const
    { return v.key_ == k; }

//Hash functor to search a value from a key
template<class Key>
struct key_hasher
    std::size_t operator()(const Key &k) const
       using boost::hash_value;
       return hash_value(k);

typedef MyClass<int, std::string> value_type;
typedef key_value_compare<value_type> key_value_comp;
typedef key_hasher<int> key_hash;

//Define an unordered_set that will link value_types
typedef unordered_multiset<value_type> Umset;
//Define a singly linked list the will link value_types
typedef slist<value_type> Slist;

int main()
    //Create a vector with 100 different value_type objects
    std::vector<value_type> values(100);
    for(int i = 0; i < 100; ++i)
       values[i].key_ = i;

    //Intrusive containers don't allocate so
    //bucket array must be provided externally
    Umset::bucket_type buckets[100];

    //Link values in an unordered set and a slist
    Umset uset(Umset::bucket_traits(buckets, 100));
    Slist lru_list;

    //Insert values in both containers
    for(int i = 0; i < 100; ++i){

    //Search an element using a whole value_type
    for(int i = 0; i < 100; ++i){
       value_type search_this(i, "");
       if(uset.end() == uset.find(search_this))
          return 1;

    //Search an element using a custom predicate instead of
    //building a whole value_type
    for(int i = 0; i < 100; ++i){
       if(uset.end() == uset.find(i, key_hash(), key_value_comp()))
          return 1;

    //Obtain most recent value...
    value_type &v = lru_list.front();
    //Erase value from lru
    //Erase it from the map from an iterator
    //obtained from the value

    return 0;

Boost list run by bdawes at, gregod at, cpdaniel at, john at