C++17 中仍然允许 XOR 链表吗？

Question

考虑到 C++17 中引入的语义变化（例如在具有正确地址和类型的指针自 C++17 以来是否仍然始终是有效指针中进行了讨论） ，XOR 链接列表以一种对我来说看起来很可疑的方式使用指针算术。）。它们现在会导致未定义的行为吗？如果是这样，可以通过洗涤来拯救它们吗？

编辑：

维基百科文章仅包含有关指针和整数之间转换的简短注释。我默认（现在明确声明）指针首先被转换为足够大小的整数类型以适合它们，然后对整数进行异或。因此，操作理论中列出的 XOR 属性保证只有从指针获得一次的整数才会被转换回它们。根据标准，从指针到整数的实际映射可以是任意注入。除此之外我不依赖任何假设。

标准是否允许使用它们并访问仍然存在的对象？C++17 之前？从 C++17 开始？

Answer 1

它是实现定义的，并且在 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;

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

然而，如果我们存储异或next指针，开始指向的新对象的生命周期next，然后对地址进行非异或并转换回指针类型，那么这将是UB 。