CODEWITHSUNDEEP
c++for-loopvectorsegmentation-faulterase
RuiQi
RuiQi

Reputation: 488

Erase elements in vector using for loop

How do I use a for loop to erase elements from a vector by its index ? I am getting a vector out of range error. I have a sample code below.

 vector<int> to_erase = {0, 1, 2}; 
 vector<int> data     = {3, 3, 3, 3};

 for(int i = 0; i < to_erase.size(); i++) {

    data.erase(data.begin() + to_erase[i]);
 }

I think it is because the size of my vector reduces through every iteration therefore it cannot access index 2.

Upvotes: 4

Views: 2376

Answers (4)

Konrad Rudolph
Konrad Rudolph

Reputation: 546153

You would normally employ the erase–remove idiom to delete multiple elements from a vector efficiently (erasing them one by one is generally less efficient, and, as you’ve seen, not always trivial). In its most general form, the idiom looks like this:

data.erase(remove_algorithm(begin(data), end(data)), end(data));

In your case, the remove_algorithm is based off indices in another vector, so we need to provide those as well:

data.erase(
    remove_indices(begin(data), end(data), begin(to_erase), end(to_erase)),
    end(data));

Unfortunately, such an algorithm isn’t contained in the standard library. However, it’s trivial to write yourself1:

template <typename It, typename It2>
auto remove_indices(It begin, It end, It2 idx_b, It2 idx_e) -> It {
    using idx_t = typename std::iterator_traits<It2>::value_type;
    std::sort(idx_b, idx_e, std::greater<idx_t>{});

    for (; idx_b != idx_e; ++idx_b) {
        auto pos = begin + *idx_b;
        std::move(std::next(pos), end--, pos);
    }
    return end;
}

Here, we first sort the indices to be removed from largest to smallest. Next, we loop over those indices. We then (maximally efficiently) move all elements between the current position (to be deleted) and the end of the vector forward by one. Subsequently, the end is decreased by one (to account for the fact that an element got deleted).

Live code

1 *Ahem* Once you’ve removed all the silly typos in your code.

Upvotes: 6

wesley.mesquita
wesley.mesquita

Reputation: 785

I think this is a bad design, because you will change the for loop invariant and will need a lot of workaround to make this happen. Anyway, if you really want to use a for loop, you MAY flag what you whant to delete and run a stl remove_if, something like:

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
using namespace std;

int main() {

    vector<int> to_erase = {0, 1, 2}; 
    vector<int> data     = {3, 3, 3, 3};

    cout << "Before:\n" ;
    for(int i=0; i<data.size(); i++)
        cout << i << "\t";
    cout << endl;   
    for(int i=0; i<data.size(); i++)
        cout << data[i] << "\t";
    cout << endl;

    for(int i = 0; i < to_erase.size(); i++) {
        //data.erase(data.begin() + to_erase[i]);
        data[i] = numeric_limits<int>::max();
    }

    data.erase(remove_if(data.begin(), 
                         data.end(), 
                         [](int i){return i==numeric_limits<int>::max();}), data.end());

    cout << "Next:\n" ;
    for(int i=0; i<data.size(); i++)
        cout << i << "\t";
    cout << endl;
    for(int i=0; i<data.size(); i++)
        cout << data[i] << "\t";

    return 0;
}

Upvotes: 0

Marco Giordano
Marco Giordano

Reputation: 610

Deleting a collection of elements meanwhile you iterate, is unsafe and probalby expensive. I would suggest that each element that meets your criteria gets swapped with an element at the end. (at the end because will be cheaper to erase from the end. You can keep track of how much back you came from the end of the vector (based on the number of swap), and break early our of the loop. Now based on how many elements you swapped you can do something like:

data.resize(data.size() - reverse_counter);

or 

int pos = data.size() - reverse_counter;
data.erease(data.begin()+pos, data.end();

It is sudo code just to explain the idea.

As mentioned in the reference, erase not at the end cause re-allocation, which is expensive. Something worth keep in mind: http://www.cplusplus.com/reference/vector/vector/erase/

Upvotes: 0

gsamaras
gsamaras

Reputation: 73444

I think it is because the size of my vector reduces through every iteration

Yes!

You could do it by keeping an extra variable, which counts the elements that are deleted, like this:

#include <iostream>
#include <vector>

using namespace std;

int main() {
        vector<int> to_erase = {0, 1, 2}; 
        vector<int> data     = {3, 3, 3, 3};

        int count_removed = 0;
        for(unsigned int i = 0; i < to_erase.size(); i++)
                data.erase(data.begin() + to_erase[i] - count_removed++);

        for(unsigned int i = 0; i < data.size(); ++i)
                        cout << data[i] << "\n";
        return 0;
}

Output:

3

I had the same problem when I first used std::erase(), good question, +1.

Upvotes: 0

Related Questions