Erasing multiple objects from a std::vector?

While this answer by Peter G. in variant one (the swap-and-pop technique) is the fastest when you do not need to preserve the order, here is the unmentioned alternative which maintains the order.

With C++17 and C++20 the removal of multiple elements from a vector is possible with standard algorithms. The run time is O(N * Log(N)) due to std::stable_partition. There are no external helper arrays, no excessive copying, everything is done inplace. Code is a "one-liner":

template <class T>
inline void erase_selected(std::vector<T>& v, const std::vector<int>& selection)
{
    v.resize(std::distance(
        v.begin(),
        std::stable_partition(v.begin(), v.end(),
             [&selection, &v](const T& item) {
                  return !std::binary_search(
                      selection.begin(),
                      selection.end(),
                      static_cast<int>(static_cast<const T*>(&item) - &v[0]));
        })));
}

The code above assumes that selection vector is sorted (if it is not the case, std::sort over it does the job, obviously).

To break this down, let us declare a number of temporaries:

// We need an explicit item index of an element
// to see if it should be in the output or not
int itemIndex = 0;
// The checker lambda returns `true` if the element is in `selection`
auto filter = [&itemIndex, &sorted_sel](const T& item) {
    return !std::binary_search(
                      selection.begin(),
                      selection.end(),
                      itemIndex++);
};

This checker lambda is then fed to std::stable_partition algorithm which is guaranteed to call this lambda only once for each element in the original (unpermuted !) array v.

auto end_of_selected = std::stable_partition(
                           v.begin(),
                           v.end(),
                           filter);

The end_of_selected iterator points right after the last element which should remain in the output array, so we now can resize v down. To calculate the number of elements we use the std::distance to get size_t from two iterators.

v.resize(std::distance(v.begin(), end_of_selected));

This is different from the code at the top (it uses itemIndex to keep track of the array element). To get rid of the itemIndex, we capture the reference to source array v and use pointer arithmetic to calculate itemIndex internally.

Over the years (on this and other similar sites) multiple solutions have been proposed, but usually they employ multiple "raw loops" with conditions and some erase/insert/push_back calls. The idea behind stable_partition is explained beautifully in this talk by Sean Parent.

This link provides a similar solution (and it does not assume that selection is sorted - std::find_if instead of std::binary_search is used), but it also employs a helper (incremented) variable which disables the possibility to parallelize processing on larger arrays.

Starting from C++17, there is a new first argument to std::stable_partition (the ExecutionPolicy) which allows auto-parallelization of the algorithm, further reducing the run-time for big arrays. To make yourself believe this parallelization actually works, there is another talk by Hartmut Kaiser explaining the internals.

You can use this method, if the order of the remaining elements doesn't matter

#include <iostream> 
#include <vector>

using namespace std;
int main()
{
    vector< int> vec;
    vec.push_back(1);
    vec.push_back(-6);
    vec.push_back(3);
    vec.push_back(4);
    vec.push_back(7);
    vec.push_back(9);
    vec.push_back(14);
    vec.push_back(25);
    cout << "The elements befor " << endl;
    for(int i = 0; i < vec.size(); i++) cout << vec[i] <<endl;
    vector< bool> toDeleted;
    int YesOrNo = 0;
    for(int i = 0; i<vec.size(); i++)
    {
        
        cout<<"You need to delete this element? "<<vec[i]<<", if yes enter 1 else enter 0"<<endl;
        cin>>YesOrNo;
        if(YesOrNo)
            toDeleted.push_back(true);
        else
            toDeleted.push_back(false);
    }
    //Deleting, beginning from the last element to the first one
    for(int i = toDeleted.size()-1; i>=0; i--)
    {
        if(toDeleted[i])
        {
            vec[i] = vec.back();
            vec.pop_back();
        }
    }
    cout << "The elements after" << endl;
    for(int i = 0; i < vec.size(); i++) cout << vec[i] <<endl;
    return 0;
}

This is non-trival because as you delete elements from the vector, the indexes change.

[0] hi
[1] you
[2] foo

>> delete [1]
[0] hi
[1] foo

If you keep a counter of times you delete an element and if you have a list of indexes you want to delete in sorted order then:

int counter = 0;
for (int k : IndexesToDelete) {
  events.erase(events.begin()+ k + counter);
  counter -= 1;
}

Here's an elegant solution in case you want to preserve the indices, the idea is to replace the values you want to delete with a special value that is guaranteed not be used anywhere, and then at the very end, you perform the erase itself:

std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};

// marking 3 elements to be deleted
vec[2] = std::numeric_limits<int>::lowest();
vec[5] = std::numeric_limits<int>::lowest();
vec[3] = std::numeric_limits<int>::lowest();

// erase
vec.erase(std::remove(vec.begin(), vec.end(), std::numeric_limits<int>::lowest()), vec.end());

// print values => 1 2 5 7 8 9
for (const auto& value : vec) std::cout << ' ' << value;
std::cout << std::endl;

It's very quick if you delete a lot of elements because the deletion itself is happening only once. Items can also be deleted in any order that way.

If you use a a struct instead of an int, then you can still mark an element of that struct, for ex dead=true and then use remove_if instead of remove =>

struct MyObj
{
    int  x;
    bool dead = false;
};

std::vector<MyObj> objs = {{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}};
objs[2].dead = true;
objs[5].dead = true;
objs[3].dead = true;
objs.erase(std::remove_if(objs.begin(), objs.end(), [](const MyObj& obj) { return obj.dead; }), objs.end());

// print values => 1 2 5 7 8 9
for (const auto& obj : objs) std::cout << ' ' << obj.x;
std::cout << std::endl;

This one is a bit slower, around 80% the speed of the remove.