Boost logo

Boost :

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


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