CODEWITHSUNDEEP
c++stdmap
user2121418
user2121418

Reputation: 31

C++ - Modifying key for all map elements

Let's consider this code:

std::map< int, char > charMap;
for( auto& i : charMap )
{
    charMap[ i.first + 1 ] = charMap[ i.first ];
    charMap.erase( i.first );
}

Let's say that the map has some values with randomed keys. I am trying to shift the keys by 1. This won't work because the loop goes on forever. Is there a fast way to make it work?

Upvotes: 2

Views: 372

Answers (3)

Kerrek SB
Kerrek SB

Reputation: 476930

In C++17, you can use node extraction and splicing (see P0083R3):

std::map<int, char> tmpMap;

for (auto it = charMap.begin(); it != charMap.end(); )
{
    auto nh = charMap.extract(it++);   // node handle
    ++nh.key();
    tmpMap.insert(tmpMap.end(), std::move(nh));
}

tmpMap.swap(charMap);

The loop extracts consecutive map nodes, mutates them, and reinserts the node into tmpMap (now with the different key). At the end, charMap is empty and tmpMap contains all the elements with their modified keys, so we swap the two.

Before C++17, you would have to copy (or move) the value data around to insert a new element with a new key.

std::map<int, char> tmpMap;

for (auto & p : charMap)
    tmpMap.emplace_hint(tmpMap.end(), p.first + 1, std::move(p.second));

tmpMap.swap(charMap);

This requires memory allocations for the nodes, though, so the new splicing-based solution is more efficient.

In either case we can use the hinted insertion, because we are reconstructing elements in the same order and so the newest element is always inserted at the end.

Upvotes: 5

Christophe
Christophe

Reputation: 73366

Ad hoc solution using the known impact on order

You could simply opt for a backward iteration, starting from the last element:

for( auto pi = charMap.end(); pi-- != charMap.begin(); pi=charMap.erase( pi ))
    charMap[ pi->first + 1 ] = charMap[ pi->first ];

Online demo

This will not loop forever here, because the new element that you insert will always be after the current one and will hence not be reprocessed again and again.

More general solution

For a more general transformation where you can't be sure about the impact on element ordering, I'd rather go for a std::transform():

std::map<int, char> tmp; 
std::transform(charMap.begin(), charMap.end(), std::inserter(tmp,tmp.begin()), 
                          [](auto e) { return std::make_pair(e.first+1, e.second); });
std::swap(tmp, charMap);    // the old map will be discarded when tmp goes out of scope

Online demo

Upvotes: 3

Sam Varshavchik
Sam Varshavchik

Reputation: 118292

You cannot use this kind of range iteration for two fundamental reasons:

The first reason is that a fundamental property of a map is that iterating over the map iterates in key order.

You are iterating over the map. So, if the first key in the map is key 0, you will copy the value to key 1. Then, you iterate to the next key in the map, which is the key 1 that you just created, and then copy it to key 2. Lather, rinse, repeat.

The are several ways to solve this, but none of that matters because of a second fundamental aspect of the map:

charMap[1]=charMap[0];

This copes charMap[0] to charMap[1]. It does nothing to charMap[0]. It is still there. Nothing happened to it. So, presuming that the lowest key in the map is 0, and you shifted the keys correctly, you will still have a value in the map with key 0. Ditto for the everything else in the map.

But let's say you solved the first problem in one of the several ways that it could be solved. Then, let's say your map has values for keys 0, 5, and 7.

After you copy key #0 to key #1, key #5 to key #6, and key #7 to key #8, take a paper and pencil, and figure out what you have now in your map.

Answer: it is not going to be keys 1, 6, and 8. It will be keys 0, 1, 5, 6, 7, and 8.

All you did was copy each value to the next key. This is because a computer does exactly what you tell it to do, no more, no less. A computer does not do what you want it to do.

The easiest way to do this is to create a new map, and copy the contents of the old map to the new map, with an updated key value. You can still use range iteration for that. Then, replace the old map with the new map.

Of course, this becomes impractical if the map is very large. In that case, it is still possible to do this without using a second map, but the algorithm is going to be somewhat complicated. The capsule summary is:

1) Iterate over the keys in reverse order. Can't use range iteration here.

2) After copying the key to the next value in the map, explicitly remove the value from its original key.

Upvotes: 0

Related Questions