CODEWITHSUNDEEP
c++stleraseidioms
daj
daj

Reputation: 7183

removing elements by value in C++ - does the preferred idiom really consist of a double negative?

I came across this answer to the question of removing elements by value in C++:

C++ Erase vector element by value rather than by position?

Basically: 

vec.erase(std::remove(vec.begin(), vec.end(), valueToRemove), vec.end());

The answer makes sense, but isn't this bad style? The logic is consists of a double negative... is there a cleaner way to do this?

Upvotes: 1

Views: 361

Answers (3)

Kerrek SB
Kerrek SB

Reputation: 477070

Remember that there are different types of containers: Contiguous vs node-based, and sequential vs associative.

Node-based containers allow efficient erase/insert. Sequential containers organize elements by insertion order (i.e. position), while associative containers arrange them by (key) value.

All current associative containers (map/set/unordered) are node-based, and with them you can erase elements directly, and you should use the element-wise member erase function directly. Lists are node-based sequence containers, so you can erase individual elements efficiently, but finding an element by value takes linear time, which is why lists offer a member remove function. Only sequence containers (vector and deque) have no easy way to erase elements by value, and that's where the free remove algorithm comes in, which first rearranges the sequence to then allow the container's member erase to perform an efficient erasure at the end of the container.

Unlike the many generic aspects of the standard library which work without any knowledge of the underlying container, the copy/erase idiom is one of those things which require a bit of detail knowledge about the differences between the containers.

Upvotes: 1

Mahesh
Mahesh

Reputation: 34625

This isn't bad and in fact an efficient way of removing elements from a vector based on a condition in linear time. Watch this video from 35th minute. STL explanation for the Erase and Remove Idiom

Upvotes: 4

Ben Voigt
Ben Voigt

Reputation: 283684

Deleting an element from a collection consists of two steps:

  • Moving down all subsequent elements to fill in the holes created by matches
  • Marking the new end

With the C++ standard library, these are two separate functions, remove and erase, respectively.

One could certainly imagine an erase_if type of function which would be easier to use, but evidently the current code is considered good enough. Of course you can write your own remove_if.

Upvotes: 6

Related Questions