suppose I will delete an element pointed to by "iter".
like this:

vector<int> s;
for(vector<int>::iterator iter=s.begin(); iter!=s.end(); iter++){
if(*iter==3)
s.erase(iter); //A
}

in line A, if element by "iter" is erased, will "iter" point to the
next element(now should be the current element) automatically?

thomas wrote:
> suppose I will delete an element pointed to by "iter".
> like this:
>
> vector<int> s;
> for(vector<int>::iterator iter=s.begin(); iter!=s.end(); iter++){
> if(*iter==3)
> s.erase(iter); //A
> }
>
> in line A, if element by "iter" is erased, will "iter" point to the
> next element(now should be the current element) automatically?

The iterator that refers to the removed element and all elements
after the removed one are invalidated by that operation. IOW, the
Standard makes no attempt to define what the 'iter' would point to
after being erased.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

On Thu, 21 Feb 2008 15:16:11 +0100, thomas <FreshThomas@gmail.com> wrote:

> suppose I will delete an element pointed to by "iter".
> like this:
>
> vector<int> s;
> for(vector<int>::iterator iter=s.begin(); iter!=s.end(); iter++){
> if(*iter==3)
> s.erase(iter); //A
> }
>
> in line A, if element by "iter" is erased, will "iter" point to the
> next element(now should be the current element) automatically?

Do :

vector<int> s;
for(vector<int>::iterator iter=s.begin(); iter!=s.end(); iter++){
if(*iter==3)
iter= s.erase(iter);
}

In message <fpk2sg$5du$1@news.datemas.de>, Victor Bazarov
<v.Abazarov@comAcast.net> writes
>thomas wrote:
>> suppose I will delete an element pointed to by "iter".
>> like this:
>>
>> vector<int> s;
>> for(vector<int>::iterator iter=s.begin(); iter!=s.end(); iter++){
>> if(*iter==3)
>> s.erase(iter); //A
>> }
>>
>> in line A, if element by "iter" is erased, will "iter" point to the
>> next element(now should be the current element) automatically?
>
>The iterator that refers to the removed element and all elements
>after the removed one are invalidated by that operation. IOW, the
>Standard makes no attempt to define what the 'iter' would point to
>after being erased.

I wonder if the OP is confused because the iterator is passed by value
and therefore not modified? Obviously erase(iter) can't change its
_value_, but it certainly changes its _meaning_ - what it points to is
no longer valid.

(And the higher-level answer to his question is that he should probably
be using std::remove anyway:

s.erase(remove(s.begin(), s.end(), 3), s.end());

)
--
Richard Herring

