问题描述
是正常版本的修改版本双向链表，其中每个节点仅存储一个指针而不是两个。该指针由下一个和前一个指针的XOR组成。为了遍历列表，需要两个指针 - 一个指向当前节点，一个指向下一个或上一个节点。要向前移动，前一个节点的地址与存储在当前节点中的指针进行异或，显示真正的下一个指针。
对指针和整数的操作将导致未定义的行为 - 例如，您不能保证设置一个数字中的特定位不会导致硬件触发中断，因此在某些情况下，bit twiddling的结果可能未定义。 / p>
我的问题是：是否有一个XOR链表的C ++实现不会导致未定义的行为？
如果是有一个实现的意思是已经写了，那么我不知道。如果你的意思是是可能写一个，那么是的，但它可能有一些注意事项的可移植性。
如果你在开始之前将两个指针转换为 uintptr_t ，并将该类型存储在节点中，而不是指针。对无符号类型的位操作从未导致未定义的行为。
但是， uintptr_t 是一个可选类型，因此不是完全便携。没有要求C ++实现实际上具有能够表示地址的整数类型。如果实现没有 uintptr_t ，则允许代码使用诊断程序进行编译，在这种情况下，其行为超出了标准的范围。不确定你是否认为侵犯没有UB或不。我的意思是，认真，一个编译器，允许使用未定义类型的代码？ ; - ）
为了避免 uintptr_t twiddling在数组 sizeof（node *） unsigned chars。指针是POD类型，因此只要对象表示在用作指针之前恢复到其原始状态，就可以复制，纺纱和残缺。
你的C ++实现有一个垃圾收集器，然后convert-to-integer / xor / xor-back-again / convert-to-pointer不必停止收集的对象（因为它导致一个不安全的派生指针）。因此，为了便于移植，您还必须 确保生成的指针有效。有两种方法：
- 在他们上调用
declare_reachable。 - 使用具有松弛指针安全性的实现（实现定义是否是这种情况，您可以使用
get_pointer_safety / code>请记住，放宽的实施可以错误地声称它是严格的）。
有一个第三种方法（虽然一个失败的XOR链表的目的，除非你碰巧有它反正）：
- 保持单独所有指针值的容器
这不能保证工作。不安全地派生的指针是无效的，即使它恰好等于安全派生的指针（3.7.4.3/4）。我也很惊讶。
An XOR linked list is a modified version of a normal doubly-linked list in which each node stores just one "pointer" instead of two. That "pointer" is composed of the XOR of the next and previous pointers. To traverse the list, two pointers are needed - one to the current node and one to the next or previous node. To traverse forward, the previous node's address is XORed with the "pointer" stored in the current node, revealing the true "next" pointer.
The C++ standard causes a bunch of operations on pointers and integers to result in undefined behavior - for example, you cannot guarantee that setting a particular bit in a number will not cause the hardware to trigger an interrupt, so in some cases the results of bit twiddling can be undefined.
My question is the following: is there a C++ implementation of an XOR linked list that does not result in undefined behavior?
解决方案 If by "is there an implementation" you mean "has it already been written" then I don't know. If you mean "is it possible to write one" then yes it is but there might be some caveats about portability.
You can bit-twiddle to your heart's content if you convert both pointers to uintptr_t before you start, and store that type in the node instead of a pointer. Bitwise operations on unsigned types never result in undefined behavior.
However, uintptr_t is an optional type and so it's not entirely portable. There is no requirement that a C++ implementation actually has an integer type capable of representing an address. If the implementation doesn't have uintptr_t then the code is permitted to compile with a diagnostic, in which case its behavior is outside the scope of the standard. Not sure whether you consider that an infringement of "without UB" or not. I mean, seriously, a compiler that allows code which uses undefined types? ;-)
To avoid uintptr_t I think that you could do your bit-twiddling on an array of sizeof(node*) unsigned chars instead. Pointers are POD types and so can be copied, spindled and mutilated provided that the object representation is restored to its original condition before being used as a pointer.
Note also that if your C++ implementation has a garbage collector, then convert-to-integer / xor / xor-back-again / convert-to-pointer doesn't necessary stop the object being collected (because it results in an "unsafely derived pointer"). So for portability you must also ensure that the resulting pointers are valid. Two ways to do this:
- call
declare_reachable on them. - Use an implementation with relaxed pointer safety (it is implementation-defined whether this is the case, and you can test for it with
get_pointer_safety() bearing in mind that a relaxed implementation is allowed to falsely claim that it's strict).
You might think that there's a third way (albeit one that defeats the purpose of the XOR linked list unless you happen to have it anyway):
- keep a separate container of all the pointer values
This is not guaranteed to work. An unsafely derived pointer is invalid even if it happens to be equal to a safely-derived pointer (3.7.4.3/4). I was surprised too.
这篇关于XOR链表可以在C ++中实现而不会导致未定义的行为？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！