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](http://stackoverflow.com/questions/8427691/remove-vector-elements-based-on-the-index) — user657267, Apr 17 '14 at 00:44

score 13 · Accepted Answer · edited Jan 08 '20 at 08:53

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 08 '20 at 08:53

keineahnung2345

2,635
4
13
28

answered Apr 17 '14 at 02:22

Tony Delroy

102,968
15
177
252

Thanks. Can you explain why do you have `&*data.begin()` instead of just `data.begin()`? – donnyton Apr 17 '14 at 18:17
@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.... – Tony Delroy Apr 17 '14 at 23:58
3

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. – D Drmmr May 26 '14 at 07:30
1

@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. – Tony Delroy May 26 '14 at 08:01
This only works for *ContiguousIterator*s, whereas `std::remove_if` only needs *ForwardIterator* – Caleth Jan 08 '20 at 09:52
@Caleth: that's a good point, but the question is very clearly about vectors. – Tony Delroy Feb 23 '20 at 13:55

score 11 · Answer 2 · answered Sep 17 '14 at 01:19

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. — Tony Delroy, May 27 '20 at 00:00

score 0 · Answer 3 · answered Apr 17 '14 at 00:39

0

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

answered Apr 17 '14 at 00:39

yizzlez

8,757
4
29
44

8

This makes an assumption about the order in which `remove_if` applies the predicate, which is not warranted by the standard text. – Benjamin Lindley Apr 17 '14 at 00:45

Caleth · Answer 4 · 2020-02-23T18:00:06.743

0

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 '20 at 18:00

answered Jan 08 '20 at 09:57

Caleth

52,200
2
44
75

Removing by index from a C++ vector using remove_if

4 Answers4

Linked