How to go (in a random order) through all the elements of a 2D array with a specific state-CodePudding

I have a simple 2D array in C like this:

Cell field[57][57];
enum State {foo, bar, baz};

Where each Cell is defined as

typedef struct Cell_t{
    enum State state;
    int value;
    float temperature;
}Cell;

My goal is to go through the field and do something with all the cells which have their state currently set as foo. The goal is to go through these in a random order. After having gone through all of the foo cells, one time step is finished and the next can happen.

That means that for example, the field might contain 1000 cells whose state is baz, and 197 cells whose state is foo, the rest is bar. They are all at random places in the 2D array. I need to go through all the foo cells in random order, do something with them, and only them.

The thing is that the actions of one foo cell can turn a cell that was not foo before into a foo cell. This new cell, however, will not make its move in this step, only the foo cells that were foo before the first change of this step can make their move. What would be the correct way to do this?

What I tried:

I went through the field sequentially, looking for foo cells, added their coordinates to a vector of coordinate arrays {x,y}, then chose one randomly, accessed it (by knowing its coordinates) in the field, did the necessary action, then deleted the coordinates from the vector. Then I chose the next random coordinates, and the next, until the vector is empty. The next step can begin afterwards.

However, I can have thousands upon thousands of cells at any given time and constantly adding and removing items from the vector can be costly. What is the fastest way to do this?

CodePudding user response：

You can put all the coordinates of foo cells in an std::vector and std::shuffle it. That's what I would do:

#include <random>
#include <algorithm>

int main() {
  Cell field[57][57];

  std::vector<std::pair<int, int>> cellsToVisit;
  for (int i = 0; i < 57; i  ) {
    for (int j = 0; j < 57; j  ) {
      if (field[i][j].state == foo) {
        cellsToVisit.push_back({i, j});
      }
    }
  }
  std::default_random_engine rng;
  std::shuffle(cellsToVisit.begin(), cellsToVisit.end(), rng);
  for (const auto& ij: cellsToVisit) {
    std::cout << "Visit cell " << ij.first << ", " << ij.second << std::endl;
  }
  
  return 0;
}