什么是无界数组？

Question

什么是无界数组，无界数组和动态分配的数组有什么区别？与无界数组相关的常见操作有哪些？（就像我们有弹出和推送堆栈数据结构）

Answer 1

无界数组可以（并且通常是）静态分配。

实现无界数组时的主要关注点是提供类似动态数组的自由来在运行时决定数组大小，而不会因运行时内存分配而造成性能损失。

以下摘录自一篇关于无界数组的优秀文章，简洁地解释了这一点 -

总体实施策略如下。我们维护一个固定长度的数组limit和一个内部索引size，该索引跟踪数组中实际有多少元素。当我们添加一个新元素时size，我们会递增，当我们删除一个元素时，我们会递减size。棘手的问题是当我们已经到达limit并且想要添加另一个元素时如何继续。此时，我们分配一个更大的新数组limit，并将已有的元素复制到新数组中。

请注意，在运行时期间，直到size超过初始值为止，limit不涉及无界数组的动态分配。

无界数组的一些特性（设计要求）：

• 获取或设置特定索引处的值（恒定时间）
• 按顺序迭代元素（线性时间，良好的缓存性能）
• 在数组末尾插入或删除元素（恒定摊销时间）

考虑到性能，与无界数组相关的唯一附加操作（与常规数组相比）是：

• add_to_end()
• delete_from_end()

允许修改无界数组的大小。

Insert_in_middle()不提供和等操作，Delete_in_middle()请记住无界数组的主要设计原则，即性能。

有关更多详细信息，请查看此问题的答案。

_{注意：虽然问题特别提到了动态分配的数组，但您可能还想检查动态数组。动态数组的一个很好的例子就是它C++ std::vector本身，它解决了与无界数组相同的几个设计原则。}