Erase an element from a map then put it back

Question

Suppose I have a backtracking algorithm where I need to remove an element from a map, do something, then put it back. I am not sure if there is a good way to do it:

func(std::<K, V> map &dict) { for (auto i : dict) { remove i from dict; func(dict); put i back to dict; } }

I know there are ways to delete an element from map in here but I am not sure if there are ways to achieve what I described above. I am aware that I can create a new dict in for loop and pass it in func but I am wondering if it can be done using the same dict.

An example in actual c++ would be helpful to illustrate your question. I'm pretty sure every line that isn't a single brace contains a syntax or logic error. — François Andrieux
– François Andrieux, Commented Jun 7, 2017 at 20:06
One does not modify the container they are iterating. (Just a guideline, of course there are exceptions) — NathanOliver
– NathanOliver, Commented Jun 7, 2017 at 20:06
The remove i from dict; step will invalidate the iterator your range-for is holding under the hood. — T.C.
– T.C., Commented Jun 7, 2017 at 20:14
There are many ways to do this ... what's appropriate depends on the map size, and mostly on how func is using your map... — Daniel Jour
– Daniel Jour, Commented Jun 7, 2017 at 20:18

PaSTE · Accepted Answer · 2017-06-09 02:34:45Z

What you ask is definitely possible. Here is one way to do it while trying to keep things simple and efficient:

void func(std::map<K, V> &dict) { for (auto i = dict.cbegin(); i != dict.cend(); ) { auto old = *i; i = dict.erase(i); // i now points to the next element (or dict.end()) some_other_func(dict); dict.insert(i, old); // i is used a hint where to re-insert the old value } }

By calling std::map::erase with an iterator argument and std::map::insert with a hint, the complexity of each iteration through this loop is amortized constant. Note that I assumed your calling of func in line 5 was actually supposed to be some_other_func, because calling func recursively would invalidate the iterator you carefully set in line 4.

However, this is not the most efficient way to do this sort of processing (@rakurai has a suggestion that should be considered).

When you call some_other_func(dict) do you mean pass a copy of dict to the some_other_func? I hope to call the same function (func) recursively. I am not sure why it invalidates the iterator since I am trying to keep the dict the same as the state it is passed in in each iteration of for loop. Could you please explain more about this? What if I want to call func in the for loop recursively? Is passing by copy the only way?
After i = dict.erase(i);, the iterator points to the next element in the map, which is why no increment is needed in the for statement. If func were called recursively (and the signature still used a reference), when the inner func erases what the outer func calls i, that would invalidate the outer i, so the next step through the for loop outside the recursive call would probably core dump. If the signature were func(std::map<K,V> dict) (no ampersand), then the map would be copied on each recursive call. This would incur a significant performance penalty, but it would work.

Rakurai · Accepted Answer · 2017-06-07 22:37:28Z

This question has an answer here.

However, your problem may be that you would like the function to ignore the key K while processing dict. How about a second parameter "K ignore" and make the function skip that pair? You could give it a default value in the declaration if that breaks other code, or overload the function.

Collectives™ on Stack Overflow

Erase an element from a map then put it back

2 Answers 2

2 Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Linked

Related