on Sat Nov 01 2008, Ion Gaztañaga <igaztanaga-AT-gmail.com> wrote:
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)); }
Mine is already nothrow unless you have a throwing hash or equality comparison, but yes, it's always better if you can map from addresses to iterators.
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; }
C'mon, it was just an untested sketch. Obviously I can handle that case.
Supposing you want to avoid duplicate values then
I have no need for duplicate values but I don't especially need the map to do anything to avoid them.
// 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); }
Is that Boost.Intrusive code or...?
Please let me know if the example was helpful or I'm wrong
It could be helpful if it is pointing the way to do this most efficiently with Boost.Intrusive. There's not quite enough detail there for me to tell yet, but at least now I'm motivated to look into it further. Wow, that's a cool library! I didn't know it had avl trees, splay trees, scapegoat trees, ... etc. Cheers, -- Dave Abrahams BoostPro Computing http://www.boostpro.com