Re: [boost] [Intrusive] [MultiIndex] Random Access mental model?

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 <joaquin-AT-tid.es> 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<>
{
    public:
    typedef Key    key_type;
    typedef Value  value_type;

    Key   key_;
    Value value_;

    MyClass()
       :  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){
       uset.insert(values[i]);
       lru_list.push_front(values[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
    lru_list.pop_front();
    //Erase it from the map from an iterator
    //obtained from the value
    uset.erase(uset.iterator_to(v));

    return 0;
}