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:
Key | Value |
Allen | 100 |
Betty | 200 |
Allen | 200 |
Betty | 300 |
John | 500 |
Allen | 900 |
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;} typename CONTAINER::iterator begin(container.find(oldKey));
for(;;){
if(begin != container.end()){
container.insert(typename CONTAINER::value_type(newKey, begin->second));
container.erase(begin); begin = container.find(oldKey);
}
else{
return;
}
}
}
}
This is purely a Generic function. Given below is its description:
- The template definition takes a single template parameter named
CONTAINER
(which can be either Map
of Multimap
). - 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. - First check and return if Old key and New Key are equal, we don't need to update anything in that case.
- 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:
container.erase(begin);
Then again a find()
call.
Please use this code when you need to solve a similar kind of problem.
History
- 11th May, 2009: Initial post