C++中如何跟踪遍历过程中的已访问点？

嘿，作为曾经也踩过容器选择坑的C++初学者，我太懂你这种困惑了！用std::map来跟踪访问点确实有点“杀鸡用牛刀”，下面给你几个更贴合需求的高效方案，一步步来：

1. 优先选std::unordered_map（哈希表，平均O(1)效率） #

std::unordered_map是哈希表实现，插入和查找的平均时间复杂度是O(1)，比std::map的O(logn)快不少，而且不需要写比较器，只需要给你的点类型提供一个哈希函数（如果是自定义类型的话）。

举个最常见的二维整数坐标例子：

#include <unordered_map>
#include <utility>

// 给std::pair<int,int>写个简单的哈希函数
struct PairHash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2>& p) const {
        // 组合两个整数的哈希值，避免简单异或的冲突
        auto hash1 = std::hash<T1>{}(p.first);
        auto hash2 = std::hash<T2>{}(p.second);
        return hash1 ^ (hash2 << 1);
    }
};

// 初始化访问标记容器
std::unordered_map<std::pair<int, int>, bool, PairHash> visited;

// 标记点(x,y)已访问
visited[{x, y}] = true;

// 检查是否访问过
if (visited.find({x, y}) != visited.end()) {
    // 这里写已访问后的逻辑
}

如果是你自己定义的Point结构体，只需要额外重载==运算符（哈希表需要判断键是否相等）：

struct Point {
    int x;
    int y;
    // 必须重载==，用于哈希表判断键是否重复
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 给Point写哈希函数
struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 1);
    }
};

// 使用方式和上面一样
std::unordered_map<Point, bool, PointHash> visited;

2. 不想写哈希函数？用std::set更轻量 #

如果你觉得写哈希函数麻烦，std::set是个不错的替代——它只需要你的点类型支持比较（比如重载<运算符），而且它专门用来存储唯一元素，刚好符合“跟踪是否访问过”的需求（因为同一个点只会存一次）。

对于std::pair<int,int>，标准库已经默认支持<比较了，直接用就行：

#include <set>
#include <utility>

std::set<std::pair<int, int>> visited;

// 标记访问
visited.insert({x, y});

// 检查是否访问过（count返回1就是存在，0就是不存在）
if (visited.count({x, y})) {
    // 已访问逻辑
}

如果是自定义结构体，只需要重载<运算符：

struct Point {
    int x;
    int y;
    // 重载<，先比x，x相同再比y
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

std::set<Point> visited;

不过要注意，std::set底层是红黑树，插入查找是O(logn)，比std::unordered_map慢一点，但比std::map更贴合你的场景——毕竟你只需要存点，不需要键值对，std::map会额外存储一个值，纯属浪费。

3. 坐标范围固定？直接用数组/二维数组（效率天花板） #

如果你的题是网格遍历、迷宫搜索这种场景，点的坐标范围是固定且不大的（比如x从0到1000，y从0到1000），那直接用二维布尔数组绝对是最优解！没有任何容器的额外开销，访问速度是O(1)，代码还超级简单。

示例代码：

// 假设坐标范围是0<=x<1000，0<=y<1000，初始化全为false
bool visited[1000][1000] = {false};

// 标记点已访问
visited[x][y] = true;

// 检查是否访问过
if (visited[x][y]) {
    // 已访问逻辑
}

如果坐标范围需要动态设置，用std::vector也很方便：

int max_x = 1000;
int max_y = 1000;
// 初始化一个max_x行max_y列的二维vector，默认值都是false
std::vector<std::vector<bool>> visited(max_x, std::vector<bool>(max_y, false));

为什么说std::map是大材小用？ #

std::map底层是红黑树，核心优势是有序存储和范围查找，但你这个场景只是要判断“某个点是否存在”，完全不需要有序的特性。而且std::map是键值对容器，你其实只需要存键（点），不需要对应的值，用它会浪费空间和性能——上面的几种方案都更贴合你的需求，代码也更简单。

内容的提问来源于stack exchange，提问作者Blubber