c++erase-remove-idiom

C++, fast removal of elements from vector by binary index


There are several posts focused on the fast removal of elements given by indices from a vector. This question represents a slightly modified version of the problem.

There is a vector of elements:

std::vector <double> numbers{ 100, 200, 300, 400, 500, 600 };

and the corresponding binary index:

std::vector<bool> idxs{ 0, 1, 0, 1, 0, 1 };   

What is the fastest method of removal of elements with the "zero indices" from the vector? It may contain millions of elements.

I tried experiments with remove_if(), but this is not correct:

numbers.erase(std::remove_if(numbers.begin(), numbers.end(), [](bool b)->bool
    {
        return b == 1;
    }), numbers.end());

Solution

  • Unfortunately there is no automatism for this. You simply have to implement a custom erase function yourself:

    auto widx = numbers.begin();
    for (auto ridx = numbers.cbegin(), auto bidx = idxs.cbegin();
         ridx != numbers.end;
         ++ridx, ++bidx) {
      if (*bidx) *widx++ = *ridx;
    }
    numbers.erase(widx, numbers.end());