CODEWITHSUNDEEP
c++c++11visual-studio-code
Pauete Galopa
Pauete Galopa

Reputation: 153

C++ - begin() returns the end() iterator with a non-empty list

As the question suggest, I'm having a very strange behavior with iterators and lists. So, the (class) problem asks for a function that erase all elements that meet a condition from a list and, when I tried to cover the case where I have a list where all elements are the same I found out that the last element persisted.

Here is the code:

void esborra_tots(list<Estudiant>& t, int x) {
    list<Estudiant>::iterator it;
    list<Estudiant>::iterator itend = t.end();

    for (it = t.begin(); it != t.end(); it++) {
        if ((*it).consultar_DNI() == x) {

            t.erase(it);
            if (t.empty()) return;
            else it = t.begin();
        }
    }
}

I've used itend just to see the value while debugging. Here is the session: See that the list *t* is not empty but t.begin() returns the same as t.end()

How is this possible? PD: I'm not searching for other approaches to the problem.

Upvotes: 1

Views: 439

Answers (2)

Asteroids With Wings
Asteroids With Wings

Reputation: 17454

It's because you're doing it++ (the loop post-action) after your it = t.begin().

Remove that, and stick an else it++ (though I prefer ++it) in your loop body; it needs to only happen when you don't do the erasure.

This is similar to the method for erasing from a map while iterating over it.

Taking a cue from that method, we can notice that your else it = t.begin() is wasteful: you're starting from the beginning of the loop every time, which increases the algorithmic complexity of your algorithm.

Instead, use the iterator returned by erase.

void esborra_tots(list<Estudiant>& t, int x) {
    list<Estudiant>::iterator it;
    list<Estudiant>::iterator itend = t.end();

    for (it = t.begin(); it != t.end(); ) {
        if ((*it).consultar_DNI() == x) {
            it = t.erase(it);
        }
        else {
            ++it;
        }
    }
}

Notice how we also no longer need to check the list for emptiness; if it's now empty, it will be t.end() and the loop will end anyway.

Currently, you're not using itend. You can't just swap it into the loop condition, for obvious reasons, but if you reset it when it gets invalidated then it could be worthwhile:

void esborra_tots(list<Estudiant>& t, int x) {
    for (auto it = t.begin(), end = t.end(); it != end; ) {
        if (it->consultar_DNI() == x) {
            it = t.erase(it);
            end = t.end();
        }
        else {
            ++it;
        }
    }
}

However, it may be clearer to just stick with your original code but remove the unused itend declaration.

Upvotes: 6

Vlad from Moscow
Vlad from Moscow

Reputation: 310990

The used approach in the function

void esborra_tots(list<Estudiant>& t, int x) {
    list<Estudiant>::iterator it;
    list<Estudiant>::iterator itend = t.end();

    for (it = t.begin(); it != t.end(); it++) {
        if ((*it).consultar_DNI() == x) {

            t.erase(it);
            if (t.empty()) return;
            else it = t.begin();
        }
    }
}

is invalid. The iterator becomes invalid after calling the method erase.

You could write the function like

void esborra_tots(list<Estudiant>& t, int x) {
    for ( auto it = t.begin(); it != t.end(); ) {
        if ((*it).consultar_DNI() == x) {

            it = t.erase(it);
        }
        else {
            ++it;
        } 
    }
}

But this is too complicated. The function will look much simpler if to use the method remove_if.

For example

void esborra_tots(list<Estudiant>& t, int x) {
    t.remove_if( [&x]( const auto &item ) { return item.consultar_DNI() == x; } );
}

Here is a demonstrative program.

#include <iostream>
#include <list>

int main() 
{
    std::list<int> list = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    for ( const auto &item : list ) std::cout << item << ' ';
    std::cout << '\n';

    list.remove_if( []( const auto &item ){ return item % 2 == 0; } );

    for ( const auto &item : list ) std::cout << item << ' ';
    std::cout << '\n';

    return 0;
}

Its output is

0 1 2 3 4 5 6 7 8 9 
1 3 5 7 9

Upvotes: 3

Related Questions