Question

XOR链表使用指针算术的方式在我看来是可疑的，因为C++17中引入了语义的变化（例如在自C++17以来，具有正确地址和类型的指针是否始终是有效指针？）。它们现在会导致未定义的行为吗？如果是，可以用清洗？

编辑：

维基百科的这篇文章只包含了一个关于指针和整数之间转换的简短说明。我默认（现在明确表示）指针首先转换为大小足以容纳它们的整数类型，然后对整数进行XOR运算。运算理论因此保证只有从指针中获得一次的整数才会转换回它们。

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

Answer 1

据我所知，retinterpret_cast往返std:：uintptr_t应该可以。

Answer 2

它的实现是定义的，并且在C++17中仍然有效，至少对GCC是这样。不能直接在两个指针之间执行异或运算；您必须通过reinterpret_cast<；标准：：intptr_t>。这种转换（和返回）的效果是实现定义。


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

从指针到整数的强制转换将丢弃[…]，，否则位不变
从整数到指针的强制转换将丢弃[…]，，否则位不变
当从指针转换为integer并再次转换时，生成的指针必须引用与原始指针相同的对象，否则行为是未定义的。

请参阅https://gcc.gnu.org/onlinedocs/gcc/Arrays-and-pointers-implementation.html
这对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*
auto next = reinterpret_cast<node*>(ptr ^ reinterpret_cast<std::intptr_t>(prev));

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

友情链接