我意识到一个可调整大小的索引集合,它使用一个数组来存储它的元素(比如List<T>在.NET或ArrayListJava中),在集合的末尾分配了O(1)插入时间.但是在关键接合点处总是有一个令人讨厌的插入,其中集合刚刚达到其容量,并且下一次插入需要将内部阵列中的所有元素的完整副本转换为新的元素(可能是两倍大).
一个常见的错误(在我看来)是使用链表来"修复"这个问题; 但我相信为每个元素分配一个节点的开销可能非常浪费,事实上,在极少数情况下阵列插入成本很高的情况下,保证O(1)插入的好处相形见绌 - 事实上,其他每一个阵列插入明显更便宜(也更快).
我认为可能有意义的是一种混合方法,它由一个链接的数组列表组成,每当当前的"head"数组达到其容量时,一个两倍大的新数组被添加到链表中.然后,由于链表仍然具有原始数组,因此不需要复制.从本质上讲,这似乎与我相似(List<T>或者说是ArrayList方法),除了以前你曾经承担过复制内部数组所有元素的成本,这里你只需要分配新数组和单个节点插入的成本.
当然,如果需要它们会使其他特征复杂化(例如,插入/移出集合的中间); 但正如我在标题中所表达的那样,我真的只是在寻找一个只添加(和迭代)的集合.
是否有适合此目的的数据结构？或者,你能想到一个吗？
刚刚学习Python.阅读官方教程.我碰到了这个:
虽然列表末尾的追加和弹出很快,但是从列表的开头进行插入或弹出是很慢的(因为所有其他元素都必须移动一个).
我猜想像Python这样的成熟语言会有各种各样的优化,那么为什么Python [似乎]不会使用链接列表以便插入速度快？
我满怀希望地输入with Ada.Containers.以查看自动完成列表，但没有看到Stack或列出任何类似的内容。Ada 标准库真的没有堆栈实现吗？
在 Rosetta Code 上，我发现了这个堆栈实现，它非常缺乏，因为它为每个添加的单个节点运行到分配器。
我觉得一定有一些我必须错过的“其他 Ada 标准库”，因为我不断遇到明显缺失的基本库功能。