通过交换到结尾从向量擦除 [英] Erasing from vector by swapping to the end

问题描述

我想知道为什么没有STL函数通过将向量交换到结尾然后将其删除来从向量中删除该元素.如果您不关心元素的实际顺序，但仍然希望快速遍历，是否有比 std :: vector 更好的数据结构?

I am wondering why there is no STL function that deletes an element from a vector by swapping it to the end and then removing it. Is there a better data structure than std::vector if you don't care about the actual order of elements and still want very fast traversal?

请注意，使用 std :: remove 和 std :: erase 并不相同，因为这是线性时间，而不是恒定时间，因为必须保留顺序.

Note that using std::remove and std::erase is not the same because this is linear time instead of constant time as the order has to be preserved.

推荐答案

您可以使用 std :: partition 代替 std :: remove / std :: remove_if :

仅保留大于3的值:

std::vector foo{1,2,3,4,5,6,7,8};

foo.erase(std::partition(foo.begin(),
                         foo.end(),
                         [](auto& v) { return v > 3; }
                        ),
          foo.end());

或者您可以使其类似于 std :: erase在C ++ 20中添加的/std :: erase_if(std :: vector) 对，并返回已删除元素的数量.我称它们为 unstable__erase 和 unstable__erase_if .

Or you could make it similar to the std::erase / std::erase_if (std::vector) pair that was added in C++20 and return the number of erased elements. I call them unstable__erase and unstable__erase_if.

// Erases all elements that compare equal to value
template<class T, class Alloc, class U>
[[maybe_unused]] constexpr typename std::vector<T,Alloc>::size_type
unstable_erase(std::vector<T,Alloc>& c, const U& value) {
    return unstable_erase_if(c, [&value](auto& v) { return v == value; });
}

// Erases all elements that satisfy the predicate pred
template<class T, class Alloc, class Pred>
[[maybe_unused]] constexpr typename std::vector<T,Alloc>::size_type
unstable_erase_if(std::vector<T,Alloc>& c, Pred pred) {
    using size_type = typename std::vector<T,Alloc>::size_type;

    auto p = std::partition(c.begin(), c.end(), std::not_fn(pred));
    auto count = static_cast<size_type>(std::distance(p, c.end()));
    c.resize(c.size() - count);

    return count;
}

---

由于 std :: partition 交换了一些原本希望通过替换上述内容而能够提高速度的元素

---

Since std::partition swaps elements I was expecting to be able to improve on the speed by replacing the above

    auto p = std::partition(c.begin(), c.end(), std::not_fn(pred));

使用

    auto p = unstable_remove_if(c.begin(), c.end(), pred);

我在以下定义了 unstable_remove_if 的地方:

where I've defined unstable_remove_if as below:

template<class ForwardIt, class UnaryPredicate>
constexpr ForwardIt
unstable_remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p) {
    for(;first != last; ++first) {
        if(p(*first)) { // found one that should be removed

            // find a "last" that should NOT be removed
            while(true) {
                if(--last == first) return last;
                if(not p(*last)) break;          // should not be removed
            }
            *first = std::move(*last);           // move last to first
        }
    }
    return last;
}

但是，令我惊讶的是，在 https://quick-bench.com/中运行该命令他们对基本类型的表现同样快(最多为 long double ).

but, to my surprise, running that in https://quick-bench.com/ showed that they performed equally fast for fundamental types (up to long double).

对于较大的类型，它显示了很大的改进(32-64字节类型的速度是8-16倍)，因此请在中使用 unstable_remove_if > unstable_erase_if(std :: vector)可能是寻求删除与某个谓词或值匹配的元素的通用解决方案的方法.

For larger types, it showed a big improvement (8-16 times as fast for 32 - 64 byte types), so using the unstable_remove_if in unstable_erase_if (std::vector) is probably the way to go for a generic solution of removing elements matching a certain predicate or value.

这篇关于通过交换到结尾从向量擦除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！