C++17 中是否仍允许 XOR 链表？

据我所知，来来回reinterpret_cast应该没问题。std::uintptr_t

它是实现定义的，在 C++17 中仍然有效，至少对 GCC 有效。不能直接在两个指针之间执行异或运算;你必须通过.此转换（和返回）的效果由实现定义。reinterpret_cast<std::intptr_t>

实现定义意味着编译器必须记录发生的情况。GCC 提供的是：

从指针到整数的强制转换将丢弃 [...]，否则位保持不变。

从整数到指针的强制转换将丢弃 [...]，否则位保持不变。

当从指针转换为整数并再次转换时，生成的指针必须引用与原始指针相同的对象，否则行为未定义。

查看 https://gcc.gnu.org/onlinedocs/gcc/Arrays-and-pointers-implementation.html

从这个描述中，我们可以得出结论：

1. 用户确保地址上的对象在将指针存储在 XOR 列表中和检索指针之间保持不变
   • 如果指向的对象在此过程中发生更改，则将整数强制转换回指针是未定义的行为
2. 这里没有解释如何来回转换结束指针、空指针和无效指针，但根据 C++ 标准“保留值”

对 XOR 列表的影响

一般来说，这应该使 XOR 列表是可实现的，只要我们重现我们存储的相同指针，并且不要在有 XOR 指针指向节点时“地毯式拉动”节点。

std::intptr_t ptr;

// STORE:
// - bit-cast both operands and XOR them
// - store result in ptr
ptr = reinterpret_cast<std::intptr_t>(prev) ^ reinterpret_cast<std::intptr_t>(next);

// LOAD:
// - XOR stored ptr and bit-cast to node*
node* next = reinterpret_cast<node*>(ptr ^ reinterpret_cast<std::intptr_t>(prev));
// valid dereference, because at the address 'next', we still store the same object
*next;

如文档中所述，“必须引用与原始指针相同的对象”，因此我们可以假设现在是指向对象的指针，如果此类指针最初存储在 .nextnextptr

但是，如果我们存储 XOR 指针，开始指向的新对象的生存期，然后取消 XOR 处理地址并转换回指针类型，则该指针将是 UB。nextnext

XOR 链表在 C++17 及更高版本中仍然有效，前提是该类型存在。uintptr_t

虽然表示特定地址的指针不一定是指向驻留在该地址的对象的指针，但有 [expr.reinterpret.cast]/5：

[...]转换为足够大小的整数（如果实现中存在任何此类整数）并返回到相同指针类型的指针将具有其原始值;指针和整数之间的映射是实现定义的。[ 注意：除 6.7.4.3 中所述的情况外，此类转换的结果将不是安全派生的指针 价值。— 结束语 ]

这告诉我们，虽然通常可能不会给你一个指向对象的指针，但在一种特殊情况下，操作数是一个整数值，以前是从指针操作数中获取的。往返产生的指针值是原始指针值，这意味着如果原始指针值指向某个对象，则结果也指向该对象（当然，假设该对象仍然存在）。reinterpret_castreinterpret_cast

但是，注释告诉我们，在 C++17 中，转换的结果可能不是“安全派生的指针值”。这意味着，一旦您执行指向整数转换的指针并且不保留该整数的副本，而是仅存储其值 XOR 其他整数，则允许实现对指针进行垃圾回收，因为（在某种技术意义上，我不会在这里讨论）指针不再“可访问”。当您稍后通过另一个 XOR 操作重构原始整数值，然后尝试将其返回到原始指针时，该指针值不是“安全派生的”，因此在某些理论实现下被认为是无效的（因为该实现可能已经对其进行了垃圾回收）。但是，如果你的实现有“宽松的指针安全”，那么这并不重要;指针仍然有效。设计意图是垃圾回收实现将自己定义为具有“严格的指针安全性”。reinterpret_cast

在实践中，实际上没有任何实现具有标准中指定的“严格的指针安全性”，即使一些垃圾回收的 C++ 实现显然确实存在。因此，严格的指针安全概念将在 C++23 中废除。您可以放心，假设存在 XOR 链表，则 XOR 链表是有效的。uintptr_t