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

Subject: Re: [boost] [Intrusive] [MultiIndex] Random Access mental model?
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2008-11-01 20:30:42

David Abrahams <dave <at> boostpro.com> writes:

> 
> 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:
[...]

Not that this has to do with the multi-indexing capabilities
of Boost.MultiIndex, but I think you can still take (a little)
advantange of the lib by using a multi_index_container<hashed_unique>
instead of a unordered_map, because the former has an iterator_to()
member function that allows you to retrieve an iterator from
a value_type*, so saving you the jump from Key* to an iterator
via map.find() that your code has at pop(). Untested code based
on yours follows:

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

      Key key;
      mutable Value value;
      mutable const fifo_value* 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.insert(value_type(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->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)
      {
        std::pair<typename map_type::iterator,bool> p
            = map.insert(value_type(k, v, &last));
        if(!p.second)p.first->value=v;

        *tail = &*p.first;
        tail = &p.first->next;
      }

      // Pop the first value off of the FIFO
      void pop()
      {
          // Here I don't need to do map.find(...)

          const value_type* h = head;
          typename map_type::iterator pos = map.iterator_to(*h);
          head = pos->next;
          map.erase(pos);
      }

   private:
       typedef fifo_value<Key, Value> value_type;
        typedef multi_index_container<
          value_type,
          indexed_by<
            hashed_unique<member<value_type, Key, &value_type::key> >
          >
        > map_type;

        map_type map;
        const value_type* head;
        const value_type** tail;
        static value_type last;
  };

Joaquín M López Muñoz
Telefónica, Investiación y Desarrollo