kra*_*mer 8 compiler-optimization data-structures
什么是阴影数组以及它是如何实现的？我在阅读有关编译器优化的同时完成了这个术语,但是我找不到任何有关它的实质性参考.
jwr*_*ush 13
当使用数组实现动态可调整大小的抽象数据类型(例如List,Queue或Stack)时,遇到的一个明显问题是数组本身不能自由调整大小.在某些时候,如果有人向数组中添加了足够多的项目,那么最终会耗尽空间.
这个问题的天真解决方案是等到使用的数组空间不足然后创建一个新的更大的数组,将旧数组中的所有项目复制到新数组中,然后使用新数组开始.
使用抽象数据类型实现的阴影数组是另一种选择.不是等到旧数组已满,而是在正在使用的数组上传递一些饱和度阈值之后创建第二个更大的数组.此后,当项目被添加到旧数组时,多个项目将从旧数组复制到阴影数组,这样当旧数组已满时,所有项目都已复制到新数组.
使用影子阵列实现而不是天真的"最后复制一切"方法的优点是每个添加操作所需的时间更加一致.