How come my vector array won't output anything after I erase an element?-CodePudding

Recently I've started learning C , and everyday I do a C practice exercise to understand the language more. Today I was learning Vector Arrays and I hit a roadblock.

I'm trying to make a simple program that takes an array, puts it into a vector, then removes all the odd numbers. But for some reason when I erase an element from the vector, and output the modified vector, it doesn't output anything.

If somebody could guide me to the right direction on what I'm doing wrong, that would be great!

remove.cpp

#include <iostream>
#include <vector>

using namespace std;

class removeOddIntegers {
    public:

        void removeOdd(int numbs[]) {

            vector<int> removedOdds;

            for(int i = 0; i < 10;   i) {
                removedOdds.push_back(numbs[i]);
            }

            for(auto i = removedOdds.begin(); i != removedOdds.end();   i) {
                if(*i % 2 == 1) {
                    removedOdds.erase(removedOdds.begin()   *i);
                    std::cout << "Removed: " << *i << endl;
                }
            }

            for(auto i = removedOdds.begin(); i != removedOdds.end();   i) {
                std::cout << *i << endl; //doesn't output anything.
            }
 
        }

};

main.cpp

#include <iostream>
#include "remove.cpp"

using namespace std;

int main() {

    removeOddIntegers r;
    int numbers[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    r.removeOdd(numbers);

    return 0;
}

Now, I understand that I could just filter through the array, and only push_back the even numbers to the vector, and quite frankly, that works like a charm. But I want to understand why my method doesn't work. How come when I remove an element from the vector, it just fails to output anything?

Thanks in advance!

CodePudding user response：

There's a few things wrong, but they mostly boil down to the same fundamental issue. You are violating iterator guarantees of std::vector::erase:

Invalidates iterators and references at or after the point of the erase, including the end() iterator.

You do this both when dereferencing the deleted iterator to display your "removed" message, and also when calling i for the loop.

In addition, your call removedOdds.erase(removedOdds.begin() *i); is wrong, because it's using the actual value in the vector as an offset from the beginning. That assumption is completely wrong.

The proper way to erase an element at an iterator and retain a valid iterator is:

i = removedOdds.erase(i);

Here is your loop with minimum changes required to fix it:

for (auto i = removedOdds.begin(); i != removedOdds.end(); ) {
    if (*i % 2 == 1) {
        std::cout << "Removed: " << *i << endl;
        i = removedOdds.erase(i);
    } else {
          i;
    }
}

Notice how the iterator is advanced in the body of the loop now. You can do a thought experiment to think about why. Or you can try doing it the wrong way and use an input like { 1, 3, 5, 7, 9 } to demonstrate the problem.

This is still not the idiomatic way to remove elements from a vector. As you alluded to, elements should be swapped to the end of the vector. The reason for this is that std::vector::erase is a linear operation that must shuffle the entire remainder of the vector. If you do this multiple times, you essentially have O(N^2) time complexity.

The recommended approach is to use std::remove_if:

removedOdds.erase(removedOdds.begin(),
                  std::remove_if(removeOdds.begin(), removeOdds.end(),
                                 [](int n) { return n % 2 == 1; }));

CodePudding user response：

The flaw in the shown algorithm is more easily observed with a much simpler example:

        for(int i = 0; i < 2;   i) {
            removedOdds.push_back(numbs[i]);
        }

This initializes the vector with just two values: 0 and 1. This is small enough to be able to follow along in your head, as you mentally execute the shown code:

        for(auto i = removedOdds.begin(); i != removedOdds.end();   i) {

Nothing interesting will happen with the first value, 0, that gets iterated here. i increments the iterator to point to the value 1, then:

            if(*i % 2 == 1) {
                removedOdds.erase(removedOdds.begin()   *i);
                std::cout << "Removed: " << *i << endl;
            }

This time erase() removes 1 from the vector. But that's what i is also pointing to, of course. Then, if you look in your C reference, you will discover that std::vector::erase:

invalidates iterators and references at or after the point of the erase, including the end() iterator.

i is now "at the point of the erase", therefore, i is no longer a valid iterator, any more. Any subsequent use of i becomes undefined behavior.

And, i immediately gets used, namely incremented in the for loop iteration expression. That's your undefined behavior.

With the original vector containing values 0 through 9: if you use your debugger it will show all sorts of interesting kinds of undefined behavior. You can use your debugger to see if the shown code ever manages to survive when it encounters a higher odd value, like 7 or 9. If it does, at that point this vector will obviously be much, much smaller, but removedOdds.erase(removedOdds.begin() *i); will now attempt to remove the 7th or the 9th value in a vector that's about half its size now, a completely non-existent value in the vector, with much hilarity ensuing.

To summarize: your "method doesn't work" because the algorithm is fundamentally flawed in multiple ways, and the reason you get "no output" is because the program crashes.