How to remove odd positions from a list?

Question

#include<iostream>
#include<list>
using namespace std;

void compute(int num)
{
list<int> L;
list<int>::iterator i;
list<int>::iterator i2;
int p;
cout<<"Enter the number of numbers\n";
cin>>p;
int a;
for(int k=1;k<=p;k++)
{
    cin>>a;
    L.push_back(k);
}
cout<<endl;
for(i=L.begin() ; i!=L.end() ; ++i)
{
    cout<<*i<<endl;
}

long int k=1;

for(i=L.begin() ; i!=L.end() ; ++i )
{
    if(k%2!=0) //This is where I try and delete values in odd positions
    {
        i2=L.erase(i);
    }
    k++;
}

for(i=L.begin() ; i!=L.end() ; ++i )
{
    cout<<*i<<endl;
}

}

int main()
{
//  int testcases, sailors;
//cin>>testcases;

//for(int i=1 ; i<=testcases ; i++)
{
//  cin>>sailors;
}
//for(int i=1;i<=testcases;i++)
{
//  int num;
    //cin>>num;
    //compute(num);
}
compute(0);
return 0;

}

I am trying to erase elements using L.erase() function in Lists. But I get an error saying "Debug assertion failed! ......Expression:list iterator not incrementable" but we CAN increment iterator right?

Answer 1

erase invalidates the iterator that was passed in as parameter - since the element at the position the iterator was pointing to was just erased! And on that same iterator, an increment is attempted in the next for loop in your code! That's why it fails.

However, erase it will return an iterator pointing to the new position, which we can use; a loop where you erase something from an STL container should therefore look something like the following; I show it with the type you use, list, but you could just as well use e.g. vector:

list<int> L;
// ...
list<int>::iterator it=L.begin();
while (it!=L.end())
{
    if(eraseCondition)
    {
        it=L.erase(it);
    }
    else
    {
        ++it;
    }
}

Or, if possible, it's even better to use std::remove_if:

container.erase(std::remove_if(L.begin(), L.end(), predicate), L.end());

In your case that will be hard - if not impossible - to use since the predicate would need state information (the information whether the index is odd or even). So I'd recommend going with a loop structure as mentioned above; just keep in mind the remove_if for the general case of removing all elements where a certain predicate returns true!

Answer 2

Adding to what wOOte said, you may want to used a reverse iterator to get around the issue.

Answer 3

Technically not in this case.

When you use erase() you delete the node that was pointed to, so you actually invalidate the iterator you were on. So when you increment it it's undefined behavior.

It might be best to create a second list with just the iterators to the positions you'd like to delete, and you can cycle through those and call erase afterward. You wouldn't be erasing the iterators from the second list, so it'd work.

Something like this:

List<IteratorType> deleteList;

//Populate deleteList with every other element from original list.

for (List<IteratorType>::iterator iter = deleteList.begin();
         iter !=deleteList.end; ++iter)
{
    originalList.erase(*iter);
}

Answer 4

The iterator i is invalidated by the call to erase; however, in the next iteration of the for loop, you try to increment it - this is invalid.

Try

for(i=L.begin() ; i!=L.end() ; )
{
    if(k%2!=0) //This is where I try and delete values in odd positions
    {
        i=L.erase(i);
    } else {
        ++i;
    }
    k++;
}

instead - only increment the iterator if you don't erase (erase basically "advances" the iterator because it yields an iterator to the element following the one you erased).

You can actually exploit this behaviour of erase to write your function without requiring k:

i = L.begin();
while ( i != L.end() ) {
    i = L.erase( i );      // Delete one
    if ( i != L.end() ) {  // Skip next, if there's an element
      ++i;
    }
}

So you delete the first element, skip the second, delete the third, and so on.