8

我刚刚注意到一个问题，询问在 C++ 中哪些递归数据类型（“自引用类型”）有好处，我很想大胆地声称

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

也就是说，如果您没有随机访问数组，您将需要某种方式（在逻辑上）对该类型中的类型进行引用（显然，MyClass* next您可以说不是拥有一个成员，void* next但它仍然指向一个MyClass对象或派生的类型）。

但是，我对绝对陈述很谨慎——仅仅因为我想不出某些东西并不意味着它不可能，所以我忽略了某些东西吗？是否存在既不使用类似于链表/树的机制组织也不专门使用连续序列的数据结构？

注意：这被标记为和，因为我对 C++ 语言特别感兴趣，但也对理论方面感兴趣。

4

5 回答 5

5

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

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

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

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

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

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

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

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

所以我的结论是，你的说法是绝对正确的。

于 2012-08-24T17:18:57.390 回答
2

问题是动态分配器本身正在管理连续存储。想想用于图灵机或冯诺依曼架构的“磁带”。所以要认真考虑这个问题，你可能需要开发一种新的计算模型和新的计算机架构。

如果你认为忽略底层机器的连续内存是可以的，我相信有很多解决方案是可能的。我首先想到的是容器的每个节点都标有与其在内存中的位置无关的标识符。然后，为了找到相关节点，扫描所有内存，直到找到标识符。如果在并行机器中有足够的计算元素，这甚至不是特别低效。

于 2012-08-24T17:00:30.507 回答
1

这是一个证明的草图。

鉴于程序的大小必须是有限的，程序中定义的所有类型必须只包含有限多个成员，并且只能引用有限多个其他类型。这同样适用于任何程序入口点和在程序初始化之前定义的任何对象。

在没有连续数组的情况下（它是具有运行时自然数的类型的乘积，因此大小不受限制），所有类型都必须通过上述类型的组合来获得；类型的派生（pointer-to-pointer-to- ）仍然受到程序大小的限制。除了连续数组之外，没有其他工具可以用类型组合运行时值。A

这有点争议；如果例如映射被认为是原始的，那么可以使用其键是自然数的映射来近似数组。当然，任何映射的实现都必须使用自引用数据结构（B 树）或连续数组（哈希表）。

接下来，如果类型是非递归的，那么任何类型链（A引用B引用C...）都必须终止，并且长度不能大于程序中定义的类型数。因此，程序可引用的数据的总大小限制为每种类型的大小乘以程序中定义的名称数量（在其入口点和静态数据中）的乘积。

即使函数是递归的也是如此（严格来说，这违反了对递归类型的禁令，因为函数是类型）；在程序中的任何一点立即可见的数据量仍然限于每种类型的大小乘以该点可见名称的数量的乘积。

一个例外是，如果您将“容器”存储在递归函数调用堆栈中；但是，这样的程序将无法在不展开堆栈并且必须重新读取数据的情况下随机遍历其数据，这有点失格。

最后，如果可以动态创建类型，则上述证明不成立；例如，我们可以创建一个 Lisp 样式的列表结构，其中每个单元格都是不同的类型：cons<4>('h', cons<3>('e', cons<2>('l', cons<1>('l', cons<0>('o', nil))))). 这在大多数静态类型语言中是不可能的，尽管在某些动态语言中是可能的，例如 Python。

于 2012-08-24T17:19:53.407 回答
0

该说法不正确。简单的反例是std::deque用 C++ 编写的。基本数据结构（对于与语言无关的部分）是指向数据数组的指针的连续数组。实际数据存储在绳索（非连续块）中，它们通过连续数组链接。

这可能会超出您的要求，具体取决于不使用连续内存区域的含义。我使用的解释是存储的数据不连续，但是这种数据结构依赖于中间层的数组。

于 2012-08-24T16:46:35.597 回答
0

我认为更好的措辞是：

It's the only way to construct data structures (more precisely containers) that can accept 
arbitrary large data collections without using memory areas of determinable address.

我的意思是普通数组用于addr(idx)=idx*size+inital_addr获取元素的内存地址。但是，如果将其更改为类似addr(idx)=idx*idx*size+initial_addr的内容，则数据结构的元素不会存储在连续的内存区域中，而是在存储元素的位置之间存在很大差距。因此，它不是连续记忆。

于 2012-08-24T17:04:18.850 回答