I have a vector of pairs, which really just store whether cells in a 2D grid are active.
vector<pair <int,int>> cellsActive;
Now I'm trying to print an arbitrary part of the whole 2D grid, in which all non-active cells are represented with a .
and the active cells are represented by a #
.
I implemented this is as following:
- Create an array
myGrid
as big as the 2D grid and set every character to.
- Iterate through the
cellsActive
vector and get each active cell:activeCell
- Change the grid so that every
activeCell
location (pair <int int>
) is now represented by a#
;myGrid[activeCell.first][activeCell.second] = "#"
- Now that
myGrid
correctly holds the values of all cells; loop through the arbitrary part of themyGrid
and print it.
However, I feel like I should be able to do this more efficiently by just printing the arbitrary part that I want to print as .
except for the relevant activeCell
locations that needs to be printed in the form of a #
. If I find a way to do it like that, I do not have to construct the whole 2D grid and then loop through it again to print it. But on the other hand, I do not know how to efficiently go through the cellsActive
list and find the relevant cells that I need to represent by a #
.
I.e. I could do this:
for (int y=0; y<arbitrary_y;y++) {
for (int x=0; x<arbitrary_x;x++) {
pair <int int> j = make_pair(y, x);
vector<intpair>::iterator it = find(cellsActive.begin(), cellsActive.end(), j);
if (it != cellsActive.end()) {
cout << "#";
}
else {
cout << ".";
}
}
}
but then I have to search through the whole cellsActive
vector every time, which seems to be computationally inefficient if the cellsActive
and arbitrary_x
and arbitrary_y
are large.
My question is, what is the computationally the most efficient way to print these .
and #
in C++?
cellsActive
and testif (it->first < arbitrary_y && it->second < arbitrary_x)
to get the#
s?cellsActive
are presorted in the y then x axis. You could do a O(n) iteration through the vector to determine if the current cell is on by having a pointer/index that only increments if the cell it points to is the current cell.CellsActive
?