1

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?

Community
  • 1
  • 1
daj
  • 6,962
  • 9
  • 45
  • 79
  • 9
    Where do you see a double negative? – jalf Sep 05 '11 at 16:06
  • Check this out: http://en.wikipedia.org/wiki/Erase-remove_idiom Suggestion: get a copy of Scott Meyer's *Effective STL* – Antonio Pérez Sep 05 '11 at 16:16
  • What is a "double negative"? Do you mean a general/logical double negative or is this some software-design term I don't know. In the latter case what does it mean? And in the former case, strange question! – Christian Rau Sep 05 '11 at 16:29
  • see below - it was a misconception on my part. feel free to remove the question... – daj Sep 06 '11 at 04:22

3 Answers3

6

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.

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
  • I see, I think I actually misinterpreted the answer. Takes a while to understand all these C++ idioms. I like the wikipedia entry too : http://en.wikipedia.org/wiki/Erase-remove_idiom – daj Sep 05 '11 at 16:24
4

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

Mahesh
  • 34,573
  • 20
  • 89
  • 115
1

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.

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084