什么是无界的阵列？ [英] What is an unbounded array?

问题描述

什么是无限的阵列，是有一个无限阵列和动态分配的数组有什么区别？什么是与无限阵列相关的常见操作？ （就像我们对堆栈数据结构pop和push）

What is an unbounded array and is there any difference between an unbounded array and a dynamically allocated array? What are the common operations associated with the unbounded array? (like we have pop and push for stack data structure)

推荐答案

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

Unbounded arrays can be (and usually are) statically allocated.

实施一个无限阵列时关注的首要问题是提供动态数组喜欢自由决定在运行时数组的大小不运行时内存分配的性能损失。

The primary concern when implementing an unbounded array is to provide dynamic-array like freedom to decide the array size during run-time without the performance penalties of run-time memory allocation.

从的中无界数组精彩文章 解释简明扼要 -

The following excerpt from an excellent article on unbounded arrays explains it succinctly -

一般的实现策略如下。我们维持一个固定长度的 限制 的数组和内部指数 尺寸 追踪许多元素实际上是如何在数组中为止。当我们添加新元素，我们增加的 尺寸 ，当我们删除，我们递减的元素 尺寸 。棘手的问题是如何，当我们已经在 上限进行 并希望添加另一个元素。在这一点上，我们分配具有较大的 限制 一个新的数组和复制我们已经有了新的数组中的元素。

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.

请注意，在运行时，直到尺寸超过限制的初始值没有涉及动态分配采用无界数组。

Notice that during run-time, until size exceeds the initial value of limit there is no dynamic allocation involved with an unbounded array.

一些功能的无限阵列（设计要求）：

Some features (design requirements) of an unbounded array :

• 获取或在特定的索引设置值（固定时间）


• 遍历为了元素（线性时间，良好的缓存性能）


• 插入或删除在数组的结尾元素（恒摊余时间）

饲养的表现，唯一额外的操作（与常规数组）与无限阵列相关的是：

Keeping performance in mind, the only additional operations(compared to regular arrays) associated with unbounded arrays are :

• add_to_end（）


• delete_from_end（）

• add_to_end()
• delete_from_end()

，以允许修改无限数组的大小。

to allow modifying the size of the unbounded array.

操作，如 Insert_in_middle（）和 Delete_in_middle（）未提供牢记的一个主要设计原理无界数组即表现。

Operations like Insert_in_middle() and Delete_in_middle() are NOT provided keep in mind the primary design principle of an unbounded array i.e. performance.

有关详细信息，检出回答这个问题。

For more details, checkout the answers to this question.

<子>注：虽然这个问题特别提到的动态分配数组，也许你可能也想签的 动态数组 。一个动态数组的一个很好的例子是 C ++的std ::矢量 本身，这涉及几个相同的设计原则，作为一个无限阵列。

_{NOTE : Though the question specifically mentions dynamically allocated arrays, probably you might also want to checkout dynamic arrays. A good example of a dynamic-array is the C++ std::vector itself which addresses several of the same design principles as that of an unbounded array.}

这篇关于什么是无界的阵列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！