> (And the higher-level answer to his question is that he should probably
> be using std::remove anyway:
>
> s.erase(remove(s.begin(), s.end(), 3), s.end());
>

What's this?
will "s.erase()" get all the elements after "3" removed?

"thomas" <FreshThomas@gmail.com> a écrit dans le message de news:
c69c72bd-a326-4bc5-b1ef-4dd03288d4f4...oglegroups.com...
>
>> (And the higher-level answer to his question is that he should probably
>> be using std::remove anyway:
>>
>> s.erase(remove(s.begin(), s.end(), 3), s.end());
>>
>
> What's this?
> will "s.erase()" get all the elements after "3" removed?

remove will remove all element equal to 3. beware, removing is not
erasing... Remove returns an iterator to the new end of the sequence s (it
does not actually modify s.end() ) , so you can use this iterator in the
vector::erase function. The size of the vector is not modified after a
remove, but the element between the returned end and the actual s.end() but
the element are unspecified.

so you can do

vector<int>::iterator NewEnd = remove(s.begin(), s.end(), 3);
s.erase(NewEnd, s.end);


Eric Pruneau

In message
<c69c72bd-a326-4bc5-b1ef-4dd03288d4f4@i29g2000prf.googlegroups.com>,
thomas <FreshThomas@gmail.com> writes
>
>> (And the higher-level answer to his question is that he should probably
>> be using std::remove anyway:
>>
>> s.erase(remove(s.begin(), s.end(), 3), s.end());
>
>What's this?

It's a C++ STL idiom.

>will "s.erase()" get all the elements after "3" removed?

No. It erases everything in the range defined by the _two_ iterators
being passed to it. And remove() copies the non-3 elements down to the
beginning of s, returning an iterator to the first element beyond them.

If you don't know this stuff, you'd do better to read a good book than
ask random questions here.

--
Richard Herring

Just a small correction.

> vector<int> s;
> for(vector<int>::iterator iter=s.begin(); iter!=s.end(); iter++){
> if(*iter==3)
> iter= s.erase(iter);
> }

After the erase() call iter points at the next element in the
container. Thus when the iter++ is called you will effectively skip
an element or if the erased element is the last element it now points
one after end().

Also for efficiency it is a god idea to get in the habit of using
prefix increment (In this case it probably makes no difference but
for the generic case it does).

On Feb 22, 4:31 am, Richard Herring <junk@[127.0.0.1]> wrote:
> In message <fpk2sg$5d...@news.datemas.de>, Victor Bazarov
> >The iterator that refers to the removed element and all elements
> >after the removed one are invalidated by that operation. IOW, the
> >Standard makes no attempt to define what the 'iter' would point to
> >after being erased.
>
> I wonder if the OP is confused because the iterator is passed by value
> and therefore not modified? Obviously erase(iter) can't change its
> _value_, but it certainly changes its _meaning_ - what it points to is
> no longer valid.

The value certainly is changed: previously it was
well-defined and now it is indeterminate! It doesn't
point anywhere; it's nonsensical to say that what
it points to is not valid. Perhaps you mean to say
that the representation isn't changed;

On 22 Feb, 08:31, Old Wolf <oldw...@inspire.net.nz> wrote:
> On Feb 22, 4:31 am, Richard Herring <junk@[127.0.0.1]> wrote:
>
> > In message <fpk2sg$5d...@news.datemas.de>, Victor Bazarov
> > >The iterator that refers to the removed element and all elements
> > >after the removed one are invalidated by that operation. IOW, the
> > >Standard makes no attempt to define what the 'iter' would point to
> > >after being erased.
>
> > I wonder if the OP is confused because the iterator is passed by value
> > and therefore not modified? Obviously erase(iter) can't change its
> > _value_, but it certainly changes its _meaning_ - what it points to is
> > no longer valid.
>
> The value certainly is changed: previously it was
> well-defined and now it is indeterminate! It doesn't
> point anywhere; it's nonsensical to say that what
> it points to is not valid. Perhaps you mean to say
> that the representation isn't changed;

That's an interesting point. Consider:
int * p = new int(441);
delete p;

Would you say that the last line changes the value of p?

DP

In message
<c76ba343-355d-46ed-b028-3cd137425161@s13g2000prd.googlegroups.com>, Old
Wolf <oldwolf@inspire.net.nz> writes
>On Feb 22, 4:31 am, Richard Herring <junk@[127.0.0.1]> wrote:
>> In message <fpk2sg$5d...@news.datemas.de>, Victor Bazarov
>> >The iterator that refers to the removed element and all elements
>> >after the removed one are invalidated by that operation. IOW, the
>> >Standard makes no attempt to define what the 'iter' would point to
>> >after being erased.
>>
>> I wonder if the OP is confused because the iterator is passed by value
>> and therefore not modified? Obviously erase(iter) can't change its
>> _value_, but it certainly changes its _meaning_ - what it points to is
>> no longer valid.
>
>The value certainly is changed: previously it was
>well-defined and now it is indeterminate!

Its value has become singular, certainly, but that's because the set of
singular values has changed, not because the iterator has.

> It doesn't
>point anywhere; it's nonsensical to say that what
>it points to is not valid.

If it doesn't point anywhere, it points nowhere. "nowhere" looks pretty
invalid to me.

> Perhaps you mean to say
>that the representation isn't changed;

Perhaps.

--
Richard Herring

On Feb 22, 11:54 pm, Richard Herring <junk@[127.0.0.1]> wrote:
> If it doesn't point anywhere, it points nowhere. "nowhere" looks pretty
> invalid to me.

Non-sequitur ; there are three possible states for
pointers (or iterators): pointing to a valid object,
null, or indeterminate. By 'anywhere' I do not
include the indeterminate case.

On Feb 22, 8:47 pm, Triple-DES <fire13...@hotmail.com> wrote:
> That's an interesting point. Consider:
> int * p = new int(441);
> delete p;
>
> Would you say that the last line changes the value of p?

Yes

In message
<ee7bf0ee-1e6d-4b5c-9e66-8d72052145b7@64g2000hsw.googlegroups.com>, Old
Wolf <oldwolf@inspire.net.nz> writes
>On Feb 22, 11:54 pm, Richard Herring <junk@[127.0.0.1]> wrote:

[big snip noted]

>> If it doesn't point anywhere, it points nowhere. "nowhere" looks pretty
>> invalid to me.
>
>Non-sequitur ; there are three possible states for
>pointers (or iterators): pointing to a valid object,
>null, or indeterminate.

The standard refers to this state as "[having] singular values".

>By 'anywhere' I do not
>include the indeterminate case.

But you obviously meant "not anywhere" to include singular states when
you wrote this:

>>> previously it was well-defined and now it is indeterminate! It
>>>doesn't point anywhere;

--
Richard Herring

On Feb 23, 2:38 am, Richard Herring <junk@[127.0.0.1]> wrote:
> But you obviously meant "not anywhere" to include singular states when
> you wrote this:
>
> >>> previously it was well-defined and now it is indeterminate! It
> >>>doesn't point anywhere;

Actually I didn't. I'll try to use more precise
terms than "anywhere" in future.

On Feb 22, 8:31 am, Old Wolf <oldw...@inspire.net.nz> wrote:
> On Feb 22, 4:31 am, Richard Herring <junk@[127.0.0.1]> wrote:

> > In message <fpk2sg$5d...@news.datemas.de>, Victor Bazarov
> > >The iterator that refers to the removed element and all elements
> > >after the removed one are invalidated by that operation. IOW, the
> > >Standard makes no attempt to define what the 'iter' would point to
> > >after being erased.

> > I wonder if the OP is confused because the iterator is
> > passed by value and therefore not modified? Obviously
> > erase(iter) can't change its _value_, but it certainly
> > changes its _meaning_ - what it points to is no longer
> > valid.

> The value certainly is changed: previously it was
> well-defined and now it is indeterminate!

I'm not sure whether you can use the word "changed" here or
not. After the erase, iter has no value. At least, not one you
can legally access.

> It doesn't point anywhere; it's nonsensical to say that what
> it points to is not valid. Perhaps you mean to say that the
> representation isn't changed;

Not with the implementation I use After the erase, the only way
you could look at the representation is by means of a memcpy,
and if you do:

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.

And trying to use the iterator will cause a core dump. (To be
very, very clear:

#include <vector>

int
main()
{
static int const init[] = { 1, 2, 3, 4, 5 } ;
std::vector< int > v( init, init + 5 ) ;
std::vector< int >::iterator
iter = v.begin() + 3 ;
v.erase( iter ) ;
std::vector< int >::iterator
i2 = iter ;
}

core dumps on the last line in main. You cannot read an invalid
iterator other than as an array of bytes.)

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

On Feb 22, 11:54 am, Richard Herring <junk@[127.0.0.1]> wrote:
> In message
> <c76ba343-355d-46ed-b028-3cd137425...@s13g2000prd.googlegroups.com>, Old
> Wolf <oldw...@inspire.net.nz> writes

> >On Feb 22, 4:31 am, Richard Herring <junk@[127.0.0.1]> wrote:
> >> In message <fpk2sg$5d...@news.datemas.de>, Victor Bazarov
> >> >The iterator that refers to the removed element and all
> >> >elements after the removed one are invalidated by that
> >> >operation. IOW, the Standard makes no attempt to define
> >> >what the 'iter' would point to after being erased.

> >> I wonder if the OP is confused because the iterator is
> >> passed by value and therefore not modified? Obviously
> >> erase(iter) can't change its _value_, but it certainly
> >> changes its _meaning_ - what it points to is no longer
> >> valid.

> >The value certainly is changed: previously it was
> >well-defined and now it is indeterminate!

> Its value has become singular, certainly, but that's because
> the set of singular values has changed, not because the
> iterator has.

> >It doesn't point anywhere; it's nonsensical to say that what
> >it points to is not valid.

> If it doesn't point anywhere, it points nowhere. "nowhere"
> looks pretty invalid to me.

It doesn't point, period.

> > Perhaps you mean to say that the representation isn't
> > changed;

> Perhaps.

Consider:

#include <vector>
#include <cstring>
#include <iostream>

int
main()
{
static int const init[] = { 1, 2, 3, 4, 5 } ;
std::vector< int > v( init, init + 5 ) ;
std::vector< int >::iterator
iter = v.begin() + 3 ;
unsigned char before[ sizeof( iter ) ] ;
std::memcpy( before, &iter, sizeof( iter ) ) ;
v.erase( iter ) ;
if ( std::memcmp( before, &iter, sizeof( iter ) ) == 0 ) {
std::cout << "unchanged" << std::endl ;
} else {
std::cout << "changed" << std::endl ;
}
}

On my implementation, this outputs "changed". And any attempt
to access iter as an std::vector< int >::iterator (e.g. to copy
it, compare it, etc.) generates a core dump.

I don't quite know what you mean by "its representation". If
it's just the underlying bits in memory, then it's changed. If
it's anything else, then you can't tell, because there's nothing
you can do other than look at the bytes that has defined
behavior (and the implementation I normally use core dumps in
all of the cases of undefined behavior).

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

On Feb 21, 6:45 pm, Martin York <Martin.YorkAma...@gmail.com> wrote:

[...]
> Also for efficiency it is a god idea to get in the habit of
> using prefix increment (In this case it probably makes no
> difference but for the generic case it does).

Measurements? Or is this just speculation on your part. (I've
actually measured with g++, and all of the standard iterators.
No measurable difference.)

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

On Feb 23, 6:40 am, James Kanze <james.ka...@gmail.com> wrote:
> 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? 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.

> And trying to use the iterator will cause a core dump.

To be expected when using indeterminate 'values'.

Old Wolf wrote:
> On Feb 23, 6:40 am, James Kanze <james.ka...@gmail.com> wrote:
> > 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". Every
pre-standard iterator I ever wrote did this. Logically, the
iterator knows about the container, and vice versa.

> > And trying to use the iterator will cause a core dump.

> To be expected when using indeterminate 'values'.

Huh? On my system, I don't get a core dump just because I copy
an invalid pointer (say, after a delete). I do if I copy an
invalid iterator, however. (If, after the erase above, I assign
iter to some other iterator, I get a core dump, with a message
that I've used an invalid iterator.)

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

In message
<a2f9ee21-5d0c-4728-b8ce-0837e6a15c0e@f47g2000hsd.googlegroups.com>,
James Kanze <james.kanze@gmail.com> writes
>Old Wolf wrote:
>> On Feb 23, 6:40 am, James Kanze <james.ka...@gmail.com> wrote:
>> > 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*.

--
Richard Herring

On Feb 25, 5:40 pm, Richard Herring <junk@[127.0.0.1]> wrote:
> In message
> <a2f9ee21-5d0c-4728-b8ce-0837e6a15...@f47g2000hsd.googlegroups.com>,
> James Kanze <james.ka...@gmail.com> writes
> >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.

> >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*.

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.)

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

In message
<79bc8204-9fcd-4cae-808b-d6b179de163c@v3g2000hsc.googlegroups.com>,
James Kanze <james.kanze@gmail.com> writes
>On Feb 25, 5:40 pm, Richard Herring <junk@[127.0.0.1]> wrote:
>> In message
>> <a2f9ee21-5d0c-4728-b8ce-0837e6a15...@f47g2000hsd.googlegroups.com>,
>> James Kanze <james.ka...@gmail.com> writes
>> >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.

>> >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*.
>
>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.

> 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

On Feb 26, 11:31 am, Richard Herring <junk@[127.0.0.1]> wrote:
> In message
> <79bc8204-9fcd-4cae-808b-d6b179de1...@v3g2000hsc.googlegroups.com>,
> James Kanze <james.ka...@gmail.com> writes
> >> 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.

> 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 in cases where the memory is managed
elsewhere (e.g. in std::vector, but also things like pointers to
local variables).

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34