为什么在向量中间添加或删除元素这么慢？

Question

根据Accelerated C++:

要使用此策略,我们需要一种从向量中删除元素的方法.好消息是这样的设施存在; 坏消息是从向量中删除元素的速度足够慢,不能反对将大量输入数据用于此方法.如果我们处理的数据变得非常大,性能会下降到惊人的程度.

例如,如果我们所有的学生都失败了,我们即将看到的功能的执行时间将与学生数量的平方成比例增长.这意味着对于100名学生来说,该课程的运行时间将是一名学生的10,000倍.问题是我们的输入记录存储在一个向量中,该向量针对快速随机访问进行了优化.该优化的一个代价是插入或删除除向量末尾之外的元素可能是昂贵的.

作者没有解释为什么向量对于10,000多名学生而言如此缓慢,以及为什么通常在向量中间添加或删除元素的速度很慢.Stack Overflow上有人可以为我提供一个漂亮的答案吗？

Answer 1

拿一排房子:如果你把它们建成一条直线,那么找到32号就很容易了:沿着这条路走32个房子的价值,你就在那里.但是在中间添加31号房子并不是那么有趣 - 这是一个大型建筑项目,对丈夫/妻子和孩子的生活造成很大的干扰.在最糟糕的情况下,路上没有足够的空间用于另一栋房屋,所以你必须在开始之前将所有房屋搬到另一条街道.

类似地,向量连续地存储它们的数据,即在存储器中的连续顺序块中.

这对于快速找到第n ^个元素非常有用(因为你只需要沿着n个位置和取消引用),但是插入到中间非常糟糕,因为你必须一次一个地移动所有后面的元素,一次一个.

其他容器设计为易于插入元件,但权衡的是它们因此不容易找到东西.没有容器是所有操作的最佳选择.