异或链表

Question

我最近发现了下面的链接，我发现它非常有趣。

http://en.wikipedia.org/wiki/XOR_linked_list

• 通用调试工具 无法遵循 XOR 链，使得 调试比较困难； [1]
• 内存减少的代价 使用量是代码的增加 复杂性，使维护工作更加繁琐 昂贵的;
• 大多数垃圾收集方案都会这样做 不适用于这样做的数据结构 不包含文字指针；
• 指针的 XOR 未定义在 一些上下文（例如，C 语言）， 尽管许多语言都提供了一些 之间的类型转换 指针和整数；
• 如果出现以下情况，指针将不可读 一个人没有遍历该列表 - 因为 例如，如果指向列表的指针 项目包含在另一个数据中 结构;
• 在遍历列表时，您需要 记住地址 之前访问过的节点 计算下一个节点的地址。

现在我想知道这是否是低级语言独有的，或者在 C# 中是否也可能？

是否有任何类似的选项可以使用 C# 产生相同的结果？

Answer 1

TL;DR 我快速编写了一个概念验证XorLinkedList 实现 在 C# 中。

使用 C# 中的不安全代码绝对可以做到这一点。但有一些限制：

1. XorLinkedList 必须是“非托管结构”，即它们不能包含托管引用
2. 由于 C# 泛型的限制，链接列表不能是泛型的（即使使用 where T : struct)

后者似乎是因为您无法将泛型参数限制为非托管结构。仅使用 where T : struct 您还可以允许包含托管引用的结构。

这意味着您的 XorLinkedList 只能保存原始值，如整数、指针或其他非托管结构。

我知道， C# 中的低级编程

private static Node* _ptrXor(Node* a, Node* b)
{
    return (Node*)((ulong)a ^ (ulong)b);//very fragile
}

非常脆弱。 C# 指针和 IntPtr 不支持 XOR 运算符（可能是个好主意）。

private static Node* _allocate(Node* link, int value = 0)
{
    var node = (Node*) Marshal.AllocHGlobal(sizeof (Node));
    node->xorLink = link;
    node->value = value;
    return node;
}

之后不要忘记 Marshal.FreeHGlobal 这些节点（实现完整的 IDisposable 模式，并确保将免费调用放在 if(dispose) 块之外。

private static Node* _insertMiddle(Node* first, Node* second, int value)
{
    var node = _allocate(_ptrXor(first, second), value);
    var prev = _prev(first, second);
    first->xorLink = _ptrXor(prev, node);
    var next = _next(first, second);
    second->xorLink = _ptrXor(node, next);
    return node;
}

结论 就

我个人而言，我永远不会在 C# 中使用 XorLinkedList（也许）。当我在 C 中编写非常低级的系统内容（例如内存分配器或内核数据结构）时，在任何其他设置中，存储效率的微小提高确实不值得，因为您不能将其与托管对象一起使用。在 C# 中，它对于日常编程来说几乎没有用处。

而且，即使是主内存，存储也几乎是免费的，如果您使用 C#，您可能不太关心存储，我在某处读到过 CLR 对象头。 40字节，所以这个指针将是你最不担心的；）

Answer 2

C# 通常不允许您在该级别操作引用，因此不幸的是。

Answer 3

作为已提出的不安全解决方案的替代方案。

如果您使用数组或列表集合支持链接列表，其中“下一个”和“上一个”而不是内存指针指示数组中的索引，您可以实现此异或，而无需诉诸使用不安全的功能。

Answer 4

有多种方法可以在 C# 中使用指针，但只能暂时拥有指向对象的指针，因此在这种情况下不能使用它们。造成这种情况的主要原因是垃圾收集——只要您可以执行异或指针之类的操作并稍后对其进行反异或，GC 就无法知道收集某些对象是否安全。

您可以通过使用一个大数组中的索引来模拟指针来制作非常类似的东西，但是您必须自己实现一种简单形式的内存管理（即，当创建新节点时，我应该将其放在数组中的哪个位置？）。

另一种选择是使用 C++/CLI，它一方面允许您充分灵活地使用指针，另一方面允许您在需要时使用 GC 和访问框架。

Answer 5

当然。您只需要编写该类的代码即可。 C# 中的异或运算符是 ^
这应该就是开始编码所需的全部内容。
请注意，这将要求代码被声明为“不安全”。请参阅此处：了解如何在c#.

Answer 6

在这里进行广泛的概括：C# 似乎已经走上了可读性和干净接口的道路，而不是位摆弄和尽可能密集地打包所有信息的道路。

因此，除非您有特殊需要，否则您应该使用为您提供的列表。未来的维护程序员会为此感谢你。

Answer 7

这是可能的，但是您必须了解 C# 如何看待对象。实例变量实际上并不包含对象，而是指向内存中对象的指针。

DateTime dt = DateTime.Now;

dt 是指向内存中包含 DateTime 方案的结构的指针。

因此，您可以执行这种类型的链表，尽管我不确定为什么您会这样做，因为框架通常已经实现了最有效的集合。作为一个思想实验，这是可能的。