arrays - 什么是无界数组？

Question

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

Answer 1

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

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

以下摘录自excellent article on unbounded arrays 简洁地解释了它 -

The general implementation strategy is as follows. We maintain an array of a fixed length limit and an internal index size which tracks how many elements are actually in the array. When we add a new element we increment size, when we remove an element we decrement size. The tricky issue is how to proceed when we are already at the limit and want to add another element. At that point, we allocate a new array with a larger limit and copy the elements we already have to the new array.

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

无界数组的一些功能(设计要求):

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

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

• add_to_end()
• delete_from_end()

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

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

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

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