Traverse unordered_map while inserting new nodes

[kimtaehong]

I'm not english native, so my explanation can be some what weird.

The simulation function below reads the cells inside the map, breed the cell if it's active and insert inactive cells into the unordered_map named "simulation".

I tried to traverse the unordered_map while inserting new node, without making any copied unordered map for copying new map each time for breeding took too long.

The problems is that, some of the iterators are being repeated, while some aren't even visited at all.

If I run this simulator for map which looks like

1 1
0 2

At the 4th repitition, though there are 6 active cells, it repeatedly reads 3 cells twice and doesn't read 3 active but not bred cells.

How should I modify this code to correctly simulate this problem?
(the source code is at
https://github.com/kaestro/algorithms/blob/master/swexpert%20academy/5653_unordered.cpp
)

void simulate() {
    for (int i = 0; i < timeLimit; ++i) {
        for (myMap::iterator it = simulation.begin(); it != simulation.end();++it) {
            if (it->second.active == DEAD || it->second.lifetime == -1) continue;
            if (it->second.active == ACTIVE) {
                const ii& pos = it->first;
                const StemCell& sc = it->second;
                breed(pos, sc);
                it = simulation.find(pos);
            }
        }

        for (myMap::iterator it = simulation.begin(); it != simulation.end(); ++it) {
            it->second.increment();
        }
    }
}

void breed(const ii& pos, const StemCell& st) {
    for (int d = 0; d < direction.size(); ++d) {
        ii nextPos = { pos.first + direction[d].first, pos.second + direction[d].second };
        myMap::iterator it = simulation.find(nextPos);
        if (it == simulation.end()) {
            simulation[nextPos] = StemCell(-1, st.healthPoint);
        } else if (it->second.lifetime == -1){
            if (it->second.healthPoint < st.healthPoint) {
                it->second.healthPoint = st.healthPoint;
            }
        }
    }
}

[Duthomhas]

The problem is that you are mixing state over a stateful boundary.

That is, B depends on A. To calculate B you need to know A.
But you change A into something else before you have finished computing B.

See the problem?

There are only two solutions. Both require you to maintain atomicity with state.

(1) Make a duplicate state map, then either
  • update your reference to the active state map, OR
  • copy the new state map to overwrite the old state map.

(2) Add an additional state flag and modify state in two passes:
  • first pass modifies the additional flag using the active flag
  • second pass copies the additional flag modifications to the active flag
  There is a whole lot of leeway on how you implement this. In particular, you don’t have to
  actually use up additional memory for it if it matters.

Honestly, unless you are working in an environment with very tight memory requirements, prefer option 1: keep two state maps and target one of them as active.

Hope this helps.

[kimtaehong]

Thank you for the reply.
I think I've understood your first solution and seems it works but I hardly understand your second answer.
Does the second solution mean that I change state of A using additional active flag, and set the circulating iterator to the beginning of the map after I've changed the state of A?

like for instance

            if (it->second.active == ACTIVE) {
                const ii& pos = it->first;
                const StemCell& sc = it->second;
                breed(pos, sc);
                it = simulation.find(pos);
                it->second.traversed = true;
                it = simulation.begin();
            }

[Duthomhas]

I think you have the idea.

struct Data                 struct Data
{                           {
  type stuff;      -->        type stuff;
};                            type modified_stuff;
                            };

First pass, look at stuff to assign value to modified_stuff.
Second pass, stuff = modified_stuff.

All stuff is still being duplicated, just in a different way...