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.