a question of iterator

evenstar

Expand|Select|Wrap|Line Numbers

 
list <int>  a; 

a.push_back(10); 

a.push_back(15); 

int* po; 

list <int>::reverse_iterator iter=a.rbegin(); 

cout<<"value of iter point to:"<<*iter<<endl;

po=&(*iter); 

a.push_back(9);

cout<<"value of iter point to:"<<*iter<<endl;

cout<<"value of po point to:"<<*po<<endl;

// Visual Studio 2008

output:
value of iter point to:15
value of iter point to:9
value of po point to:15
I didn't move iter ,and i think it should point to value of 15.But it has point to 9,after "push_back".Why?

JosAH

Read the second paragraph of this link. In short: your iterator isn't valid anymore after a (structural) change of the container.

kind regards,

Jos

evenstar

Thanks very much for your help,but it is a list,not a vector.

JosAH

Quote:

Originally Posted by evenstar

Thanks very much for your help,but it is a list,not a vector.

Ah, silly me ... it looks like your rbegin() object is 'over active'; this shouldn't happen as far as I know; I'll give it some more thoughts; strange ...

kind regards,

Jos

Banfa

I can tell you what the actual behaviour of the STL (in my implementation which is gcc 4.4.3) is, whether this is mandated or not by the standard I don't know.

By it's nature rbegin returns the same value as end (in the same way rend returns the same value as begin). That is it returns a pointer just passed the end of the list. When you dereference the iterator returned by rbegin the first thing is does is temporarily back-up the list 1 place and then return that value.

What happens is when you get the iterator it points to rbegin, the beginning of the reversed list. The effect of this in your small (and ill advised in my opinion) program is that when you perform the 3rd push_back the iterator remains pointing at the start of the reversed list (probably what you would expect to happen if you took the value of begin and then did a push_back).

You dereference the actual value and take a pointer to it and you get a pointer to a specific list item and that remains constant but your iterator constantly remains pointing at the start of the reversed list not the start of the reversed list at the time you requested the iterator value because it actually points past the end of the list. So when you push_back the iterator points to the new reversed list start where as you pointer remains pointing at the specific list entry you pointed it at.

evenstar

"it actually points past the end of the list"?Oh, what has happened ?

JosAH

Quote:

Originally Posted by Banfa

By it's nature rbegin returns the same value as end (in the same way rend returns the same value as begin). That is it returns a pointer just passed the end of the list. When you dereference the iterator returned by rbegin the first thing is does is temporarily back-up the list 1 place and then return that value.

I find your reasoning wobbly at best ;-) and I checked good ol' Bjarne for this: read page 444 (the C++ programming language 3rd edition) for a nice picture of where those iterators actually point to. Page 557 gives the answer (par. 19.2.5: Reverse Iterators). Because you can't actually point before the first element (see that picture) you have to keep track of a 'current' position. That 'current' position is one position beyond (in normal direction) the actual position. That way you prevent something from pointing before the first element (which is impossible). The 'current' position is the actual reverse iterator. Halfway page 557 you can see what actually happens; it's nifty ...

kind regards,

Jos

Banfa

I'll have to look it up tomorrow as my copy of that book is at work were I use it :D

evenstar

Oh,I got it ,because of "current-1".JosAH and Banfa,I thank you very much indeed,that's very kind of you.

The book also says:
"avoid access violations,current points to the element after the one the reverse_iterator refers to.This implies that * returns the value * (current-1) and..."

But how to access violations?The rend(one-before-the-beginning)element can stop it.So,i don't think uisng "current-1" is necessary.

Banfa

I have read the book Jos and it says what you say it says (surprise surprise eh). My thinking and logic where along the write lines but I am definately glad I read the book and got the kinks sorted out.

evenstar, as to your last question in the same book you need to refer to section 5.3 Pointers into Arrays which says among other things:

Taking a pointer to one element beyond the end of an array is guaranteed to work.

and

The result of taking the address of the element before the initial element is undefined and should be avoided.

Now while a list may not be an array a vector is and they both use the same standard implementation of the reverse iterator (shown on page 557 of said book) so the reverse iterator must conform to the 2 quotes I gave. That is it can point into or 1 past the end of the "array" or at any element in the array.

In light of that having the reverse iterator point to 1 past the required element and returning (current - 1) keeps the logic and pointer arithmetic nice and simple.