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(), ???);

Novotny

possible duplicate of Remove vector elements based on the index – Lorenalorene

Answer 1

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.

Keynote

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

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

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. – Journalize

@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. – Keynote

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

@Caleth: that's a good point, but the question is very clearly about vectors. – Keynote

Answer 2

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.

Kinser

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. – Keynote

Answer 3

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;
}

Polychaete

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.) – Sensualist

Answer 4

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

Violinist

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