有没有办法在向量常量时间中插入一些东西

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

无论如何在恒定时间内这样做,类似于用于擦除的交换/调整大小技巧？

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

基本思想被称为光标间隙(因为它用于早期文本编辑器)或更一般地称为间隙缓冲结构.有一个关于它的维基百科文章.但简而言之,您只需保留所有未使用项目的序列或"间隙",其中您具有插入/删除位置,并且移动插入/删除位置一步对应于将实际项目从一侧复制到另一侧.间隙.

具有连续索引范围的索引仍然是恒定时间,中间有间隙(您只需要正确定义它),但是为了然后将向量缓冲区直接用作连续数组,必须将间隙移动到一侧,这是一个线性时间操作.