cpp vector erase by indices too slower than python

Question

I want to delete items in vector by indices in cpp code. However it is too slow

1. cpp version

long remove_cnt = 0;
for (auto &remove_idx : remove_index) {
    mylist.erase(mylist.begin() + (long) remove_idx - remove_cnt);
    remove_cnt++;
}

2. python version

new_mylist = [item for i, item in enumerate(mylist) if i not in remove_index]

I expect that cpp is faster than python. But my cpp code is too slower than python code. Are there other efficient code in cpp??

Answer 1

Your question is a good example of why a 1-1 translation between languages usually doesn't work.

To efficiently erase items from a vector you don't do it by index. Assuming you got your indices in python by evaluating some condition (a predicate). You can directly use this predicate in C++. Say you want to remove all ints > 4 then the code looks like this:

#include <algorithm>
#include <iostream>
#include <vector>

bool greater_then_4(const int value)
{
    return value > 4;
}


int main()
{
    std::vector<int> values{ 1, 2, 3, 4, 5, 6, 7, 8 };

    // https://en.cppreference.com/w/cpp/algorithm/remove
    // remove all values greater then 4. remove will actually move all those values till the end
    auto it = std::remove_if(values.begin(), values.end(), greater_then_4);

    // shrink the vector to only include the items not matching the predicate
    values.erase(it, values.end());

    for (const auto value : values)
    {
        std::cout << value << " ";
    }

    return 0;
}