list iterator not incrementable

Question

I have an old project that was built using visual studio 2003 and I recompiled it with vs2005 recently. However, during runtime, I get the following error:

list iterator not incrementable

I traced the program to this function:

void InputQueue::update()
{
    list<PCB>::iterator iter;
    list<PCB>::iterator iterTemp;
    for(iter = begin(); iter != end(); iter++)
    {
     if(iter->arrivalTime == 0)
     {   
      ReadyQueue::getInstance()->add(*iter);
      iterTemp = iter;
      iter++;
      erase(iterTemp);
     }
    }
}

I'm not a C++ expert and this is as far as the VS debugger got me. Could somebody explain to me what the problem is?

Thanks

Answer 1

Notice that if iter->arrivalTime == 0, then the list iterator gets incremented twice: once before element removal, and once again at the end of the loop.

If the item to be removed is the last item in the list, this will obviously not work correctly. I dare say that it never did work correctly even in VS2003, but VS2005 alerts you about it better. :-)

Remember, it's undefined behaviour to iterate past end(). Absolutely anything can happen, such as program crash, or (in this case) an error message.

Answer 2

I'm just going to elide a few lines of your code to show where the problem lies:

    for(iter = begin(); iter != end(); iter++) // ***
    {
        if(iter->arrivalTime == 0)
        {                       

                iter++; // ***

        }
    }

On the two lines marked ***, you are incrementing the iterator. The problem is that on the second of the two lines, you aren't checking to see that you haven't gone to the end of the container. Effectively, if you get into the inner loop, you are incrementing twice, but only checking if you are able to increment once.

One solution is to check whether you are at end() before doing the second increment, but it looks to me like you are trying to preform the same operation as I was in my question a while ago to do with filtering items from a container (a map in that case, but the same applies for most STL containers).

Answer 3

I beliebe Chris is right. However, another problem might stem from the fact that you assign to the iterator. – Are list iterators guaranteed to be assignable? Without looking at the standard, I don't think so because assignability is nowhere mentioned in the SGI documentation of iterators.

Answer 4

I would re-write you loop to be like the following:

while (iter != end())
{
  if(iter->arrivalTime == 0)
  {
    ReadyQueue::getInstance()->add(*iter);
    iter = erase(iter);
  }
  else
  {
    ++iter;
  }
}

Now you are correctly looping through the list checking every index.

Answer 5

This is but a sidenote, but an important one.

I guess you inherit from a std::ist<PCB>. I must say: inheriting to reuse functionality hasn't often turned out well for me. But since you're also 'inheriting' the project, there's nothing much to do about it...

Answer 6

I see the problem. I modified my for loop to Mark's while loop but now I get a "list iterator incompatible" error.

Answer 7

If you getting "list iterator incompatible" it's probably because inside your "ReadyQueue::getInstance()->add(*iter);" you are changing something in *iter that is making the hash algorithm returns a different value for erase than it did during the insert.

Answer 8

May I suggest a simpler algorithm?

The free function std::remove_if can be used to partition your list in 2, elements that match or don't match the predicate (i.e. arrivalTime==0). It returns the iterator seperating the ranges. You can then call ReadyQueue::getInstance()->add(subrange_begin, subrange_end) (you do have that overload, right?) and erase the subrange afterwards.

Just a case where you can use STL algorithms instead of writing your own loops.