Problem with having 2 iterators on STL list

[MichelC]

Hello,

I'm having very weird bug with a STL list. I boiled down my source code to the function inserted below. Basically, I populate a STL list with a number of items. Then I initialize 2 iterators to the list's "begin()" and increment one of them through "++". The VS2005 debugger enters an infinite loop in STL code.

bool Test()
{
   list<ITEM>::iterator iter1;
   list<ITEM> itemList;
   list<ITEM>::iterator iter2 = itemList.begin();
   int itemIndex;

   // Populate the list with dummy contents
   for( itemIndex=0; itemIndex<5; itemIndex++)
   {
      ITEM something;
      itemList.push_back(something);
   }
  
   iter2 = itemList.begin();
   iter1 = itemList.begin();
   iter1++; // BUG (infinite loop)

   return true;
}

Note that the iter2 iterator is first initialized to the list's "begin()" before the list is actually populated. If I remove that initialization, everything works fine.

That brings 2 questions:
1- Is there a law against initializing a STL list iterator to an empty list's "begin()"?
2- Is there a law against having 2 iterators into the same STL list?

[jsmith]

no and no.

so the function never returns?

did you add a cout on line 18 (with a flush)? what about after line 12?

[MichelC]

That's right. The application hangs in the infinite loop. It would never reach line 18; and on line 12 I can see the itemList getting correctly populated in the VS2005 debugger's watch window.

In any case I copy-pasted below the section of the STL code where the infinite loop occurs. It is taken from a file named "xutility". The _Pnext variable is getting assigned the value of its _Mynextiter member which is equal to _Pnext itself. It seems there is no validation to prevent this from evolving into an infinite loop. Maybe it would be a minor modification that could be added to the STL implementation.

class _Iterator_base
	{	// base of all iterators

//(..)

	private:
	void __CLR_OR_THIS_CALL _Clean_up_iter_debug()
		{	// cut ties with parent, if any
		_Lockit _Lock(_LOCK_DEBUG);
		_Iterator_base **_Pnext =
			(_Iterator_base **)&_Mycont->_Myfirstiter;

// INFINITE LOOP HERE, _Pnext IS EQUAL TO _Mynextiter
		while (*_Pnext != 0 && *_Pnext != this)   
			_Pnext = &(*_Pnext)->_Mynextiter;  

[guestgulkan]

I still can't see how the original posted code could create an infinite loop.

[Robertlzw]

I tested it with the following code using Visual Studio 2008 Professional. No bug is found:

#include <iostream>
#include <list>

using namespace std;

class ITEM
{
public:
	ITEM():m_x(-1) {}					
	ITEM(int x) : m_x(x) {}
	int get() const { return m_x;}
	~ITEM() {}
private:
	int m_x;
};
ostream& operator<<(ostream& os, ITEM& it)
{
		os << it.get() << endl;
		return os;
}

int main()
{
   list<ITEM>::iterator iter1;
   list<ITEM> itemList;
   list<ITEM>::iterator iter2 = itemList.begin();
   int itemIndex;

   // Populate the list with dummy contents
   for( itemIndex=0; itemIndex<5; itemIndex++)
   {
      ITEM something(itemIndex);
      itemList.push_back(something);
   }
  
   iter2 = itemList.begin();
   iter1 = itemList.begin();
   cout << *iter1 << endl; // print out: 0
   iter1++; // NO BUG FOUND
   cout << *iter1 << endl; // print out: 1

   itemList.clear();
   return 0;
}

[MichelC]

Thanks for the feedback everyone, it is highly appreciated! Basically I understand that my code is OK (woo-hoo!). Still I see the problem (d'oh!) but now I can point a finger at the calling function.

Is there a way to submit requests for changes in STL? Who's responsible for STL anyway? When I look at the source code for _Clean_up_iter_debug() and how it behaves, I see that one of the items in the list being scanned has its 'next' pointer pointing to itself (hence the infinite loop I encounter). It would be fairly easy to detect that kind of situation.

[jsmith]

Check the copyright on the STL headers provided by your compiler.

[MichelC]

Found the problem: _HAS_ITERATOR_DEBUGGING (insert Darth Vader breathing sound here)

The 'STL iterator debugging' has become available starting with Visual Studio 2005. It can be disabled by adding:
#define _HAS_ITERATOR_DEBUGGING 0
but the default value is 1.

All statically-linked libraries must have same definition. The calling library had a different value than my library which resulted in an infinite loop problem at the STL level.