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

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