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

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 <igaztanaga-AT-gmail.com> wrote:

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

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
      {
          fifo_hashmap()
            : head(&last), tail(&head)
          {}

          // Insert the key with no value
          void insert_key(Key k)
          {
              map[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->second.next;
          }

          // 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->second.next;
          }
      
          // Pop the first value off of the FIFO
          void pop()
          {
              Key* h = head;
              typename map_type::iterator pos = map.find(*h);
              head = pos->second.next;
              map.erase(pos);
          }
      
       private:
            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
http://www.boostpro.com