Pass additional arguments to remove_if

Question

I would like to remove elements from a vector using remove_if function but limiting the erasing to N elements.

Example:

// predicate function that determines if a value is an odd number.
bool IsOdd (int i) {

  if (we deleted more than deleteLimit)
    return false;

  return ((i%2)==1);
}


void otherFunc(){
  int deleteLimit = 10;

  // remove odd numbers:                       
  std::vector<int>::iterator newEnd =
  std::remove_if (myints.begin(), myints.end(), IsOdd (how to pass deleteLimit?) );
}

I need that IsOdd predicate stores how many elements it has removed and how many we want to delete. The only way is to use a global variable? Like this:

int deleteLimit = 10;
int removedSoFar = 0;
bool IsOdd (int i) {

  if (deleteLimit < removedSoFar)
    return false;

  if (i%2==1) {
    removedSoFar++
    return true;
  }

  return false;

}
remove_if ...

Briard

You can also use myints.size() in some functor or lambda function to determine how many elements have been erased. – Trengganu

I'm not sure that predicates passed to remove_if are allowed to be stateful – Underwood

@Trengganu But std::remove_if doesn't remove elements, it only moves them to the end and you should then use erase to actually remove them from the container. – Bowens

Answer 1

The state telling "how many elements have been removed so far" should be defined outside of the function / the call to the algorithm. This is because a functor should not have a state which is modified when being called (this would be undefined behavior).

You should take a reference to this state (counter) in the constructor of the functor (or capture by reference in the lambda), so you can access and modify this counter. When this functor is now copied, it doesn't matter which one is called by the algorithm, since all of them now hold the reference to the same state.

Using functors (C++03):

class IsOdd {
    int deleteLimit;
    int & deletedSoFar;

public:
    IsOdd(int deleteLimit, int & deletedSoFar) :
        deleteLimit(deleteLimit), deletedSoFar(deletedSoFar)
    {}

    bool operator()(int i) const {
        if (deletedSoFar < deleteLimit && i % 2) {
            ++deletedSoFar;
            return true;
        }
        return false;
    }
};

int deletedSoFar = 0;
int deleteLimit = 10;
std::remove_if (myints.begin(), myints.end(), IsOdd(deleteLimit, deletedSoFar));

Using lambda (C++11):

int deletedSoFar = 0;
int deleteLimit = 10;
auto it = std::remove_if (myints.begin(), myints.end(), [deleteLimit,&deletedSoFar](int i){
    if (deletedSoFar < deleteLimit && i % 2) {
        ++deletedSoFar;
        return true;
    }
    return false;
});
myints.erase(it, myints.end());

Bowens

Yes the lambda example is the one that I will use. Similar to ForEver's answer, but he refused to add deletedSoFar as an argument. – Briard

It's worth noting that OP most probably needs erase/remove_if idiom, not just remove_if call. – Underwood

@Bowens I edited your answer. If possible, could you check if it was a valid edit? If not, my apologies and please make a rollback. – Obstruct

@Streppel Thank you for your effort. I see what your thought was: you thought the operator might not be const because it modifies a member. But that's not correct: it doesn't modify the member, but it accesses the int value in order to change that, which lives outside of the object, i.e. within the operator the object's content is not modified. That makes it possible to still have the operator be const. You can see an example here: ideone.com/hxmhhU As you can see at the bottom, the code compiles and gives the expected result. Thank you anyways :) – Bowens

@Streppel I wanted to add: lambdas in C++11 are implemented like that: they have a const operator(), unless you add the keyword mutable. Yet when capturing by reference you can modify the value within the lambda without adding that keyword, the reason is the same as I explained above: the value you capture a reference of, lives outside of the functor/lambda. And in case you wonder: with pointers it's the same story: you are allowed to change objects behind pointer-members within a const function, that's because the object you're modifying doesn't live within the object. – Bowens

@Bowens Oh, I got it. Thank you for your kind response. :-) – Obstruct

@Bowens I just made a final edit to add the missing parenthesis on bool operator() now. – Obstruct

@Streppel Oh I didn't see you also edited that one. Thanks for that :) – Bowens

Answer 2

Besides creating your own functor, you can pass a lambda expression:

auto deleteLimit = 25;
auto removedSoFar = 0;
auto it = remove_if (myints.begin(), 
                     myints.end(), 
                     [deleteLimit, &removedSoFar](int i)->bool 
                     { 
                       if ( (deletedSoFar < deleteLimit) && (i % 2)) {
                          ++deletedSoFar;
                          return true;
                       }
                       return false;
                      } );

