我已经读过将项目添加到结尾的时间复杂度 std::vector 是摊销常数并在a的顶部和底部插入项目 std::deque 因为这两个容器都有一个随机访问迭代器，因此访问任何索引处的元素是不变的。如果我有任何这些事实错误，请告诉我。我的问题是如果访问一个元素 std::vector 要么 std::deque 那么为什么通过擦除O（n）去除元素的时间复杂度是恒定的。其中一个答案 这里 这里指出通过擦除去除元素是O（n）。我知道擦除会删除起始迭代器和结束迭代器之间的元素，所以答案基本上意味着它 O(n) 取决于两个迭代器之间的元素的数量，并且从任何索引中的vector / deque中删除单个元素将为零？
事情有点不同 std::vector 和 std::deque，以及它们与C ++ 98和C ++ 11不同。
复杂性 std::vector::erase() 对于擦除范围的长度和范围的末端与容器的末端之间的元素数量是线性的（因此从末尾擦除元素需要恒定的时间）。
C ++ 2003 [lib.vector.modifiers] 内容如下：
iterator erase(iterator position);
iterator erase(iterator first, iterator last);`
...
复杂： 析构函数
T被称为次数等于被删除元素的数量， 但是 赋值运算符 的T被称为次数等于被擦除元素后向量中元素数量的次数。
C ++ 14草案N4140 [vector.modifiers] 内容如下：
复杂： 析构函数
T被称为等于元素数量的次数 擦除了，但是 移动赋值运算符 的T被称为等于数量的次数 擦除元素后向量中的元素。
因此，您可以看到C ++ 11/14实现通常更有效，因为它执行移动分配而不是复制分配，但复杂性保持不变。
复杂性 std::deque::erase() 是擦除范围的长度和线性的线性 最低限度 两个数字：范围开始之前剩余元素的数量，以及范围结束后剩余元素的数量。因此，从开头或结束擦除元素需要恒定的时间。
C ++ 2003 [lib.deque.modifiers]：
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
复杂： 对析构函数的调用次数与擦除的元素数相同，但是 赋值运算符的调用次数是 最多 等于元素数量的最小值 在擦除元素之前和擦除元素之后的元素数量。
C ++ 14草案N4140 [deque.modifiers]/5：
复杂： 对析构函数的调用次数与擦除的元素数相同，但对赋值运算符的调用次数为 不再 比擦除元素之前的元素数量和擦除元素之后的元素数量中的较少者一样。
所以，它在C ++ 98和C ++ 11/14中是相同的，除了C ++ 11可以在移动赋值和复制赋值之间进行选择（这里我看到标准中的一些不一致，因为措辞没有提到移动如此转让 std::vector - 可能是另一个问题的原因）。
还要注意措辞中的“最多”和“不再”。这允许实现比线性更有效，但在实践中它们是线性的（DEMO）。
擦除向量中的元素是O（n），因为一旦删除元素，您仍需要移动所有连续元素以填充创建的间隙。如果向量具有n个元素，那么在最坏的情况下，您将需要移位n-1个元素，因此复杂度为O（n）。
确实是删除元素 O(n) 不是因为你要做的就是要找到要删除的元素，而是因为你要对所有的元素做些什么 后 它。需要向下滑动这些元素以填充空槽。
因此，平均而言，擦除将在向量的一半处占据一个元素，因此您将不得不移动大约一半的元素。于是 O(n)。最好的情况是，你删除最后一个元素 - 不需要滑动。最糟糕的情况是，你擦掉第一个元素 - 必须移动 一切 其他元素。