David Abrahams wrote:
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:
Ok, thanks for the example. The only advantages I see to implement this class with Boost.Intrusive is that pop() could be faster (and no-throw): void pop() { value_type & v = fifo->front(); fifo.pop_front(); //Nothrow map.erase(map.iterator_to(v)); } and that you avoid copies (what happens if the key is already in the map in your example?):
// 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; }
Supposing you want to avoid duplicate values then // push a value for the given key onto the FIFO void push(Key const& k, Value const& v) { typename map_type::insert_commit_data data; //Test if the key is there without constructing //the value if(!map.insert_check(key, key_hasher() , key_mapped_compare(), data).second){ //Already present, return return; } //Success guaranteed, now commit mapped_type *m= new mapped_type(k, v); //Nothrow map.insert_commit(*m, data); //If slist is implemented with cachelast<true> option //you have O(1) push_back() fifo->push_back(*m); } If you allow duplicates then I suppose you meant unordered_multimap instead of unordered_map, so just forget insert_check/insert_commit and do direct insertion: mapped_type *m= new mapped_type(k, v); map.insert(*m, data); fifo->push_back(*m); The drawback is that you need to define a "mapped_type" that stores Value and Key and do the memory management. Please let me know if the example was helpful or I'm wrong (again). Regards, Ion