c++ - 如何验证 vector 是否在某个索引处具有值

Question

在“ self 回避随机游走”的情况下，我有一个二维 vector ，其配置了阶跃坐标。我希望能够检查某个站点是否已被占用，但问题是轴可以为零，因此检查坐标的fabs()是否为true(或者它有一个值)，将不起作用。因此，我考虑过循环执行这些步骤并检查我的坐标是否等于所有轴上的另一个坐标，如果是，则后退并重试(所谓的深度优先方法)。

有没有更有效的方法来做到这一点？我见过有人使用包含所有可能坐标的 bool 数组，如下所示:

bool occupied[nMax][nMax];          // true if lattice site is occupied
for (int y = -rMax; y <= rMax; y++)
        for (int x = -rMax; x <= rMax; x++)
            occupied[index(y)][index(x)] = false;

但是，在我的程序中，维数是未知的，这样的方法也是如此:

typedef std::vector<std::vector<long int>> WalkVec;
WalkVec walk(1, std::vector<long int>(dof,0));
siteVisited = false; counter = 0;  
            while (counter < (walkVec.back().size()-1))
            {
                tdof = 1;
                while (tdof <= dimensions)
                {

                    if (walkHist.back().at(tdof-1) == walkHist.at(counter).at(tdof-1) || walkHist.back().at(tdof-1) == 0)
                    {
                        siteVisited = true;
                    }
                    else
                    {
                        siteVisited = false;
                        break;
                    }
                    tdof++;
                }

如果维数，则在自由度处工作。 (检查零检查位置是否为原点。三个零坐标，或同一步骤中的三个访问坐标是使其为真的唯一方法)有没有更有效的方法？

Answer 1

您可以分别使用 STL 的 set 或 unordered_set 在 O(log n) 或 O(1) 时间内完成此检查。 unordered_set 容器需要你为你的坐标编写一个自定义的哈希函数，而 set 容器只需要你提供一个比较函数。集合实现特别容易，对数时间应该足够快:

#include <iostream>
#include <set>
#include <vector>
#include <cassert>

class Position {
public:
    Position(const std::vector<long int> &c)
        : m_coords(c) { }

    size_t dim() const { return m_coords.size(); }
    bool operator <(const Position &b) const {
        assert(b.dim() == dim());
        for (size_t i = 0; i < dim(); ++i) {
            if (m_coords[i] < b.m_coords[i])
                return true;
            if (m_coords[i] > b.m_coords[i])
                return false;
        }
        return false;
    }

private:
    std::vector<long int> m_coords;
};

int main(int argc, const char *argv[])
{
    std::set<Position> visited;
    std::vector<long int> coords(3, 0);
    visited.insert(Position(coords));

    while (true) {
        std::cout << "x, y, z: ";
        std::cin >> coords[0] >> coords[1] >> coords[2];
        Position candidate(coords);
        if (visited.find(candidate) != visited.end())
            std::cout << "Aready visited!" << std::endl;
        else
            visited.insert(candidate);
    }
    return 0;
}

当然，正如 iavr 提到的，任何这些方法都需要 O(n) 存储。

编辑:这里的基本思想非常简单。目标是以一种允许您快速检查是否访问过特定位置的方式存储所有访问过的位置。您的解决方案必须扫描所有访问过的位置才能执行此检查，这使其成为 O(n)，其中 n 是访问过的位置数。要更快地执行此操作，您需要一种方法来排除大多数访问过的位置，这样您就根本不必与它们进行比较。

您可以通过考虑对排序数组进行二分查找来理解我的基于集合的解决方案。首先，你想出一种比较(排序)D 维位置的方法。这就是 Position 类的 < 运算符正在做的事情。正如 iavr 在评论中指出的那样，这基本上只是一个字典序比较。然后，当所有访问过的位置按此顺序排序后，您可以运行二分搜索来检查候选点是否已访问:您递归地检查候选点是否会在列表的上半部分或下半部分找到，消除一半从每个步骤的比较中得出的剩余列表。在每一步将搜索域减半为您提供对数复杂度 O(log n)。

STL 集容器只是一个很好的数据结构，它可以在您插入和删除元素时让您的元素保持有序，确保插入、删除和查询都很快。如果您好奇的话，我使用的 STL 实现使用红黑树来实现这个数据结构，但从您的角度来看这是无关紧要的；重要的是，一旦你给它一个比较元素的方法(< 运算符)，将元素插入集合(set::insert)和询问元素是否在集合中(set::find)是 O(记录 n)。我通过将它添加到访问集来检查来源——没有理由特殊对待它。

unordered_set 是一个哈希表，一种渐进式更高效的数据结构 (O(1))，但更难使用，因为您必须编写良好的哈希函数。此外，对于您的应用程序，从 O(n) 到 O(log n) 应该足够好了。