Boost logo

Boost :

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>> 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
        : 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->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));

        *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;

       typedef fifo_value<Key, Value> value_type;
        typedef multi_index_container<
            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

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