c++ - Erasing from vector by swapping to the end

Question

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?

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.

question from:https://stackoverflow.com/questions/65893596/erasing-from-vector-by-swapping-to-the-end

Answer 1

You can use std::partition instead of std::remove/std::remove_if:

Keep only values greater than 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());

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;
}

---

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));

with

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

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;
}

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

Edit: 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.