C++关于erase的复杂度

被这个问题困扰了很多次,有必要整理一下。

当然最好的参考资料就是http://www.cplusplus.com/reference/set/set/erase/ 里的Complexcity部分了,但是有必要记住常见的一些复杂度。否则会掉坑的。

先来看一下vector的erase复杂度:

Linear on the number of elements erased (destructions) plus the number of elements after the last element deleted (moving).

析构函数的复杂度和后面要移动的复杂度,所以一般情况下如果不是删除最后一个(当然删除最后一个直接用pop_back()就可以了)是O(1)外,其它都是O(n),即线性的。

再来看一下set的erase复杂度如下,它有三种情况的erase,复杂度不同

(1)iterator erase (const_iterator position);
(2) size_type erase (const value_type& val);

>(3) iterator erase (const_iterator first, const_iterator last);

For the first version (erase(position)), amortized constant.
For the second version (erase(val)), logarithmic in container size.
For the last version (erase(first,last)), linear in the distance between first and last.

第一种方法也就是删除迭代器的位置,复杂度是摊销常数;第二种方法也就是直接删除一个常数,复杂度是log,最后一种删除一段区间,复杂度是O(n)

可以看到,如果我们的序列本身有序并且删除的位置可以确定或者值确定,那么用vector会很慢,这时可以考虑set或者是手写erase类似这种


上周周六打完了蓝桥杯和TCO Beijing后,放飞自我了一天。又得赶DDL了。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注