c++ - 有没有办法在 vector 常数时间的中间插入一些东西

Question

我想将元素 i 插入 std::vector someVector 但不想使用 .insert() 因为它是O(n) 的复杂性，因为(据我所知)它推回了所有其他元素。

有没有类似于删除的交换/调整大小技巧在恒定时间内这样做？

Answer 1

是的，如果您可以接受对插入或删除位置的顺序访问的限制。

基本思想被称为光标间隙(因为它在早期的文本编辑器中使用)或更普遍的间隙缓冲区结构。有一个 Wikipedia article about it .但简而言之，您只需维护具有插入/删除位置的所有未使用项目的序列或“间隙”，并且将插入/删除位置移动一步对应于将真实项目从一侧复制到另一侧差距。

使用连续索引范围进行索引仍然是常数时间，中间有一个间隙(您只需要正确定义它)，但是为了随后直接将 vector 的缓冲区用作连续数组，间隙必须向一侧移动，这是一个线性时间操作。