Removing by index from a C++ vector using remove_if

Question

We can use remove_if in C++ to remove elements from a vector in linear time based on a predicate that operates on the elements.

bool condition(double d) {...} vector<double> data = ... std::remove_if (data.begin(), data.end(), condition);

What if my condition depends not on the values, but on the indices? In other words, if I wanted to remove all the odd-indexed elements, or some arbitrary index set, etc?

bool condition(int index) {//returns whether this index should be removed} vector<double> data = ... std::remove_if (data.begin(), data.end(), ???);

possible duplicate of Remove vector elements based on the index — user657267
– user657267, Commented Apr 17, 2014 at 0:44

keineahnung2345 · Accepted Answer · 2020-01-08 08:53:37Z

13

You can use pointer arithmetic to find the index of a specific element that std::remove_if passes to the predicate:

std::remove_if(data.begin(), data.end(), [&data](const double& d) { return (&d - &*data.begin()) % 2); });

Note that remove_if passes the result of dereferencing an iterator, and that's guaranteed to be a reference per Table 106 - Iterator requirements in the Standard.

edited Jan 8, 2020 at 8:53

keineahnung2345

2,7014 gold badges16 silver badges30 bronze badges

answered Apr 17, 2014 at 2:22

Tony Delroy

107k16 gold badges188 silver badges265 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

donnyton Over a year ago

Thanks. Can you explain why do you have &*data.begin() instead of just data.begin()?

Tony Delroy Over a year ago

@donnyton because begin() returns an iterator, but we want to compare it to the address of the parameter (i.e. a pointer), hence the &* dance....

D Drmmr Over a year ago

I don't think the standard guarantees this will work, because it assumes that the elements are not moved/swapped before the predicate is applied. The standard only guarantees that the predicate is applied exactly last - first times. AFAICT an implementation could move/swap elements before applying the predicate, which would be stupid, but in accordance with the Standard.

Tony Delroy Over a year ago

@DDrmmr: there's also "For purposes of determining the existence of data races, algorithms shall not modify objects referenced through an iterator argument unless the specification requires such modification." - that stipulation to minimise data races should also forbid needless movement/swapping (at least with other members of the container) prior to the application of the predicate.

Caleth Over a year ago

This only works for ContiguousIterators, whereas std::remove_if only needs ForwardIterator

|

jonas simple · Accepted Answer · 2014-09-17 01:19:44Z

I actually made an account only for this. Use awesomeyi answer. Is way cleaner.

int count = 0; auto final = std::remove_if (data.begin(), data.end(), [&count](const double d) { return (count++) % 2; });

The standard does say that the predicate is applied exactly last - first times. And remove_if works with ForwardIterators.

This implies that the predicate is applied only once in the same order they originally appear in the sequence.

Unless of course, the library is trolling you, by keeping internal copies of the ForwardIterator.

I'm pretty sure it's allowed for the implementation to do things like iterate keeping the addresses of elements, then apply the predicate in threads or using some parallel instructions, so I don't think this is particularly safe.

Caleth · Accepted Answer · 2020-02-23 18:00:06Z

2

An algorithm similar to std::remove_if, but passing indexes to it's predicate

template<class ForwardIt, class UnaryPredicate> ForwardIt remove_indexes_if(ForwardIt first, ForwardIt last, UnaryPredicate p) { ForwardIt dest = first; for(ForwardIt i = first; i != last; ++i) if (!p(std::distance(first, i))) *dest++ = std::move(*i); return dest; }

edited Feb 23, 2020 at 18:00

answered Jan 8, 2020 at 9:57

Caleth

66k2 gold badges53 silver badges101 bronze badges

1 Comment

Piotr Siupa Over a year ago

Definitely the right approach. No questionable hacks to make the standard implementation do something it isn't designed to do. No assuming internal working of unknown implementation which will backfire in some niche compiler. Sometimes the right approach is to just write your own function. We like to use the ones provided by the language because they are well optimized but unless you have something like vector of bools, you probably cannot optimize this much more. (But let's hope they'll add this one to the standard one day.)

yizzlez · Accepted Answer · 2014-04-17 00:39:15Z

Take advantage of the fact that lambas can capture variables. A quick example:

vector<double> data = {5, 3, 6, 7, 8}; int count = 0; auto final = std::remove_if (data.begin(), data.end(), [&](const double d) { bool b = false; if(count % 2) b = true; ++count; return b; }); for(auto beg = data.begin(); beg != final; ++beg) cout << *beg << endl;

Code will print: 5 6 8

This makes an assumption about the order in which remove_if applies the predicate, which is not warranted by the standard text.

Collectives™ on Stack Overflow

Removing by index from a C++ vector using remove_if

4 Answers 4

6 Comments

1 Comment

1 Comment

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

6 Comments

1 Comment

1 Comment

1 Comment

Linked

Related