可以在 C++ 中实现 XOR 链表而不会导致未定义的行为吗? [英] Can an XOR linked list be implemented in C++ without causing undefined behavior?

问题描述

XOR 链表 是普通链表的修改版本双向链表，其中每个节点只存储一个指针"而不是两个.该指针"由下一个指针和前一个指针的异或组成.要遍历列表，需要两个指针——一个指向当前节点，一个指向下一个或上一个节点.为了向前遍历，将前一个节点的地址与当前节点中存储的指针"进行异或运算，揭示真正的下一个"指针.

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.

C++ 标准会导致对指针和整数的一系列操作导致未定义的行为 - 例如，您不能保证在数字中设置特定位不会导致硬件触发中断，因此在某些情况下位处理的结果可能是不确定的.

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.

我的问题如下:是否有不导致未定义行为的异或链表的 C++ 实现?

My question is the following: is there a C++ implementation of an XOR linked list that does not result in undefined behavior?

推荐答案

我的问题如下:是否有不导致未定义行为的异或链表的 C++ 实现?

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.

如果您在开始之前将两个指针都转换为 uintptr_t 并将该类型存储在节点中而不是指针中，则您可以随意调整自己的内容.无符号类型的按位运算永远不会导致未定义的行为.

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.

然而，uintptr_t 是一个可选类型，因此它不是完全可移植的.不要求 C++ 实现实际上具有能够表示地址的整数类型.如果实现没有 uintptr_t 则允许代码编译带有诊断，在这种情况下，其行为超出标准范围.不确定您是否认为这是对没有 UB"的侵犯.我的意思是，说真的，一个允许使用未定义类型的代码的编译器?;-)

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? ;-)

为了避免 uintptr_t 我认为你可以在 sizeof(node*) 无符号字符数组上进行位操作.指针是 POD 类型，因此可以复制、转轴和切割，前提是对象表示在用作指针之前恢复到其原始状态.

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.

还要注意，如果您的 C++ 实现有垃圾收集器，则转换为整数/异或/异或返回再次/转换为指针不需要停止正在收集的对象(因为它会导致不安全的派生指针").因此，为了可移植性，您必须还确保结果指针有效.有两种方法可以做到这一点:

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:

1. 对它们调用 declare_reachable.
2. 使用具有宽松指针安全性的实现(是否是这种情况由实现定义，您可以使用 get_pointer_safety() 测试它，记住允许宽松的实现错误地声称它是严格的).

1. call declare_reachable on them.
2. 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):

• 为所有指针值保留一个单独的容器

这不能保证有效.即使不安全派生的指针恰好等于安全派生的指针 (3.7.4.3/4)，它也是无效的.我也很惊讶.

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.

这篇关于可以在 C++ 中实现 XOR 链表而不会导致未定义的行为吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！