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, Jun 07 '17 at 20:06
One does not modify the container they are iterating. (Just a guideline, of course there are exceptions) — NathanOliver, Jun 07 '17 at 20:06
The `remove i from dict;` step will invalidate the iterator your range-for is holding under the hood. — T.C., Jun 07 '17 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, Jun 07 '17 at 20:18
What about leaving the object in the map, but marking it with a "disabled" flag? — Solomon Slow, Jun 07 '17 at 21:35

PaSTE · Accepted Answer · 2017-06-09T02:34:45.830

2

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).

edited Jun 09 '17 at 02:34

answered Jun 08 '17 at 13:51

PaSTE

4,050
18
26

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? – ZigZagZebra Jun 08 '17 at 22:04
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 dict)` (no ampersand), then the map would be copied on each recursive call. This would incur a significant performance penalty, but it would work. – PaSTE Jun 09 '17 at 02:59

score 0 · Answer 2 · answered Jun 07 '17 at 22:37

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.

Erase an element from a map then put it back

2 Answers2