使用迭代器从C中的向量末尾删除元素

发布时间：2020-12-16 09:51:43 所属栏目：百科来源：网络整理

导读：我想以相反的顺序从向量中删除元素,从最后一个元素开始.据我所知,使用迭代器执行此操作的最简单方法是： std::vectorint data = ...std::vectorint::iterator iter;for(iter = data.end() - 1; iter != data.begin() - 1; iter--) { data.erase(iter);} 我的

我想以相反的顺序从向量中删除元素,从最后一个元素开始.据我所知,使用迭代器执行此操作的最简单方法是：

std::vector<int> data = ...
std::vector<int>::iterator iter;
for(iter = data.end() - 1; iter != data.begin() - 1; iter--) {
    data.erase(iter);
}

我的问题是,这些erase()调用中的每一个都是O(1),因为我们最后会删除,即使删除的一般复杂性是O(n)？此外,假设向量至少有1个元素,此代码是否“安全”？

解决方法

不,你的算法有UB.
如果没有,它将有O(n).
将正文更改为此将删除UB：iter = data.erase(iter);
为什么？因为vector.erase()的行为如下：

>效果：在擦除点处或之后使迭代器和引用无效.
>复杂性：T的析构函数被称为等于元素数量的次数
擦除,但T的移动赋值运算符被称为等于数的次数
擦除元素后向量中的元素.

如果你像这样重写循环,它甚至可以用于空容器：

for(auto it = data.end(); it!=data.begin(); it = data.erase(it-1)) /**/;

它等于：

std::remove_if(data.rbegin(),data.rend(),[](data::reference x){return true;});

无论如何,使用data.clear(),data.resize(0)或使用临时空向量进行交换很可能会更快.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!