通常认为删除std :: vector中间的元素是昂贵的,因为它需要复制每个元素后才能填充这个孔.
使用C 11,std :: vector将会将所有元素下移,这应该是非常快的(如果只是相对于副本),至少我认为是这样.在时间上仍然是线性的,但一般来说它应该比旧版本快.
这会是真的吗我不必担心在中间删除一些对象吗？
解决方法
如果您考虑到标准对成本的影响,那将是非常昂贵的.该标准规定了对所包含类型执行的操作的成本,并且操作数仍然相同,只是每个操作都将更快.
作为一个例子,在C 03中考虑在矢量< string>的中间插入元素的代价.标准调用O(N),其中N是向量的大小,但实际成本是O(N * M),其中M是字符串的大小.在分析容器中的操作成本时忽略M的原因在于它取决于包含的元素.在C 0x中具有可移动类型的代价将为O(N)(字符串可以移动到新位置),但是在这两种情况下,通告的复杂度将为O(N).
对于一个简单的反例,如果您认为在C03中间插入是一个昂贵的操作,并且您考虑std :: vector< int> ;,那么在C 0x中的向量中间插入只是在这种情况下,没有加速. 还要注意,任何潜在的改进将取决于您的对象是可移动的(它们不需要),并且一些当前的STL实现已经以类似的方式进行了优化(没有语言支持),例如Dinkumware实现(我认为是这样)有一些优化,当std :: vector< std :: vector< T> >增长,它创建新的存储并用空的向量初始化(没有分配的内存,所以成本是最小的),然后交换旧的和新的分配的区域中的向量,有效地实现移动语义.
