How to change some keys in a std::map using extract and insert

Question

I've recently read this question about node_type, and I learned that if I need to modify the key of a specific node in a map, I could extract the node, modify the key and insert the node back in the map (like in this example).

Now, let's say I need to change the key of multiple nodes of this map, and to know which nodes I need to modify, I have to iterate over the values. I think I shouldn't insert the nodes back in the map while iterating (but maybe I'm wrong, see the end of the question), so I was thinking I could iterate over the map in a first time, extract the nodes I need to modify, store those in a vector, and insert the nodes back in a second time, when I'm finished iterating the map and modifying the nodes.

I suspect I could achieve that by storing the keys in a vector, not the nodes, but since the whole point is to change the keys, I thought it could be handy to use the nodes which seem to be made for that purpose.

So, basically, here's what I have so far:

  std::vector</*don't know what to put here since node_type is undefined*/> tmp;
  for (auto& it : myMap) {
    if(it.second->needsToBeModified()){
      tmp.push_back(myMap.extract(it.first));
    }
  }

I can't figure out what type that tmp vector would be.

As I said before, I may be wrong about not wanting to insert back the nodes while iterating, reading this answer stating that inserting or deleting in a map while iterating doesn't invalidate iterators (apart from the deleted entry). But this feels weird, what would happen if I insert a node in the map while iterating over it, would the inserted node come up in the iterating loop? Could that lead in an infinite loop?

Answer 1

The vector type is simple to address, since std:map specializations expose a type alias.

std::vector<std::map<K,V>::node_type> tmp;

The more involved point is the iteration. You cannot use a simple range-based for. That is because node extraction invalidates iterators to the extracted element. And that includes the iterator used behind the scenes for iteration. Instead, a more appropriate loop would be

for (auto it = myMap.begin() ; it != myMap.end();) {
    if(it->second->needsToBeModified()){
      auto out = it++;
      tmp.push_back(myMap.extract(out));
    }
    else
      ++it;
}

Insertion while iterating is possible (since it doesn't invalidate iterators). But if the iteration order is important (even if only for debuggability), I think an auxiliary vector like you use is appropriate.

Answer 2

StoryTeller's answer is correct, however it would be nice if you wouldn't have to know how to spell out the whole type. There are several ways to simplify the declaration of tmp. The first is to avoid repeating the type of myMap, by using decltype():

std::vector<decltype(myMap)::node_type> tmp;

However, this still required you to know that the type of myMap contains another type named node_type. If you didn't know that, and still wanted to declare a vector that holds the result of myMap.extract(), then you can write:

std::vector<decltype(myMap.extract(myMap.begin()->first))> tmp;

As you can see, that's unfortunately quite a bit longer to type in, but you didn't have to use any knowledge about myMap, other than how you are actually using it inside the for-loop.