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.