c++ - 3D hasing : should I use unions as keys and how? 的 unordered_map 的最佳使用

Question

我想使用 C++11 std::unordered_map用于 3D(2D，4D)中规则矩形网格上的散列点。

最初我是这样手动打包和解包索引的:

inline int_fast64_t xyz2i( int_fast16_t ix, int_fast16_t iy, int_fast16_t iz ){
     return ix | ( iy << 16 ) | ( iz << 32 );
}

inline void i2xyz( int_fast64_t i, int_fast16_t& ix, int_fast16_t& iy, int_fast16_t& iz ){
    iz=( i & 0xFF0000 ) >> 32;
    iy=( i & 0x00FF00 ) >> 16;
    ix=( i & 0x0000FF );
}

然后我意识到使用 unions可能会更好:

class NodeIndex4D{
    public:
    union{
        struct{ int_fast16_t x,y,z,w; };
        int_fast16_t array[4];
        int_fast64_t i;
    };
};

但是，我仍然觉得我没有以最好的方式做到这一点。 C++ 语言特性也许可以更好地用于此目的。

例如不太好的是我的insertNode功能:

std::unordered_map<int_fast64_t,Node> nodes;

Node& insertNode( int_fast16_t ix, int_fast16_t iy, int_fast16_t iz ){
    NodeIndex4D inod; 
    inod.x=ix; inod.y=iy; inod.z=iz; inod.w=0;  // NOT SO NICE
    int sz0 = nodes.size();
    Node& node = nodes[inod.i]; // get valid reference ( if new allocate, if old take it )
    if( nodes.size() > sz0 ){ // new element
        node.id = sz0;
        index2pos( {ix,iy,iz}, node.pos ); // not relevant here 
        node.pos.add_mul( scaling, -0.5 ); // not relevant here
    }
    return node;
}

可能无法执行类似 std::unordered_map<NodeIndex4D,Node> 的操作这将在 NodeIndex4D.i 上使用标准哈希函数？

我也在考虑将我的插入函数定义为 Node& insertNode( NodeIndex4D inod )并将其命名为 Node& insertNode( {ix,iy,iz,0} )

Answer 1

部分可移植 的方法是将一个 int64_t 别名为一个包含 4 个 int16_t 的数组。即使标准没有明确允许，它也应该适用于同时支持 int16_t 和 int64_t 的任何通用架构(据我所知)。

唯一棘手的部分是字节顺序，应该在程序开始时在静态元素中测试它，以确定 x、y、z、w 的等级是 0、1、2、3 还是 3、2、1，分别为 0。以下代码应该可以解决问题:

class Node4D {
    uint64_t packed;
    uint16_t (& unpacked)[4];

    static bool isBigEndian() {
        static bool inited = false;
        static bool bigEndian = false;
        if (! inited) {
            Node4D n;
            inited = true;
            n.packed = 1;
            bigEndian = (n.unpacked[0] == 0);
        }
        return bigEndian;
    }

public:
    Node4D(): unpacked(reinterpret_cast<uint16_t (&)[4]>(packed)) {
        packed = 0;
    }
    Node4D(uint64_t p): unpacked(reinterpret_cast<uint16_t (&)[4]>(packed)) {
        packed = p;
    }
    Node4D(uint16_t x, uint16_t y, uint16_t z, uint16_t w):
    unpacked(reinterpret_cast<uint16_t (&)[4]>(packed)) {
        set(x, y, z, w);
    }
    uint64_t get() {
        return packed;
    }
    void get(uint16_t& x,uint16_t& y,uint16_t& z,uint16_t& w) {
        if (isBigEndian()) {
            w = unpacked[0];
            z = unpacked[1];
            y = unpacked[2];
            x = unpacked[3];
        }
        else {
            x = unpacked[0];
            y = unpacked[1];
            z = unpacked[2];
            w = unpacked[3];
        }
    }

    void set(uint16_t x, uint16_t y, uint16_t z, uint16_t w) {
        if (isBigEndian()) {
            unpacked[0] = w;
            unpacked[1] = z;
            unpacked[2] = y;
            unpacked[3] = x;
        }
        else {
            unpacked[0] = x;
            unpacked[1] = y;
            unpacked[2] = z;
            unpacked[3] = w;
        }
    }
};

在内部，该结构仅包含一个 8 字节长的元素，因此它可以安全地用作键。