How to modify key values in std::map container

Question

Given

std::map<int,std::string> myMap;
fillMyMapWithStuff(myMap);

// modify key values - I need to add a constant value to each key
for (std::map<int,std::string>::iterator mi=myMap.begin(); mi != myMap.end(); ++mi)
{
    // ...
}

Whats a good way apply some re-indexing? Must I remove the old entry and add a new one with the new key and old value?

Answer 1

Yes, you must. The key is const while it is in the map.

Answer 2

Yes, you have to remove the old entry and add a new one with the new key. Keys are not modifiable.

If you were modifying only one or a few elements, you could do it efficiently by hinting map::insert with the position of the new element. Since your new keys are sure to be located somewhere after the old keys, you can hint with the iterator that points at the old element. However, you'd have to take care not to re-evaluate the freshly-inserted keys (by iterating end to front for example), and in case of modifying the entire map, it's more efficient to just build a new one.

Answer 3

Looks like you are better off building a new map and swapping it afterward. You'll have only n insert operations instead of n deletions and n insertions.

Answer 4

I think you'll have to construct a new map. If you delete and add new keys within the loop, it might destroy the integrity of iterating over the set of old keys, and not touching the just-inserted keys. (Unless you know how your keys are distributed and put your own logic in there.)

std::map<int,std::string> myMap;
fillMyMapWithStuff(myMap);

std::map<int,std::string> newMap;

// modify key values - I need to add a constant value to each key
for (std::map<int,std::string>::iterator mi=myMap.begin(); mi != myMap.end(); ++mi)
{
    newMap[mi->first] = mi->second;
}

Answer 5

There's one more option. If this operation is a significant feature of your collection, and performance is important, you can avoid copying the map altogether. You can create a class overloading operator[], as well as other accessors and mutators, and add the current shift of the key value.