迷宫搜索算法开发：Python键为tuple值为tuple列表的dictionary的C++替代实现

我明白你在C里复刻Python中用tuple作为键的字典结构时遇到的困扰——Python的dict对tuple键的支持确实很灵活，但C需要我们明确类型的规则。下面给你几种实用的实现方案，适配不同的场景：

方案1：使用std::map搭配std::pair #

std::map默认支持std::pair<int, int>作为键，因为标准库已经为pair重载了<运算符，满足红黑树的排序需求。这是最直接的方案，不需要额外的自定义代码：

#include <map>
#include <vector>
#include <utility>
#include <iostream>

int main() {
    // 定义图结构：键是坐标(x,y)，值是相邻坐标的列表
    std::map<std::pair<int, int>, std::vector<std::pair<int, int>>> maze_graph;

    // 向图中添加节点和相邻关系
    maze_graph[{0, 0}] = {{0, 1}, {1, 0}};
    maze_graph[{0, 1}] = {{0, 0}, {0, 2}};

    // 访问某个节点的相邻节点
    auto it = maze_graph.find({0, 0});
    if (it != maze_graph.end()) {
        std::cout << "Neighbors of (0,0):\n";
        for (const auto& neighbor : it->second) {
            std::cout << "(" << neighbor.first << ", " << neighbor.second << ")\n";
        }
    }

    return 0;
}

这个方案的优点是开箱即用，无需额外配置；缺点是std::map的插入和查找是O(log n)时间复杂度，适合中小规模的迷宫。

方案2：使用std::unordered_map搭配自定义哈希函数 #

如果你需要更快的平均O(1)查找/插入效率，可以用std::unordered_map，但标准库没有为std::pair提供默认的哈希函数，需要我们自己实现：

#include <unordered_map>
#include <vector>
#include <utility>
#include <iostream>
#include <functional>

// 为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);
    }
};

int main() {
    // 定义哈希表类型，指定自定义哈希函数
    std::unordered_map<std::pair<int, int>, std::vector<std::pair<int, int>>, PairHash> maze_graph;

    // 插入节点和相邻关系
    maze_graph[{1, 1}] = {{1, 0}, {0, 1}, {1, 2}, {2, 1}};

    // 访问节点
    if (maze_graph.contains({1, 1})) {
        std::cout << "Neighbors of (1,1):\n";
        for (const auto& neighbor : maze_graph[{1, 1}]) {
            std::cout << "(" << neighbor.first << ", " << neighbor.second << ")\n";
        }
    }

    return 0;
}

注意：哈希函数的实现可以根据需求优化，比如使用更复杂的组合方式（如hash1 * 31 + hash2）来减少冲突概率。

方案3：自定义坐标结构体（可读性更强） #

如果觉得std::pair不够直观，可以自定义一个Coordinate结构体，重载必要的运算符或提供哈希函数：

#include <map>
#include <unordered_map>
#include <vector>
#include <iostream>
#include <functional>

struct Coordinate {
    int x;
    int y;

    // 重载==运算符，用于unordered_map的查找
    bool operator==(const Coordinate& other) const {
        return x == other.x && y == other.y;
    }

    // 重载<运算符，用于std::map的排序
    bool operator<(const Coordinate& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

// 为Coordinate自定义哈希函数
struct CoordinateHash {
    std::size_t operator()(const Coordinate& c) const {
        return std::hash<int>{}(c.x) * 31 + std::hash<int>{}(c.y);
    }
};

int main() {
    // 使用std::map的版本
    std::map<Coordinate, std::vector<Coordinate>> maze_map;
    maze_map[{2, 2}] = {{2, 1}, {1, 2}};

    // 使用std::unordered_map的版本
    std::unordered_map<Coordinate, std::vector<Coordinate>, CoordinateHash> maze_umap;
    maze_umap[{2, 2}] = {{2, 1}, {1, 2}, {2, 3}, {3, 2}};

    return 0;
}

这种方式代码可读性更好，尤其是在复杂的迷宫算法中，Coordinate比pair更清晰。

方案4：二维数组（规则迷宫专属） #

如果你的迷宫是规则的矩形（比如已知最大的x和y范围），直接用二维数组存储相邻节点列表会更高效，不需要任何键值对映射：

#include <vector>
#include <utility>
#include <iostream>

int main() {
    // 假设迷宫是5x5的，初始化二维数组
    const int max_x = 4;
    const int max_y = 4;
    std::vector<std::vector<std::vector<std::pair<int, int>>>> maze(
        max_x + 1,
        std::vector<std::vector<std::pair<int, int>>>(max_y + 1)
    );

    // 设置(0,0)的相邻节点
    maze[0][0] = {{0, 1}, {1, 0}};

    // 访问(0,0)的相邻节点
    std::cout << "Neighbors of (0,0):\n";
    for (const auto& neighbor : maze[0][0]) {
        std::cout << "(" << neighbor.first << ", " << neighbor.second << ")\n";
    }

    return 0;
}

这个方案的优点是访问速度最快（O(1)），代码最简单，但只适用于坐标范围固定的规则迷宫。

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