使用Key Indexing来避免初始化

在c/c++中, 使用new或者malloc来分配int数组是很快的, 因为没有初始化过程. 但是在使用时会有问题: 如果不初始化, 如何知道哪一项的数据是有效的? 如果初始化, 那么效率又会比较低下.

假设有一个比较大数组a[0..n-1], 数组里每项是一个int变量, 但只有k项被使用(k « n). 如何设计一个数据结构, 避免初始化a中所有的元素, 又能正确的访问数组中的每一项? 假设内存足够.

可以使用两个长度为n的辅助数组from和to. 例如:

        0 1 2 3 4 5 6 7 8 9a    = [?|1|?|?|2|?|?|9|?|?|]from = [?|0|?|?|2|?|?|1|?|?|]to   = [1|7|4|?|?|?|?|?|?|?|]              top

from数组表示的是, a[i]被初始化时, a数组中元素的个数, 也就是说, a[i]是第from[i]个被初始化的.

to数组表示的是, 第i个被初始化的元素, 它在a中的下标是to[i].

top表示的是to数组中有效元素的个数, 指向to数组中所有有效元素的下一项, 它的值等于目前a数组中有效元素的个数.

图中为先后设置a[1]=1; a[7]=9; a[4]=2;后, a, from, to中的结果.

在设置一个元素时, 使用如下方法:

a[i] = number;if (!is_initialized(i)) {    from[i] = top;    to[top] = i;