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