Re: [boost] [interprocess][multi_index] emplace() is not sufficient for maps

Subject: Re: [boost] [interprocess][multi_index] emplace() is not sufficient for maps
From: Howard Hinnant (howard.hinnant_at_[hidden])
Date: 2009-09-24 12:40:58

On Sep 24, 2009, at 11:47 AM, Howard Hinnant wrote:

> typedef ... map;
> map m;
> map::node_ptr p = m.remove(m.emplace_hint(m.begin(),  
> my_special_cheap_key_value, mv1, mv2));
> p->first = modify( p->second );
> m.insert( boost::move(p) );

One further point that I hadn't realized until now:

Assuming map is a red-black tree:

If the new node is inserted either at the minimum of the tree (left  
most), or the maximum of the tree (right most), then that new node  
will have two properties (even after rebalancing):

1.  It will have no children.
2.  It will be red.

This means that the subsequent remove (if it happens without further  
intervening insertions) will not cause a rebalance.  Removing a red  
node with no children is as cheap as it gets for red black tree node  
removal.  So for those using this technique, it would be good to make  
my_special_cheap_key_value either less than all valid key values, or  
greater than all valid key values, and adjust the insertion hint  
accordingly.

-Howard