std::vector和std::deque的情况稍有不同，C98和C11的情况也有所不同。

标准：：向量

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 x一个月10个月1个月：

iterator erase(iterator position);
iterator erase(iterator first, iterator last);

• 复杂度：* 析构函数的调用次数与被擦除元素的数量相同，但赋值运算符的调用次数 * 至多 * 等于被擦除元素之前的元素数量和被擦除元素之后的元素数量中的最小值。

C++14草图N4140 x1米11分：

• 复杂度：* 析构函数的调用次数与被擦除元素的数量相同，但赋值运算符的调用次数 * 不多于 * 被擦除元素之前的元素数量和被擦除元素之后的元素数量中的较小者。

所以，C98和C11/14中是一样的，除了C++11可以在移动赋值和复制赋值之间选择（这里我看到标准中的一些不一致，因为措辞没有提到std::vector的移动赋值-可能是另一个问题的原因）。
还要注意措辞中的“最多”和“不再”，这使得实现比线性更高效，尽管实际上它们是线性的（DEMO）。

删除一个向量中的元素是O（n）的，因为一旦你删除了这个元素，你仍然需要移动所有后续的元素来填充所产生差距。如果一个向量有n个元素，那么，在最坏的情况下，你需要移动n-1个元素，因此复杂度是O（n）。

删除元素确实是O(n)，不是因为你必须做什么才能找到要删除的元素，而是因为你必须对它 * 之后 * 的所有元素做什么。
平均来说，擦除将占用向量一半的元素，所以你必须移动一半的元素，因此O(n)。最好的情况是擦除最后一个元素--不需要滑动;最坏的情况是擦除第一个元素--然后必须移动 * 每 * 个其他元素。

通过使用这种方式，时间复杂度=范围长度+移位长度（n -范围末端）

vector<int> it = (vector<int>::iterator) &vec[pos];
    vec.erase(it, it+length);