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

在“自我规避的随机游走”情况下，我有一个二维 vector ，具有步进坐标的配置。我希望能够检查某个站点是否已被占用，但是问题是轴可以为零，因此检查坐标的fabs()是否为true(或它具有值)将无法工作。因此，我考虑过遍历所有步骤，并检查我的坐标是否等于所有轴上的另一个坐标，如果匹配，则后退并重试(所谓的“深度优先”方法)。

有更有效的方法吗？我见过有人使用 bool(boolean) 数组和所有可能的坐标，像这样:

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++;
                }

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

最佳答案

您可以分别使用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类的
STL集容器只是一个很好的数据结构，可在您插入和删除元素时使元素保持排序的顺序，从而确保插入，删除和查询都很快。如果您感到好奇，我使用的STL实现使用一棵红黑树来实现此数据结构，但是从您的 Angular 来看，这是无关紧要的。重要的是，一旦您提供了一种比较元素的方法(
unordered_set是一个哈希表，它是一种渐近有效的数据结构(O(1))，但更难使用，因为您必须编写一个良好的哈希函数。同样，对于您的应用程序，从O(n)到O(log n)应该足够好了。