递归类型真的是构建非连续任意大小数据结构的唯一方法吗？

Question

我刚刚注意到一个问题,询问递归数据类型("自引用类型")在C++中是否有用,我很想大胆宣称

这是构建数据结构(更准确地说是容器)的唯一方法,它可以接受任意大数据集合而不使用连续的内存区域.

也就是说,如果你没有随机访问数组,你需要一些引用(逻辑上)对该类型内的类型的方法(显然,不是有一个MyClass* next你可以说的成员,void* next但仍然指向一个MyClass对象或派生的类型).

但是,我对绝对陈述很谨慎 - 只因为我想不出某些东西并不意味着它不可能,所以我忽略了什么？是否有数据结构既没有使用类似于链表/树的机制进行组织,也没有使用连续序列？

---

注意:这被标记为c ++和语言无关,因为我特别感兴趣的是C++语言,但也有理论方面.

Answer 1

这是构建可以接受任意大数据集合而不使用连续内存区域的数据结构（更准确地说是容器）的唯一方法。

想了想，这个说法似乎是对的。事实上，这是不言而喻的。

假设我在非连续内存中有一组元素。还假设我目前在 element e。现在的问题是，我如何知道集合中的下一个元素？有什么办法吗？

给定e集合中的一个元素，只有两种方法可以计算下一个元素的位置：

• 如果我假设它在偏移处，sizeof(e)而不管是什么e，那么这意味着下一个元素从当前元素结束的地方开始。但这意味着该集合位于连续内存中，这在本讨论中是被禁止的。

• 元素e本身告诉我们下一个元素的位置。它可以存储地址本身或偏移量。无论哪种方式，它都使用了自引用的概念，这在本次讨论中也是被禁止的。

在我看来，这两种方法的基本思想完全相同：它们都实现了自引用。唯一的区别是，在前者中，自引用是隐式实现的，使用sizeof(e)as offset。这种隐式自引用由语言本身支持，并由编译器实现。在后者中，很明显，一切都由程序员自己完成，因为现在偏移量（或指针）存储在元素本身中。

因此，我没有看到任何第三种实现自我参考的方法。如果不是自引用，那么将使用什么术语来描述下一个元素到元素的位置的计算e。

所以我的结论是，你的说法是完全正确的。