std::vector removing elements which fulfill some conditions

Question

As the title says I want to remove/merge objects in a vector which fulfill specific conditions. I mean I know how to remove integers from a vector which have the value 99 for instance.

The remove idiom by Scott Meyers:

vector<int> v;
v.erase(remove(v.begin(), v.end(), 99), v.end());

But suppose if have a vector of objects which contains a delay member variable. And now I want to eliminate all objects which delays differs only less than a specific threshold and want to combine/merge them to one object.

The result of the process should be a vector of objects where the difference of all delays should be at least the specified threshold.

[`remove_if`](http://en.cppreference.com/w/cpp/algorithm/remove) — BoBTFish, Jun 24 '13 at 08:17
*"I want to eliminate all objects which delays differs only less than a specific threshold"* -- Could you elaborate on this? Differs from what? Other elements in the container? Nearby elements? Some specific value? — Benjamin Lindley, Jun 24 '13 at 08:20
possible duplicate of [Removing elements from C++ std::vector](http://stackoverflow.com/questions/2642509/removing-elements-from-c-stdvector) — stijn, Jun 24 '13 at 08:27
Suppose the vector contains some objects, object `o1` and object `o2` which have a delay of `o1.delay=10` and `o2.delay=50`, thus they have a relative delay of 40. This delay difference is too small to be taken into account, thus I want to consider `o1` and `o2` as one object instead of two separate objects. — antibus, Jun 24 '13 at 08:30
@Christoph if you want to take more than one value into account, `remove_if` might be hard to use — Bartek Banachewicz, Jun 24 '13 at 08:35
@Christoph: And how would you want to handle this situation: `diff(o1,o2) < threshold` and `diff(o2,o3) < threshold` but `diff(o1,o3) > threshold` — Benjamin Lindley, Jun 24 '13 at 08:38
@Bartek Banachewicz: Yes, this is the case. I want to compare on delay with all other. — antibus, Jun 24 '13 at 08:38
@Benjamin Lindley: You're right. This could lead to a degeneration of the vector to one object at worst. Maybe I have to think of this a little more. — antibus, Jun 24 '13 at 08:40

Bartek Banachewicz · Accepted Answer · 2013-06-24T08:23:51.397

59

std::remove_if comes to the rescue!

99 would be replaced by UnaryPredicate that would filter your delays, which I am going to use a lambda function for.

And here's the example:

v.erase(std::remove_if(
    v.begin(), v.end(),
    [](const int& x) { 
        return x > 10; // put your condition here
    }), v.end());

edited Jun 24 '13 at 08:23

answered Jun 24 '13 at 08:18

Bartek Banachewicz

38,596
7
91
135

The condition can not be variable. For example putting max instead of 10. – user1436187 Oct 11 '15 at 14:44
@user1436187 uh, why not? – Bartek Banachewicz Oct 11 '15 at 22:04
It would be great if you explain how can we do something like this: `v.erase(std::remove_if( v.begin(), v.end(), [](const int& x, int max) { return x > max; // put your condition here }), v.end());` – user1436187 Oct 12 '15 at 05:34
5

@user1436187 it must come from outer scope. Define before the `v.erase()` call and pass to lambda inside `[]`. – Bartek Banachewicz Oct 12 '15 at 10:15

Drew Dormann · Answer 2 · 2023-07-25T17:16:51.777

18

C++20 introduces std::erase_if for the very purpose of the objective in this question.

It simplifies the erase-remove idiom for std::vector, and is also implemented for other standard containers, such as std::map or std::string.

Given the example in the current accepted answer:

v.erase(std::remove_if(
    v.begin(), v.end(),
    [](const int& x) { 
        return x > 10; // put your condition here
    }), v.end());

You can now make the same logic more readable as:

std::erase_if( v, [](int x){return x > 10;} );
//   container ^  ^ predicate

edited Jul 25 '23 at 17:16

answered Aug 13 '21 at 20:15

Drew Dormann

59,987
13
123
180

2

Worth mentioning that the Standard Library also introduces appropriate versions of this function for `basic_string`, `map` etc. This should be the default choice today. – Bartek Banachewicz Oct 07 '21 at 12:23

Zan Lynx · Answer 3 · 2019-12-14T20:48:00.997

An old question but a popular reference so I'm adding another option to this.

The remove_if function preserves the order of the sequence. That can be very important. However, it can also be a complete waste of time if your program doesn't care about the order.

In order to preserve the order, remove_if needs to shift the elements down to fill in the removed elements.

Let me introduce partition. Instead of shifting elements to fill in gaps, it moves an element from the end into the gap. This does not preserve the order, but it can be much faster, especially in a large array.

Here is a sample program:

#include <algorithm>
#include <chrono>
#include <iostream>
#include <iterator>
#include <memory>
#include <string>
#include <vector>

using namespace std;

struct Event {
  chrono::nanoseconds delay;
  string name;

  friend ostream &operator<<(ostream &os, const Event &e) {
    return os << "{ \"delay\": " << e.delay.count() << ", \"name\": \""
              << e.name << "\" }";
  }
};

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &container) {
  bool comma = false;
  os << "[ ";
  for (const auto &x : container) {
    if (comma)
      os << ", ";
    os << x;
    comma = true;
  }
  os << " ]";
  return os;
}

int main() {
  vector<Event> iv = {
      {0ms, "e1"},  {10ms, "e2"}, {11ms, "e3"}, {0ms, "e4"},
      {12ms, "e5"}, {8ms, "e6"},  {13ms, "e7"},
  };

  iv.erase(partition(begin(iv), end(iv),
                     [](const auto &x) { return x.delay > 0ns; }),
           end(iv));
  cout << iv << '\n';
  return 0;
}

I compile it on Linux with GCC like so:
g++ -Wall -W -pedantic -g -O3 -std=c++17 partition-test.cpp -o partition-test

And run it:
./partition-test [ { "delay": 13000000, "name": "e7" }, { "delay": 10000000, "name": "e2" }, { "delay": 11000000, "name": "e3" }, { "delay": 8000000, "name": "e6" }, { "delay": 12000000, "name": "e5" } ]

Let me also introduce a fun command line tool named jq aka JSON Query:

./partition-test | jq 
[
  {
    "delay": 13000000,
    "name": "e7"
  },
  {
    "delay": 10000000,
    "name": "e2"
  },
  {
    "delay": 11000000,
    "name": "e3"
  },
  {
    "delay": 8000000,
    "name": "e6"
  },
  {
    "delay": 12000000,
    "name": "e5"
  }
]

Which is a pretty great JSON formatter also. Makes it easy to read.

Now you can see that "e7" and "e6" filled in the erased Event objects with delay == 0. And the array is no longer in order.

sasha.sochka · Answer 4 · 2013-06-24T08:46:56.987

3

Using predicate function (idiomatic way in C++11):

v.erase(remove_if(
            v.begin(), v.end(), bind(greater<int>(), _1, 99)),
        v.end());

edited Jun 24 '13 at 08:46

answered Jun 24 '13 at 08:37

sasha.sochka

14,395
10
44
68

3

funky `bind`, +1 for that alone. – Bartek Banachewicz Jun 24 '13 at 08:39
1

Personally, I find lambdas make `bind` mostly obsolete. They're much more generally useful, and even in simple cases like this where `bind` would work, a lambda is much simpler both to understand, and to remember the syntax for. – Benjamin Lindley Jun 24 '13 at 08:49
1

@BenjaminLindley Agreed. On the other hand, if you don't have C++11, `boost::bind` is still useful. – James Kanze Jun 24 '13 at 08:51

std::vector removing elements which fulfill some conditions

4 Answers4

Linked

Related