Click here to Skip to main content
15,846,571 members
Articles / Programming Languages / C++

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

Rate me:
Please Sign up or sign in to vote.
4.96/5 (25 votes)
11 May 2009CPOL3 min read 40K   16   8
An introduction to the necessary steps for updating const key fields in a map/multimap


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.


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));
            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);

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:


    Then again a find() call.

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


  • 11th May, 2009: Initial post


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Written By
Software Developer (Senior) Rebaca Technologies
India India
int main(){
return 0;

Comments and Discussions

GeneralMy vote of 5 Pin
Manoj Kumar Choubey28-Feb-12 19:01
professionalManoj Kumar Choubey28-Feb-12 19:01 
GeneralMy vote of 5 Pin
Rahul Rajat Singh17-Feb-12 20:15
professionalRahul Rajat Singh17-Feb-12 20:15 
GeneralMy vote of 4 Pin
John Schroedl18-May-11 6:09
professionalJohn Schroedl18-May-11 6:09 
GeneralGreat artical Pin
ed welch12-Jun-09 3:23
ed welch12-Jun-09 3:23 
GeneralRe: Great artical Pin
programmersmind13-Jun-09 9:21
programmersmind13-Jun-09 9:21 
GeneralA couple of bugs PinPopular
Graham Shanks11-May-09 2:03
Graham Shanks11-May-09 2:03 
GeneralRe: A couple of bugs Pin
programmersmind11-May-09 2:39
programmersmind11-May-09 2:39 
GeneralRe: A couple of bugs Pin
Graham Shanks11-May-09 3:46
Graham Shanks11-May-09 3:46 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.