How To Update Your Const Key Fields in a Map/Multimap

Introduction

This is not a typical C++/STL article. Instead it is an observation which I faced in my professional programming life. The idea is simple, but the effect/impact is broad. Here I am going to provide a little utility that can take back a big effort while you are doing something same.

Background

What makes a Map/Multimap beautiful? Yes you guessed it right - A key-value field type container. If you have a look in the definition of STL Map/Multimap, you'll find something like this:

template <typename K, typename V,
          typename Compare = less<K>,
          typename Allocator = allocator<pair<const K, V> > >
class map; 

template <typename K, typename V,
          typename Compare = less<K>,
          typename Allocator = allocator<pair<const K, V> > >
class multimap;

So the definition looks pretty much the same, the only difference is Map never allows you to have duplicate keys, whereas Multimap allows.

Another observation/constraint is the Key field in a Map/Multimap is always constant. Once populated, you can't change/update the Key field in a conventional way, and there is a good reason behind this:

Because Map/Multimap sorts the elements based on their keys (along with the sorting functor (default is std::less, however you are free to change it to std::greater or your own functor) ) and assign the keys in a internal Red-black tree structure, if you or any generic algorithm updates the key field, that Red-Black tree will be invalid. The whole Tree might need to re-shuffle, which is quite a time consuming process. That is why STL designers takes the decision of:

You can't update the key field of a map/multimap in a conventional way.

You can't use map/multimap as a destination in a generic algorithm that updates the container.

But what if - you need to update your map/multimap's key field ? Sometimes it is damn necessary. Say initially you have a Multimap like this:

Now you've to update the key "Allen" with "Gary". How will you do that?

You've only one choice left:

To modify the key of an element, you must remove the element that has the old key and insert a new element that has the new key and old value.

So, how can you do that by using a Generic Function?

Using the Code

Generic functions are good, specially when if you make it detachable from a container. In order to solve the above mentioned problem: my strategy is to write a generic function like this:

namespace My_Utility{
template <typename CONTAINER>
    void replace_key(CONTAINER& container,
                     const typename CONTAINER::key_type& oldKey,
                     const typename CONTAINER::key_type& newKey)
    {
        if(!container.key_comp()(oldKey,newKey) && !container.key_comp()(newKey,oldKey)){
	    return;} //Thanks to Graham for this Fix
        typename CONTAINER::iterator begin(container.find(oldKey));
        for(;;){
            if(begin != container.end()){
                container.insert(typename CONTAINER::value_type(newKey, begin->second));
                container.erase(begin); // Thanks to Graham for this potential fix
                begin = container.find(oldKey);
            }
            else{
                return;
            }
        }
    }
}

This is purely a Generic function. Given below is its description: 

1. The template definition takes a single template parameter named CONTAINER (which can be either Map of Multimap).
2. The argument list takes a Container, a const old key and a const new key, please see both the types of old key and newkey are fetched from the templated type. So this is purely generic.
3. First check and return if Old key and New Key are equal, we don't need to update anything in that case. 
4. If Old key and New key differ, then the function does as follows: 

   It finds the first iterator position where the old key exists, then it starts an infinite loop, which breaks when the iterator contains a value container.end(). Keep in mind that the find() algorithm returns cont.end() if it finds nothing, and returns the first iterator position when search is successful.

   If begin!=container.end(), then the function inserts a new row. Please see the code carefully.

   Then it erases the old row. Please see the code. It is:

   C++

   container.erase(begin);

   Then again a find() call.

Please use this code when you need to solve a similar kind of problem.  

History

• 11^th May, 2009: Initial post