如何用带符号坐标键正确初始化std::map实现四叉树节点映射？

你的问题核心是自定义vec2作为std::map或std::unordered_map键时，比较器或哈希函数没有正确区分正负坐标，导致(-1,-1)和(1,1)被判定为同一键。以下是针对两种容器的具体修复方案：

一、修复std::map的键比较逻辑 #

std::map基于有序存储，依赖operator<（或自定义比较器）区分键。如果你的比较逻辑只比较坐标绝对值或存在逻辑错误，就会出现正负坐标被视为相等的情况。

正确的vec2结构体实现（适用于std::map） #

#include <map>
#include <iostream>

struct vec2 {
    int x;
    int y;

    // 正确实现operator<，确保正负坐标能被区分
    bool operator<(const vec2& other) const {
        // 先比较x坐标，x不等时直接返回结果；x相等时比较y坐标
        if (x != other.x) {
            return x < other.x;
        }
        return y < other.y;
    }
};

int main() {
    std::map<vec2, std::string> node_map;
    node_map[{1, 1}] = "1000";
    node_map[{-1, -1}] = "0010";

    // 现在能正确输出0010
    std::cout << node_map[{-1, -1}] << std::endl;
    return 0;
}

关键说明 #

• 不要在比较逻辑中使用abs(x)或忽略符号的判断，必须直接比较原始带符号整数值。
• 如果需要自定义比较器而非重载operator<，可以在声明std::map时传入自定义比较结构体，逻辑和上述operator<一致即可。

二、修复std::unordered_map的哈希与相等判断 #

std::unordered_map依赖哈希函数生成唯一哈希值，同时需要operator==判断键是否相等。之前的错误大概率是哈希函数未考虑坐标符号，或者operator==逻辑错误。

正确的vec2结构体实现（适用于std::unordered_map） #

#include <unordered_map>
#include <iostream>
#include <functional> // 用于std::hash

struct vec2 {
    int x;
    int y;

    // 严格判断坐标符号与数值都完全相等
    bool operator==(const vec2& other) const {
        return x == other.x && y == other.y;
    }
};

// 自定义哈希函数，结合正负坐标生成唯一哈希值
namespace std {
    template<> struct hash<vec2> {
        size_t operator()(const vec2& v) const {
            // 组合x和y的哈希值，避免符号相同但数值不同的坐标产生冲突
            size_t hash_x = hash<int>()(v.x);
            size_t hash_y = hash<int>()(v.y);
            return hash_x ^ (hash_y << 1);
        }
    };
}

int main() {
    std::unordered_map<vec2, std::string> node_map;
    node_map[{1, 1}] = "1000";
    node_map[{-1, -1}] = "0010";

    // 现在能正确输出0010
    std::cout << node_map[{-1, -1}] << std::endl;
    return 0;
}

关键说明 #

• 如果觉得移位异或的哈希组合不够稳定，可以手动实现hash_combine逻辑来提升哈希唯一性：

  template <typename T>
  void hash_combine(size_t& seed, const T& val) {
      std::hash<T> hasher;
      seed ^= hasher(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
  }
  
  // 修改哈希函数为：
  size_t operator()(const vec2& v) const {
      size_t seed = 0;
      hash_combine(seed, v.x);
      hash_combine(seed, v.y);
      return seed;
  }
  

三、验证四叉树节点映射逻辑 #

单独写一个测试函数，直接传入(-1,-1)验证坐标到二进制串的映射结果，排除映射逻辑本身的错误，确保(-1,-1)确实对应0010。

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