// really remove the elements from the container
myints.erase(it, myints.end());

However, beware that stateful functors and std library algorithms are not always good mix. Here, calls to the lambda can have a side effect, so you have no guarantee over which elements in the sequence will be removed.

Note the final call to std::vector::erase. This is required to really remove the unwanted elements from the container. See the erase remove idiom.

Decomposed

to keep the count? something like [deleteLimit &removedSoFar]... ? Does removedSoFar keeps the values after each iteration ? Also in your example you are not increasing its value – Briard

@yes123 In principle, yes, to keep the count, capture by reference. However, note that calling algorithms such as std::remove_if with "stateful" functors is not a great idea. – Decomposed

Well, it is not "stateful" if you take a reference to a counter in the constructor of the functor. Which is basically equivalent to capturing by reference. – Bowens

@juanchopanza: how you are supposed to count the removes if you don't pass removedSoFar to the lambda? – Briard

@Bowens it is stateful in the sense that the outcome of the predicate depends on more than its inputs. You could get different results based on exactly the same input iterator range. – Decomposed

@yes123 I think it is not guaranteed to work as you expect it to. – Decomposed

@Decomposed Well, when a lambda captures by reference, its behavior is always defined by more than its inputs... – Bowens

@Bowens but the point is that the referred to variable is being modified inside of the lambda. And I don't think the standard guarantees that this algorithm will work as expected here. – Decomposed

@juanchopanza: which other efficient strategy do you suggest (without using the .erase inside an interation)? – Briard

@Decomposed It would be strange if the standard allows to capture by (non-const) reference and doesn't allow to modify the value. Or do we talk of different things here? – Bowens

@Bowens different things. We are talking of the guarantees the standard places on how algorithms work. For instance, remove_if could traverse the sequence in random order. – Decomposed

@yes123 I can't think of a nice way to do it. You could loop over the sequence, storing iterators to the elements you want to remove. Then remove them. This way you are fully in control of what gets removed. – Decomposed

@Decomposed Well, OP didn't request to erase first elements satisfying predicate, so even if sequence is traversed in different order, requirement of removing at most N elements satisfying predicate is still met :-) – Underwood

@TadeuszKopec sure, if the requirement is to remove any N elements, then it is fine, I agree. I edited my answer to mention this. – Decomposed

Answer 3

Use functor, structure with operator (), or use some bind features (std::bind/boost::bind).

bool isOdd(int current, int limit, int& count)
{
   if (count >= limit)
   {
      return false;
   }
   if (current % 2 == 1)
   {
      ++count;
      return true;
   }
   return false;
}

int count = 0, limit = 10;
vec.erase(std::remove_if(vec.begin(), vec.end(),
std::bind(&isOdd, _1, limit, std::ref(count)), vec.end());

And with functor

struct IsOdd : public std::unary_function<int, bool>
{
public:
   IsOdd(int l) : count(0), limit(l)
   {
   }
   bool operator () (int i)
   {
      if (count >= limit)
      {
         return false;
      }
      if (current % 2 == 1)
      {
         ++count;
         return true;
      }
      return false;
private:
   int count;
   int limit;
};

int limit = 10;
vec.erase(std::remove_if(vec.begin(), vec.end(),
isOdd(limit)), vec.end());

Trembly

You marked your operator() const but it modifies count. It should be non-const, but this means that copying the functor within the algorithm is dangerous. It would be better if you take a counter by reference in the functor and modify this instead. Your operator can then still be const if I'm not wrong. – Bowens

Answer 4

int initial_size = myints.size();
std::remove_if (myints.begin(), myints.end(), [myints.size(),limit,initial_size](int i)->bool{  
return ( ( initial_size-myints.size() )<limit ? i%2 : false) } );

Trengganu

Answer 5

The code in the voted up answer has a small mistake. There are missing parentheses just before the operator keyword. I couldn't make the edit as its less than six characters and I couldn't comment as my score is too low.

class IsOdd {
        int deleteLimit;
        int & deletedSoFar;

    public:
        IsOdd(int deleteLimit, int & deletedSoFar) :
            deleteLimit(deleteLimit), deletedSoFar(deletedSoFar)
        {}

        bool operator()(int i) const {
            if (deletedSoFar < deleteLimit && i % 2) {
                ++deletedSoFar;
                return true;
            }
            return false;
        }
    };

    int deletedSoFar = 0;
    int deleteLimit = 10;
    std::remove_if (myints.begin(), myints.end(), IsOdd(deleteLimit, deletedSoFar));

Someone