1

我有一个对象向量，想按值删除。但是，该值仅出现一次，我不关心排序。

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

需要明确的是，如果我的代码是 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 比较。

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

4

4 回答 4

2

用于std::find替换循环。从迭代器的前身获取替换值end，并将该迭代器用于erase该元素。因为这个迭代器是最后一个元素，erase所以很便宜。奖励：bool返回成功检查并template结束int。

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;
}
于 2019-12-30T03:51:36.287 回答
2

在“现代成语”中肯定有比擦除-删除-成语更好的方法吗？

标准库中没有针对每个利基用例的现成函数。Unstable remove 是未提供的功能之一。不久前就有人提出过（p0041r0）。同样，对于不包含重复的向量的特殊情况，也没有特殊版本的算法。

因此，如果您希望使用最佳算法，则需要自己实现该算法。有std::find用于线性搜索。之后，您只需要从最后一个元素进行分配，最后将其弹出即可。

于 2019-12-30T06:59:19.983 回答
0

如果您使向量的大小更小，则大多数实现std::vector::resize都不会重新分配。因此，以下可能与 C 示例具有相似的性能。

void find_and_delete(std::vector<int>& v, int value) {
    auto it = std::find(v.begin(), v.end(), value);
    if (it != v.end()) {
        *it = v.back();
        v.resize(v.size() - 1);
    }
}
于 2019-12-30T03:36:55.160 回答
0

C++ 方式与以下内容基本相同std::vector：

template <typename T>
void delete_by_value(std::vector<T>& v, const T& value) {
    auto it = std::find(v.begin(), v.end(), value);

    if (it != v.end()) {
        *it = std::move(v.back());
        v.pop_back();
    }
}
于 2019-12-30T07:30:47.877 回答