Boost logo

Boost :

Subject: Re: [boost] [Intrusive] [MultiIndex] Random Access mental model?
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2008-11-01 19:22:39


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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk