我想插入元素i进入std::vector someVector,但不希望使用.insert(),因为它是O(n)的复杂性,因为(据我所知),它推回所有其他元素.
无论如何在恒定时间内这样做,类似于用于擦除的交换/调整大小技巧？
是的,如果您可以接受对插入或删除位置的顺序访问的限制.
基本思想被称为光标间隙(因为它用于早期文本编辑器)或更一般地称为间隙缓冲结构.有一个关于它的维基百科文章.但简而言之,您只需保留所有未使用项目的序列或"间隙",其中您具有插入/删除位置,并且移动插入/删除位置一步对应于将实际项目从一侧复制到另一侧.间隙.
具有连续索引范围的索引仍然是恒定时间,中间有间隙(您只需要正确定义它),但是为了然后将向量缓冲区直接用作连续数组,必须将间隙移动到一侧,这是一个线性时间操作.
| 归档时间： |
|
| 查看次数： |
317 次 |
| 最近记录： |