vector.erase(iterator iter) will change "iter" or not?

[Richard Herring]

In message

unsigned char before[ sizeof( std::vector<int>::iterator ] ;
memcpy( before, &iter, sizeof( std::vector<int>::iterator ) ) ;
v.erase( iter ) ;
memcmp( before, &iter, sizeof( std::vector<int>::iterator ) ) ;
the memcmp will return a value not equal to 0.

How does that work?

About how you'd expect. The container knows about the iterators
which refer to it, and marks them as invalid whenever it
invalidates them.

I agree that it's legal, but I wouldn't expect it anywhere
except the DS9000; it seems that the implementation, when
faced with vector::erase, would have to go out of its way to
go and change bits in the original 'iter' that the parameter
to vector::erase was copied from.

I'm not sure what you mean by "go out of its way".

Iterate through every copy of every iterator ever generated from that
container, to see if it references the region that's about to be
invalidated?

Every
pre-standard iterator I ever wrote did this. Logically, the
iterator knows about the container, and vice versa.

But physically it need not: see implementations where
vector<T>::iterator is implemented as plain T*.

 

[James Kanze]

In message

Old Wolf wrote: [...]

I agree that it's legal, but I wouldn't expect it anywhere
except the DS9000; it seems that the implementation, when
faced with vector::erase, would have to go out of its way to
go and change bits in the original 'iter' that the parameter
to vector::erase was copied from.

I'm not sure what you mean by "go out of its way".

Iterate through every copy of every iterator ever generated
from that container, to see if it references the region that's
about to be invalidated?

Iterate through every copy of every iterator which currently
exists. Iterators which no longer exist don't matter. And how
many iterators normally exist at any one time.

But physically it need not: see implementations where
vector<T>::iterator is implemented as plain T*.

It's not *required* by the STL. All of the good implementations
do it. It was in my pre-standard containers, where the
specifications didn't allow invalidating the iterator just
because it was convenient for the implementation. (In the case
of lists, there are other possibilities as well---my DLList
class actually didn't delete the node until there were no
iterators pointing to it, and the iterators managed a reference
count in the node.)

 

[Richard Herring]

In message

In message

Old Wolf wrote: [...]
I agree that it's legal, but I wouldn't expect it anywhere
except the DS9000; it seems that the implementation, when
faced with vector::erase, would have to go out of its way to
go and change bits in the original 'iter' that the parameter
to vector::erase was copied from.
I'm not sure what you mean by "go out of its way".

Iterate through every copy of every iterator ever generated
from that container, to see if it references the region that's
about to be invalidated?

Iterate through every copy of every iterator which currently
exists. Iterators which no longer exist don't matter.

"Iterators which no longer exist" don't exist - how _could_ you iterate
through them? :-/

And how
many iterators normally exist at any one time.

First you'd have to define "normally". It might be O(N) if you use
containers of iterators to represent indexes sorted on different
criteria. I don't say it's a good design, but it's certainly a possible
one.

It's not *required* by the STL. All of the good implementations
do it.

No doubt, if you define "good" implementations as the ones that do it.
It's a shame they can't do the same for all the references and pointers
that also become invalidated.

 

[James Kanze]

In message

No doubt, if you define "good" implementations as the ones
that do it.

I define good by those which are standards conformant, and work
as advertised. Basically, Dinkumware and g++.

It's a shame they can't do the same for all the references and
pointers that also become invalidated.

That is, of course, a language issue, rather than a library
issue. The Boehm collector goes a long way in this regard, but
obviously, it can't help in cases where the memory is managed
elsewhere (e.g. in std::vector, but also things like pointers to
local variables).