c++ - 在数组中间添加新索引

Question

我知道我可以删除数组中间的一些东西，例如

char* cArray = (char*) malloc(sizeof(char) * sizeTracker);

使用 memmove 函数。这样就可以从数组中删除一些东西，而不必使用临时数组，切换到 vector 等。这里的问题是我可以在数组中间添加一个新索引吗(是否有一个函数)？或者假设使用 realloc 我在末尾添加了一个新索引，那么如何有效地向下移动值？

Answer 1

替代答案

我一直在思考这个问题以及@DietmarKühl 开始谈论像双端队列那样插入 block 的评论。问题是双端队列是 block 的链表，所以你不能从数组开始。如果你从一个数组开始，然后想在中间插入一些东西，你必须做其他事情，我想我有一个想法 - 它没有充实很多，所以它可能行不通，但我还是会分享它。请发表评论，告诉我您对这个想法的看法。

如果您有一个项目数组，然后想在中间添加一个项目，您真正想要做的就是添加一个 block 并更新映射。映射是使它一切正常的东西 - 但它会减慢访问速度，因为您需要在每次访问数组之前检查映射。

映射将是一个二叉树。它一开始是空的，但节点将包含一个值:如果您想要的索引是<您遍历左指针的值，如果它是>=您遍历右指针。

举个例子:

插入前:

root -> (array[100000], offset: 0)

在 5000 处插入后:

root -> {value: 5000,
         left:  (array[100000], offset: 0),
         right: {value: 5001,
                 left:  (newarray[10], offset: -5000),
                 right: (array[100000], offset: 1),
                }
        }

我在这里使用了 10 个 block - newarray 的大小为 10。如果您只是在各处随机插入索引，则 block 大小应为 1，但如果您插入 blovk 大小大于 1 的连续索引组，那就更好了。这实际上取决于您的使用模式...

当您检查索引 7000 时，您检查了根节点:7000 >= 5000 因此您遵循右指针: 7000 >= 5001 因此您遵循右指针:它指向原始数组，偏移量为 1 所以你访问数组[index+offset]。

当您检查索引 700 时，您检查了根节点:700 < 5000 因此您遵循左指针:它指向偏移量为 0 的原始数组，因此您访问数组 [index+offset]。

当您检查索引 5000 时，您检查了根节点:5000 >= 5000 因此您遵循右指针: 5000 < 5001 因此您遵循左指针:它指向偏移量为 -5000 的新数组，因此你访问 newarray[index+offset]。

当然，对此进行优化对于使其有用非常重要 - 您必须在每次插入后平衡树，否则右侧会比左侧长得多。

这样做的缺点是现在对数组的访问是 O(log inserts) 而不是 O(1) 所以如果有很多插入你会想要经常重新分配以将数据结构压缩回数组但您可以在适当的时候保存它。

就像我说的那样，它不是很充实，因此在实践中可能行不通，但我希望它无论如何都值得分享。

原始答案

如果你有一个 C 风格的数组并且想在中间插入一个索引，你需要一个比你需要的更大的数组(加上一个变量，比如 sizeTracker 来跟踪大小)。

然后，如果还有剩余空间，您可以将数组的后半部分移出一个，在中间创建一个点。

如果没有剩余空间，您可以 malloc 另一个包含额外空间的整个数组，然后 memmove 前半部分和 memmove 后半部分分别留下一个空隙。

如果你想让 malloc 分摊常数时间，你需要在每次重新分配数组时将数组的大小加倍。 memmove 成为 x86 上的一条机器指令，但即使那样它仍然是 O(n) 因为移动了每个值。

但是性能并不比你的删除技巧差 - 如果你可以删除整个数组的任何地方，那么成本也是 O(n)，因为你在删除时平均移动了一半的值。