c++ - 当我不关心顺序并且没有重复项时，更快的删除删除习惯用法？

Question

我有一个对象 vector ，想要按值删除。但是，该值仅出现一次(如果有的话)，而且我不关心排序。

显然，如果这种按值删除非常常见，和/或数据集相当大，那么 vector 就不是最好的数据结构。但假设我已经确定情况并非如此。

要明确的是，如果我的代码是 C，我会对以下内容感到满意:

void delete_by_value( int* const piArray, int& n, int iValue ) {
    for ( int i = 0; i < n; i++ ) {
        if ( piArray[ i ] == iValue ) {
            piArray[ i ] = piArray[ --n ];
            return;
        }
    }
}

使用 std::algos 和容器方法的“现代习语”方法似乎是:

v.erase(std::remove(v.begin(), v.end(), iValue), v.end());

但是这应该慢得多，因为对于随机存在的元素，它需要 n/2 次移动和 n 次比较。我的版本是 1 次移动，n/2 次比较。

在“现代习语”中肯定有比删除删除习语更好的方法吗？如果不，为什么不呢？

Answer 1

使用std::find来替换循环。从 end 迭代器的前身获取替换值，并使用该迭代器删除 该元素。由于此迭代器指向最后一个元素，因此删除很便宜。奖励:bool 返回成功检查和 int 上的 template。

template<typename T>
bool delete_by_value(std::vector<T> &v, T const &del) {
    auto final = v.end();
    auto found = std::find(v.begin(), final, del);
    if(found == final) return false;
    *found = *--final;
    v.erase(final);
    return true;
}