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