Is there something like std::remove() which does not preserve the order of retained elements of a vector?

user_115751 0
Viewed 133

In C++14, I have a std::vector of values for which I want to remove all elements that match a given value and I do not care about preserving the order of the elements after doing the remove. The specification for std::remove provides that the relative order of the elements that remain is preserved.

Is there a built-in algorithm to do something like a std::remove but that does not preserve the order? I wish to do this since it is less work to just swap elements from the end of the vector into locations to be removed, thus scrambling the order of elements in the vector. The algorithm is still linear in that it has to visit each element to check for removal, but the amount of constant work it has to perform on each element goes way down if only a handful of items end up being removed.

unordered std vector stl-algorithm c++
1 Answers

Is there a built-in algorithm to do something like a std::remove but that does not preserve the order? I wish to do this since it is less work to just swap elements from the end of the vector into locations to be removed

std::partition() is an algorithm that will do what you are asking for. Instead of the value to remove, you will need to provide a predicate for the values to keep.

For example, given std::vector v;, instead of

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

you would write:

v.erase( std::partition(v.begin(), v.end(), [&](const auto& elem){return elem!=value;}), v.end() );

However, this is not necessarily more efficient than std::remove(). The problem is that std::remove() does not swap - instead, it only moves the elements, keeping the elements to be removed in an arbitrary moved-out state. This may be more efficient than swapping, especially if swapping vector elements is not cheap.

user_4595650
Related