从向量有效地遍历值

Question

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

vector<pair <int,int>> cellsActive; 

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

我实现了以下目标：

1. 创建与2D网格一样大的数组myGrid，并将每个字符设置为.
2. 迭代cellsActive向量并获得每个活动单元格：activeCell
3. 更改网格，以使每个activeCell位置（pair <int int>）现在都由#表示； myGrid[activeCell.first][activeCell.second] = "#"
4. 现在myGrid正确保存所有单元格的值；循环遍历myGrid的任意部分并打印。

但是，我觉得我应该能够通过仅将要打印的任意部分打印为.来更有效地做到这一点，但相关的activeCell位置需要以[[ C0]。如果我找到了这样的方法，则不必构造整个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和cellsActive和arbitrary_x很大，这似乎在计算上效率低下。

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

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

  • 没有多余的内存。