std::remove_if - lambda, not removing anything from the collection

Question

Ok, I expect I've made a dumb mistake here. I have a list of DisplayDevice3d and each DisplayDevice3d contains a list of DisplayMode3d. I want to remove all items from the list of DisplayDevice3d that don't have any DisplayMode3d's. I'm trying to use a Lambda to do it, ie.:

    // If the device doesn't have any modes, remove it.

  std::remove_if(MyDisplayDevices.begin(), MyDisplayDevices.end(),
   [](DisplayDevice3d& device) 
   { 
    return device.Modes.size() == 0; 
   }
  ); 

Even though out of 6 DisplayMode3d's in MyDisplayDevices, only 1 has any DisplayMode3d's in its Modes collection, nothing is being removed from the list.

What numpty mistake have I made here?

Edit:

Ah ok, my mistake was I should be using MyDisplayDevices.remove_if instead of std::remove_if, however the answers below are correct for use of std::remove_if :p.

MyDisplayDevices.remove_if( [](DisplayDevice3d const & device) 
                            { 
                                return device.Modes.size() == 0; 
                            });

Chaparajos

If the container itself supports remove_if then by all means use it. I believe this is the case with std::list. For containers, that don't offer remove_if, you can use std::remove_if in combination with the container's erase member function. – Accroach

@Accroach In other words, rat poison – Nicholas

possible duplicate of Erasing elements from a vector – Nicholas

Answer 1

You need to call erase on the iterator returned from remove_if, It should look something like this:

auto new_end = std::remove_if(MyDisplayDevices.begin(), MyDisplayDevices.end(),
                              [](const DisplayDevice3d& device)
                              { return device.Modes.size() == 0; });

MyDisplayDevices.erase(new_end, MyDisplayDevices.end());

Vietnamese

Answer 2

remove_if doesn't remove anything from list it just moves them to end. You need to use it along with erase. See this question for more details.

Argybargy

So I erase from the iterator it returns to the end of the list? – Chaparajos

@Troyseph: The things that you want to keep are moved to the front (via assignment). Nothing is moved to the back. The stuff you don't need anymore is just there at the end and can be erased. – Accroach

Answer 3

remove_if doesn't perform resizing, but instead it just returns the iterator to the element that follows the last element not removed. This iterator can be passed to erase() to do the clean up.

Hew

Answer 4

As others have mentioned, there are ways to make it work. However my advice would be to completely avoid remove_if and stick to a standard iterator-based removal instead. The idiom below works both for list and vector and does not produce unexpected behavior.

for( vector<TYPE>::iterator iter = vec.begin() ; iter != vec.end() ; )
  if( iter->shouldRemove )
    iter = vec.erase( iter ) ; // advances iter
  else
    ++iter ; // don't remove

As the comments below mention, this method does have a higher cost than remove_if when more than 1 element is removed.

remove_if works by copying elements from further ahead in the vector, and overwriting vectors that should be removed from the vector by the one immediately in front of it. For example: remove_if called on a vector to remove all 0 elements:

0 1 1 0 1 0

results in:

1 1 1 0 1 0

Notice how the vector isn't correct yet. That is because remove_if returns an iterator to the last valid element... it doesn't automatically resize the vector. You still need to call v.erase() on the iterator returned from your call to remove_if.

An example is below

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

void print( vector<int> &v )
{
  for( int i : v )
    printf( "%d ", i );
  puts("");
}

int main()
{
  vector<int> v = { 0, 1, 1, 0, 1, 0 };
  print( v ); // 0 1 1 0 1 0
  vector<int>::iterator it = remove_if( v.begin(), v.end(), [](int i){ return i == 0; } );
  print( v ); // 1 1 1 0 1 0
  v.erase( it, v.end() ); // actually cut out values not wanted in vector
  print( v ); // 1 1 1 (correct)
}

Nicholas

Why would you recommend this method over remove_if()? Surely remove_if() doesn't produce "unexpected behavior" either (it's just poorly named =P). And std::remove_if() would provide more opportunities for the compiler to intelligently optimize, wouldn't it? Because it iterates from beginning to end, while guaranteeing to the compiler that no funny business is going on, unlike manually iterating. (i.e. the same optimization benefits range-for() has over regular for()) – Amazement

bobobobo: The problem is that your algorithm is slow for vector. Each erase will shift the remaining elements down by one. If you're erasing 50 elements out of 1000, that's ~50,000 moves, where you only needed ~1000 moves of the survivors to their final slots. – Implacable