XOR 链表是普通双向链表的修改版本，其中每个节点仅存储一个“指针”而不是两个。该“指针”由下一个和前一个指针的 XOR 组成。要遍历列表，需要两个指针——一个指向当前节点，一个指向下一个或前一个节点。为了向前遍历，前一个节点的地址与存储在当前节点中的“指针”进行异或运算，从而显示出真正的“下一个”指针。
C++ 标准会导致对指针和整数的一堆操作导致未定义的行为——例如，你不能保证在数字中设置特定位不会导致硬件触发中断，因此在某些情况下位的结果twiddling 可以是未定义的。
我的问题如下：是否存在不会导致未定义行为的 XOR 链表的 C++ 实现？
我的问题如下：是否存在不会导致未定义行为的 XOR 链表的 C++ 实现？
如果“是否有实现”是指“它已经被编写过”，那么我不知道。如果您的意思是“是否可以写一个”，那么可以，但可能有一些关于可移植性的警告。
uintptr_t如果在开始之前将两个指针都转换为，并将该类型存储在节点中而不是指针中，则可以对您的心脏内容进行位旋转。无符号类型的按位运算永远不会导致未定义的行为。
但是，uintptr_t它是一个可选类型，因此它不是完全可移植的。不要求 C++ 实现实际上具有能够表示地址的整数类型。如果实现没有uintptr_t，则允许使用诊断编译代码，在这种情况下，其行为超出标准范围。不确定您是否认为“无UB”侵权。我的意思是，严肃地说，一个允许使用未定义类型的代码的编译器？;-)
为了避免这种情况，uintptr_t我认为您可以sizeof(node*)改为对一组无符号字符进行操作。指针是 POD 类型，因此只要对象表示在用作指针之前恢复到其原始状态，就可以被复制、旋转和切割。
另请注意，如果您的 C++ 实现具有垃圾收集器，则 convert-to-integer / xor / xor-back-again / convert-to-pointer 不必停止收集对象（因为它会导致“不安全地派生指针”）。因此，为了可移植性，您还必须确保生成的指针有效。有两种方法可以做到这一点：
declare_reachable他们。get_pointer_safety()同时记住允许宽松的实现错误地声称它是严格的）。您可能会认为还有第三种方式（尽管这种方式违背了 XOR 链表的目的，除非您碰巧拥有它）：
这不能保证有效。不安全派生的指针是无效的，即使它恰好等于安全派生的指针 (3.7.4.3/4)。我也很惊讶。