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

Subject: Re: [boost] [Intrusive] [MultiIndex] Random Access mental model?
From: David Abrahams (dave_at_[hidden])
Date: 2008-11-01 20:10:13

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