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