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:

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

Mark Ingram · Answer 1 · 2013-08-02T09:30:08.047

14

I would re-write your 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.

edited Aug 02 '13 at 09:30

answered Oct 13 '08 at 08:20

Mark Ingram

71,849
51
176
230

You aren't incrementing the iterator in the first part of the if – 1800 INFORMATION Oct 13 '08 at 08:21
1

I am - iter = erase(iter). The erase function returns the new iterator after the one that's just been deleted. – Mark Ingram Oct 13 '08 at 08:24
Oh right never mind me. This doesn't work with certain types of containers, mind you – 1800 INFORMATION Oct 13 '08 at 08:25
True, but the OP mentioned that he was working with lists (which do have an erase function). – Mark Ingram Oct 13 '08 at 09:06

score 9 · Answer 2 · answered Oct 13 '08 at 08:17

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.

score 1 · Answer 3 · edited May 23 '17 at 12:02

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).

suc · Answer 4 · 2013-11-06T16:46:21.750

The root cause is "list.erase()" will change the iterator. The correct write for "for" loop:

   for (list<CMessage*>::iterator it=que.begin(); it!=que.end(); ++it)
   {
    if(m_type == (*it)->m_type)
    {
        delete *it;
        it=que.erase(it); //"list.erase()" will change the iterator!!!
        if(it==que.end()) break; //Check again!!!
        //still has side effect here. --it?
    }
   }

But it still has side effect, so Mark's while solution will be the best.

score 0 · Answer 5 · answered Oct 13 '08 at 08:19

0

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.

answered Oct 13 '08 at 08:19

Konrad Rudolph

530,221
131
937
1,214

It seems from http://www.sgi.com/tech/stl/Iterators.html that forward iterators are assignable. std::list's iterators are bidirectional iterators (http://www.sgi.com/tech/stl/List.html, http://www.sgi.com/tech/stl/ReversibleContainer.html), and are thus also forward iterators. :-) – C. K. Young Oct 13 '08 at 08:33
Hmm, is this what they mean by “multi-pass”? Because otherwise nothing is said about assignability *of the iterator* (as opposed to its value!). – Konrad Rudolph Oct 13 '08 at 09:59

score 0 · Answer 6 · answered Oct 13 '08 at 08:26

0

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...

answered Oct 13 '08 at 08:26

xtofl

40,723
12
105
192

Implementation inheritance, while not ideal, can be forgiveable if it's private inheritance only. :-) – C. K. Young Oct 13 '08 at 08:34

score 0 · Answer 7 · answered Oct 13 '08 at 09:32

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.

score 0 · Answer 8 · answered Oct 13 '08 at 09:56

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.

list iterator not incrementable

8 Answers8

Linked