std::list.erase() seems to be rearranging the elements of the list

Question

Consider the following function

void removeOdd(list<int>& li)
{
    for(list<int>::iterator it=li.begin(); it!=li.end(); it++)
    {
        if((*it)%2) it = li.erase(it);
    }
}

From my understanding of lists, where the return value is an "iterator pointing to the element that followed the last element erased by the function call",

std::list.erase() documentation

the removeOdd() function should ignore the element after the element erased and carry on through the list.

However, when linked into this test script

#include <list>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;

void test()
{
    int a[9] = { 5, 2, 8, 9, 6, 7, 3, 4, 1 };
    list<int> x(a, a+9);  // construct x from the array
    assert(x.size() == 9 && x.front() == 5 && x.back() == 1);
    removeOdd(x);
    assert(x.size() == 4);
    vector<int> v(x.begin(), x.end());  // construct v from x
    sort(v.begin(), v.end());
    int expect[4] = { 2, 4, 6, 8 };
    for (int k = 0; k < 4; k++){
        assert(v[k] == expect[k]);
    }
}
int main()
{
    test();
    cout << "Passed" << endl;
}

it passes. Moreover, modifying removeOdd() to

void removeOdd(list<int>& li)
{
    for(list<int>::iterator it=li.begin(); it!=li.end(); it++)
    {
        if((*it)%2){
            cout << *it << " ";
            it = li.erase(it);
            cout << *it << endl;
        } 
        else cout << *it << endl;
    }
}

and running the entire script on my WSL instance (compiling with g++), the following output is produced:

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

Am I missing something or is the list iterator looping back into the list?

I tried to read documentation online about std::list.erase() and random access iterators, but still could not understand the behavior described above.

Answer 1

In removeOdd(), you are incrementing it on every loop iteration, even when you remove an item, which will cause you to skip the next item, or even increment out of bounds. You need to increment it only for items that you don't remove, eg:

void removeOdd(list<int>& li)
{
    for(list<int>::iterator it = li.begin(); it != li.end(); )
    {
        if (*it % 2)
            it = li.erase(it);
        else
            ++it:
    }
}

A better option is to use std::remove_if() with list::erase() instead of using a manual loop, eg:

void removeOdd(list<int>& li)
{
    li.erase(
        remove_if(li.begin(), li.end(),
                  [](int i){ return (i % 2) != 0; }
        ),
        li.end()
    );
}

In C++20 and later, you can use std::erase_if() instead, eg:

void removeOdd(list<int>& li)
{
    erase_if(li,
        [](int i){ return (i % 2) != 0; }
    );
}

UPDATE:

In your test() example, your original code does not actually work:

• it checks and removes 5 from the list
• it skips checking 2, leaving it in the list!
• it checks and keeps 8 in the list
• it checks and removes 9 from the list
• it skips checking 6, leaving it in the list!
• it checks and removes 7 from the list
• it skips checking 3, leaving it in the list!
• it checks and keeps 4 in the list
• it checks and removes 1 from the list
• IT SHOULD STOP HERE, BUT IT DOESN'T!!!!
• it skips checking 5, leaving it in the list!
• it checks and keeps 2 in the list
• it checks and keeps 8 in the list
• it checks and keeps 6 in the list
• it checks and removes 3 from the list
• it skips checking 4, leaving it in the list!

Online Demo

You removed the last item from the list, and then incremented it (which is now equal to the end iterator), thus going out of bounds of the list because it != li.end() is no longer valid, and thus your code exhibits undefined behavior.

So, simply by a fluke of UB, you ended up with a result of [2,8,6,4] (before sorting). You would have gotten [2,8,6,3,4] instead if the UB was not present.

Fixing removeOdd() as I described above solves the UB problem, and gives the expected result:

Online Demo