Boost logo

Boost :

Subject: Re: [boost] [Intrusive] [MultiIndex] Random Access mental model?
From: David Abrahams (dave_at_[hidden])
Date: 2008-11-01 16:30:06

on Sat Nov 01 2008, Ion Gaztañaga <> wrote:

> 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.

I know. I think you must misunderstand me. When I wrote of using "a
value_type that holds an additional pointer" I meant that I would build
the FIFO queue using the hash nodes, roughly:

      // Totally untested!!
      // My values happen to be default constructible; if they
      // weren't and Boost.Intrusive could help, I might take
      // advantage of it. Otherwise, I know how to take care of
      // it myself but I am trying to keep this posting simple.

      template <class Key, class Value>
      struct fifo_value
          fifo_value() : next(0) {}
          fifo_value(Value v, Key* next = 0) : value(v), next(next) {}

          Value value;
          Key* next;

      template <class Key, class Value>
      struct fifo_hashmap
            : head(&last), tail(&head)

          // Insert the key with no value
          void insert_key(Key k)
          // Has the value been pushed onto the FIFO?
          bool has_value(Key k) const
               typename map_type::iterator pos = map.find(k);
               return pos != map.end() && pos->;

          // Has the key been inserted in the map?
          bool mapped(Key k) const
               return map.find(k) != map.end();

          // push a value for the given key onto the FIFO
          void push(Key const& k, Value const& v)
              typename map_type::iterator pos
                = map.insert(k, fifo_value(v, &last));
              *tail = &pos->first;
              tail = &pos->;
          // Pop the first value off of the FIFO
          void pop()
              Key* h = head;
              typename map_type::iterator pos = map.find(*h);
              head = pos->;
            typedef unordered_map<key, fifo_value<key, value> > map_type;

            map_type map;
            Key* head;
            Key** tail;
            static Key last;

That implements pretty much all the operations I need.

> 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 know.

Dave Abrahams
BoostPro Computing

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