什么是无界数组?无界数组和动态分配数组有什么区别?与无界数组相关的常见操作有哪些? (就像我们有堆栈数据结构的弹出和推送)
无界数组可以(并且通常是)静态分配。
实现无界数组时的主要关注点是提供类似动态数组的自由来在运行时决定数组大小,而不会因运行时内存分配而造成性能损失。
以下内容摘自一篇关于无界数组的优秀文章简单地解释一下——
总体实施策略如下。我们维护一个固定长度的数组limit
和一个内部索引size
它跟踪数组中实际有多少元素。当我们添加一个新元素时,我们会递增size
,当我们删除一个元素时,我们会递减size
。棘手的问题是当我们已经达到了目标时如何继续limit
并想添加另一个元素。此时,我们分配一个更大的新数组limit
并将我们已有的元素复制到新数组中。
请注意,在运行时,直到size
超过初始值limit
无界数组不涉及动态分配。
Some features无界数组的(设计要求):
- 获取或设置特定索引处的值(恒定时间)
- 按顺序迭代元素(线性时间,良好的缓存性能)
- 在数组末尾插入或删除元素(恒定摊销时间)
考虑到性能,与无界数组相关的唯一附加操作(与常规数组相比)是:
add_to_end()
delete_from_end()
允许修改无界数组的大小。
类似的操作Insert_in_middle()
and Delete_in_middle()
不提供请记住无界数组的主要设计原则,即性能。
欲了解更多详细信息,请查看此问题的答案question.
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.
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)