Sign in to follow this  
rene_g

std::list::reverse_iterator starts out of bounds?

Recommended Posts

Hello all! I was actually wondering if I should post this question in the Beginners section as it seems it's a simple problem, however I ultimately decided not to. In a class of mine, I have the following declarations:
typedef list<Entity*> EntityList;
EntityList m_children;



In one of my member functions of the same class, I have this code:
	void EntityImpl::DrawChildren()
	{
		EntityList::iterator begin = m_children.begin(); // For debug purposes
		EntityList::reverse_iterator iter = m_children.rbegin();
		EntityList::reverse_iterator rend = m_children.rend(); // For debug purposes
		for (; iter != m_children.rend(); ++iter)
		{
			(*iter)->OnDraw();
		}
	}



If I try to run this code, really bad things happen. My computer has crashed with BSOD about 4 times now, with different error codes (BAD_POOL_CALLER and 2 other ones I can't remember). (Before anyone starts suggesting I check my RAM, harddrive and so on, let me assure you that's not the problem. My program is the problem. I have debugged a complete dump of my system with WinDBG, and the problem is a dereferenced pointer, that's invalid, inside my program. And that's exactly what is happening in the member function posted above) Okay, if I debug my member function above, the variable "iter" is assigned the result of m_children.rbegin(). And this function returns an invalid pointer. (In debug mode, the iterator address returned is 0xcdcdcdcd) And basically, this is what I don't get. Is this really supposed to happen? Should I get an invalid pointer from this function? When I'm debugging this, m_children has 1 item in the list. For debug purposes I added the "rend" variable which is assigned the m_children.rend() result. This function returns a VALID pointer, which is the 1 and only item in the list. The variable "begin" is also a valid pointer, pointing to the same element as "rend". So when my program runs, it starts out with an invalid pointer, dereferences it and the program (And computer) crashes. I have been trying to figure out if I'm supposed to increment the pointer before I use it, but I can't believe that's the case, as I haven't been able to find any documentation that says that. Besides, I don't think that would be very intuitive... but I might be wrong... So, alot of text and explainations. Does anyone have the silver bullet for me? What am I doing wrong here? Thanks alot for any help!

Share this post


Link to post
Share on other sites
I haven't used C++ in a few years so forgive me if I'm wrong but shouldn't rend() return a pointer to one before the begining and then rbegin() return a pointer to the end of the container?

James

PS: Just did a quick Google - try running the sample here and see what happens.

Share this post


Link to post
Share on other sites
Hi,

I tried your code and it works! :o) But yes there is a problem in Visual studio that reverse iterators show their *real* value and not *logical* one. Quick look into source code of std::list reveals that your rbegin "iter" is indeed pointing behind the list, however when you dereference it this operation is done

return (*--_Tmp);

thus giving you the right value.

You can check it by reading the iterator dereference before OnDraw call like

Entity* e = *iter;






Share this post


Link to post
Share on other sites
Try with while:

while(iter != m_children.rend())
{
if(*iter) (*iter)->OnDraw();
++iter;
}

also it can be some difference in debug/release version. Not always the same.
0xcdcdcdcd is "null pointer" for debugging purposes. Also debug mode will not always throw errors, but release will.

It is possible that somewhere in your code you are adding to entity list entity with null pointer. You will get into array one child but calling
(*iter)->OnDraw(); // NULL->OnDraw();
will crash the program.
Thats why there is if...[smile]

Hope this helps

Share this post


Link to post
Share on other sites
Hi James! Thanks for your reply!

I looked at the page you linked to, and the description of rbegin() and rend() is:

"The rbegin function returns a reverse bidirectional iterator that points just beyond the end of the controlled sequence. The rend function returns a reverse bidirectional iterator that points at [b]the first[/] element of the sequence."

So, I guess it can be illustrated like this:

1 2 3
( )(#)( )

Where # is the only item in my list, rbegin() would return an iterator pointing at 3, and rend() would return an iterator pointing at 2. So I guess the right thing to do, is just to increment the rbegin() pointer before using it?

But then again, look at their sample code:

typedef set<int,less<int>,allocator<int> > SET_INT;

void main()
{
SET_INT s1;
SET_INT::reverse_iterator i;
cout << "s1.insert(5)" << endl;
s1.insert(5);
cout << "s1.insert(10)" << endl;
s1.insert(10);
cout << "s1.insert(15)" << endl;
s1.insert(15);
cout << "s1.insert(20)" << endl;
s1.insert(20);

// displays: 20,15,10,5

for (i = s1.rbegin(); i != s1.rend(); i++)

cout << "s1 has " << *i << " in its set." << endl;

}



They start the iterator at rbegin() and do not increment it. Isn't this a contradiction?

Share this post


Link to post
Share on other sites
Quote:
Original post by rene_g
They start the iterator at rbegin() and do not increment it. Isn't this a contradiction?


They are incrementing with i++
for (i = s1.rbegin(); i != s1.rend(); i++)

Share this post


Link to post
Share on other sites
Iterating over a range using forward or reverse iterators should look exactly the same. rbegin() returns an iterator that you can dereference just like the iterator returned by begin() (provided the container is not empty), and rend() returns an iterator that you shouldn't dereference and marks the end of the range. (If reverse-iterators didn't encapsulate the complications of iterating backwards, they would be entirely pointless.)

Internally the implementation of reverse iterators can be more complicated. For example, rbegin() for a vector might return an iterator that internally indeed points to one-past-end-of-the-array, but operator* returns *(iter - 1). The reason is that pointers shouldn't be decremented past the beginning of the array.

Perhaps the Entity* that is held in OP's list itself is not valid?

Share this post


Link to post
Share on other sites
In short: don't trust the debugger. :) They implemented reverse iterators on top of bidirectional forward iterators by having each reverse iterator contain a forward iterator that is "one later" than it should be, and decrementing it each time you dereference it.

This confuses the debugger, but it doesn't mean the code is wrong.

To see what is going on better, do the following:
	void EntityImpl::DrawChildren()
{
EntityList::iterator begin = m_children.begin(); // For debug purposes
EntityList::reverse_iterator iter = m_children.rbegin();
EntityList::reverse_iterator rend = m_children.rend(); // For debug purposes
for (; iter != m_children.rend(); ++iter)
{
Entity*& child = *iter;
child->OnDraw();
}
}

You will be able to look at the value of child, which shouldn't be 0xCDCDCDCD.

Share this post


Link to post
Share on other sites
Thank you all for your replies!

You're absolutely right about the iterator, when it's dereferenced, it will be decremented. This is what tricked me to believe the iterator wasn't valid to begin with. So after all my loop is alright. The object pointed to in my list was valid, so after some heavy debugging, i found out what the real cause of the problem was.

*sigh* It was an uninialised struct, I made myself. [doh]

This struct caused a RECT to be set to some very strange values, and I used this rect as a scissor rectangle. The rectangle was given some extreme dimensions (Really large numbers) and i guess my nVidia driver just couldn't take it. So it made my computer crash.

I fixed the problem with the struct, and everything is working smoothly now. [smile]

Thanks alot for your help!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this