c++ - 有效地遍历 vector 中的值

Question

我有一个 vector 对，它实际上只是存储2D网格中的单元是否处于 Activity 状态。

vector<pair <int,int>> cellsActive; 

现在，我尝试打印整个2D网格的任意部分，其中所有非 Activity 单元格都用 .表示，而 Activity 单元格则用 #表示。

我实现了如下:

创建一个与2D网格一样大的myGrid数组，并将每个字符设置为.

遍历cellsActive vector 并获取每个 Activity 单元格:activeCell

更改网格，以使每个activeCell位置(pair <int int>)现在都由#表示； myGrid[activeCell.first][activeCell.second] = "#"

现在，myGrid正确保存了所有单元格的值。遍历myGrid的任意部分并打印出来。

但是，我觉得我应该能够通过仅将要打印的任意部分打印为 .来更有效地做到这一点，但相关的 activeCell位置需要以 #的形式打印。如果我找到了类似的方法，则不必构造整个2D网格，然后再次遍历它即可打印。但是，另一方面，我不知道如何有效地浏览 cellsActive列表并找到我需要用 #表示的相关单元格。

即我可以这样做:

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 << ".";
        }
    }
}

但是然后我必须每次都搜索整个 cellsActive vector ，如果 cellsActive和 arbitrary_x和 arbitrary_y很大，这似乎在计算上效率低下。

我的问题是，在C++中打印这些 .和 #的计算最有效的方法是什么？

Answer 1

我看到2种有趣的方式:

创建缓冲区结果，并填充它:

std::vector<std::vector<char>> chars(arbitrary_x, std::vector<char>(arbitrary_y, '.'));
// or even better std::vector<char> chars(arbitrary_x * arbitrary_y, '.');

for (auto [x, y] : cellsActive) {
    if (x < arbitrary_x && y < arbitrary_y) { chars[x][y] = '#'; }
}

// display chars.

复杂度:max(O(N), O(arbitrary_x * arbitrary_y))

额外的内存:arbitrary_x * arbitrary_y

或排序cellsActive并执行类似合并的代码。

auto comp = [](const auto& lhs, const auto& rhs){
    return std::tie(lhs.second, lhs.first) < std::tie(rhs.second, rhs.first);
};
std::sort(cellsActive.begin(), cellsActive.end(), comp);
auto it = cellsActive.begin();

for (int y = 0; y < arbitrary_y; y++) {
    for (int x = 0; x < arbitrary_x; x++) {
        const std::pair p{x, y};

        while (it != cellsActive.end() && comp(*it, p)) {
            ++it;
        }
        if (it != cellsActive.end() && *it == p) {
            std::cout << '#';
        } else {
            std::cout << '.';
        }
    }
}
// You can even break the loops when `it` reaches the end and print remaining '.'.

复杂度:max(O(N log N), O(arbitrary_x * arbitrary_y))

没有额外的内存。