Re: [boost] Does Boost has an utility to replace all OLD Keys with NEW one for MultiMap/Map?

Subject: Re: [boost] Does Boost has an utility to replace all OLD Keys with NEW one for MultiMap/Map?
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-05-07 13:01:06

Tushar Chowdhury wrote:
> As of now I failed to get such an algo. I've come up with an proposed
> solution. Please verify:

Hi Tushar,

I'm not aware of anything that does this in Boost, though maybe someone 
who knows more about e.g. Boost.Range can suggest something.

To get O((log N) + M) time-complexity (where N is the size of the 
container and M is the number of affected elements), rather than O(M 
log N), you need to do something like this:

- Get the affected range using std::multimap::equal_range.
- Insert new elements using the version of std::multimap::insert that 
takes an insertion location hint.
- Erase the old elements using the version of std::multimap::erase that 
takes an iterator.

You have the choice of either erasing the old elements individually as 
you go, or erasing them all at the end.  I can't say which would be quicker.

How about:

template <typename CONT>
void replace_key(CONT& cont, typename CONT::key_type oldk, typenamme 
CONT::key_type newk)
{
   if (newk==oldk) return;

   typedef typename CONT::iterator iter;
   std::pair<iter,iter> r = cont::equal_range(oldk);
   iter hint = cont.begin();
   for (iter i = r.first; i != r.second; ++r) {
     hint = cont.insert(hint,std::make_pair(newk,i->second));
   }
   cont.erase(r.first,r.second);
}

Two snags with that:
- I'm using the insert hint wrongly, I think.  IIRC you need to iterate 
backwards to get the hint to work.
- I'm not convinced that the loop termination is right.  If I had 
elements with keys 1 and 3 and I tried to replace 1 with 2, then the 
end iterator returned by equal_range would point to the first element 
with key 3.  This would be wrong as soon as a 2 element was inserted.  
(Does Boost.Range do anything to work around this?)

Conveniently, I believe that the same fix (i.e. iterating backwards) 
solves both.  Left as an exercise :-)  (Oh, except that the erase would 
still erase the wrong elements in that case.)

Phil.