iterators

[punt]

There appears to be some disagreement on the validity of iterators, after an erase concerning the vector class.

lib.vector.modifiers - void erase(iterator position); "Effects - invalidates all the iterators + references after the point of the erase" - C++ Standard 23.2.5.6

Now the fact that it may work, and other examples do it, unless there is an updated specification (which perhaps there might be), the iterator is invalid. It is intended for deque and vector to be interchangable, with usage depending on if you need to release memory (over preformance).


The fact that UOX depends on a undefined behavior for vector iterators, regardless of "common usage" else where, could be a reason for some of the random crashes.

[giwo]

Somehow I knew there would be a post on this when I came back....

std::vector::erase()

Code: Select all

...
			pointer _Ptr = copy(_ITER_BASE(_Last), _Mylast,
				_ITER_BASE(_First));
			_Destroy(_Ptr, _Mylast);
			_Mylast = _Ptr;
...

To repeat what I already told you in IRC, if it hadn't been intended for the iterator to be usable after an erase(), they wouldn't have done the work of correcting the pointer for you. It would have been just as simple to set _Mylast to _Last, or _First, or not change it at all. Functionality created by those who wrote the .erase() function is intended functionality, and I will consider it such until you give me a GOOD reason (I mean beyond your thoughts) on why it's not.

As for std::deque and std::vector being interchangeable, I see no reason they need to be. If we use a deque, we program for that usage, if we use a vector, we program as such. In this case, the notion of using a whole new vector just to store those we wish to keep and then transferring that data back over on the existing vector was what was CAUSING our crash.

Once again, if this style of coding is good enough for Stanford, it's good enough for UOX3.

[punt]

I am not aruging that a vector class may do that (I am not sure what vector implementation you are referencing), but that isn't the set standard (is is undefined)!!!

But at this web site:
http://www.csci.csusb.edu/dick/c++std/c ... lib.vector

section 23.4.2.3

You will find it talk about erase(), and that it invalides any iterators outstanding beyond that location.





Now, lets ensure we are discussing the same thing. I am saying that any iterator you have after a erase is invalid. NOT the one returned by the operation (that is the next one or the end(), and tha is true for vector and deque).

So not sure which we are talking about.
If the first (not the return value) then you are counting on behavior that is not the specification(which I guess isn't a good reason in your mind).

So regardless of what Stanford or others do, you are counting on a specific behavior.

The standard is for vector and deque to be the same for usage (I only mention it to check errors).


I am fine with UOX3 coding to behavior that works, but not the standard (again, perahaps an updated standard has been released, I coudn't find it). But to say to that vectors do something , if it isn't ina standard, it shouldn't be generalized, but referenced to a specific implementation.

Recognize that as one goes to other STL implemntations , it may not work.

[Sydius]

I agree with punt for once… however I will even go so far as to say that we SHOULD aim for both functioning AND standard-compliance whenever possible. I think you two are talking about two different things, though.

I think punt’s concern is more or less over what happens to all the invalidated iterators that may be hanging around after a call to erase (not necessarily the iterator being erased). This is definitely something to be concerned about, but depends more upon whether or not there is code which assumes an iterator is valid without first performing a check (which is certainly possible, considering UOX’s history).

[giwo]

punt and I resolved the issue last night in IRC chat.

I had to eat a bit of my own foot, but all is well. Basically, I just needed to see the standard for it myself, as every code example or lecture I have found to date has shown to (and even stated that) expect vector.erase() to NOT invalidate the iterator. The simple fix for this (which I was not aware of) is simply do ourIter = vector.erase();

It is quite interesting, though, and probably typical of Microsoft to state that using vector.erase() will invalidate the iterator while their standard STL libraries automatically set the iterator to the next valid list object.

Anyhow, there were remarkably very few instances where UOX3 does this kind of bad behaviour, likely due to my own implementation of CDataList that happened a while back, fixing many issues we were having during iteration.

[Sydius]

Erm, so no iterators are stored anywhere?

What I was thinking punt’s concern was, was with stored (or even local ones, if threading is an issue) iterators that might be invalidated by a call to erase somewhere else.

But then, I do not see why you would be storing iterators anywhere in UOX, unless for some kind of efficiency reason. Efficiency is pretty low on the priority list, though, so I assume there aren’t any?

[punt]

The issue was after a call to a vector.erase(), if you still had an outstanding iterator (say in your loop), is it invalidated.

According to the C++ standard, all STL calls to erase or insert invalidate the iterator (there are conditions that is not true).

As it turned out, MSVC does not invalidate the iterator for vector.erase() (although according to xir their documentation does say otherwise), and apparently some professors show code examples taking advantage of that behavior.

Anyway, it got to a discussion of if invalidating was truely the standard, which I think we have agreed it is (the documented standard).

My understanding is gwio will update the use of those (mainly in loops) for standard conformance.


It is a dead discussion.

[Sydius]

So no stored iterators?

[lingo]

Although I agree to punt's point initially, but after reading through some mailing lists, particular http://lists.boost.org/Archives/boost/2002/08/33428.php, discussing the issues. I think we all misunderstood.

(23.2.4.3/3) std::vector<>::erase invalidates all iterators and
references /after/ the point of the erase.

It meant Only iterators that point to elements after the erased elements will be invalidated in vectors, So iterators point to or before the erased elements are fine.

But I am confuse as hell at this point because it is contrary to my prior understanding.

[Sydius]

ARGH! I GET IT ! THAT IS WHAT I HAVE BEEN TRYING TO EXPLAIN!

Again, I ask… so no stored iterators?

*dies*

[giwo]

lol

Yes, Sydius, we store iterators. Almost every class that has a list stored in it stores an iterator for that list, either directly or by using CDataList. This way we have First/Next/Last instead of forcing you to do the STL yourself.

That is an interesting point you raise, lingo. However, as punt mentioned in another post, if the idea is for a vector and a deque to be interchangable, then you cannot assume it fixes the iterator for you (as a deque will invalidate them).