"P.J. Plauger" wrote:
[SNIP]
> > An iterator is invalid when it is no longer points in a valid [begin,end]
> > range.  In the cases where iterators remain valid, the standard makes no
> > requirements that they continue to be pointed at the same rvalue or object.
>
> The problem here, once again, is that the term ``invalid'' also has more
> than one colloquial meaning. And its usage within the C++ Standard is
> arguably inconsistent. Clearly, erasing a list element renders invalid any
> iterators that designate the erased element. But it is less clear whether
> changing the elements designated by the predecessor and/or successor of
> an iterator renders it invalid.

Sorry to drop into this thread...  I see that hardcore professionals do
talk here, and I am not one.  However Let me pls. try to shed some light
on this invalid issue with my infantile style.  An iterator "points"
somewhere.  "Shows the route" or "gives access" to some "distant"
(decoupled?) things.  Whatever it is.  Now in this way it isd similar to
a traffic sign, showing the way to somewhere.

Let's say we have a roundabout with 5 exists.  In the middle there is a
column, with several D1-1 signs (name and arrow) in angles showing which
exit is for which direction.  Sort of pointers/iterators, if we consider
the roundabout and the 5 exists as a container of edges (of a graph).
Now if I turn the column, so that the signs will point to other exists
than before (or we may try to turn the roundabout/earth, but that's too
expensive :-), will they be valid?  Certainly not.  Why?  In case of
these traffic signs it is clear (while it is not so clear with
iterators).  Because while they point to a road (so I do not crash
following the arrow) they have a label as well: and that label, the
"thing" they point at is not valid anymore.  And of course (technical
talk aside) I will get lost if I follow that "turned signs".

I guess it is similar with iterators.  There is two kinds of validity.
One is whether there is a road in the direction of the arrow (does it
still point to a memory a valid memory location, where there is such an
object, constructed etc.) and is this pointed "thing" the one I wanted?
I mean I did a find and then I use that iterator assuming it does point
to the element found.  Or if I have moved it, then to an element from a
certain distance from the found one (eg.: +/- 3rd).  Now if any
operation makes it to point to sth else (like +4th element instead of
+3rd) the iterator _is_ invalid, but this is validity is from a
different point of view.  My algorithm (if this behaviour is defined by
the std) may depend on that behaviour.  Or it may hit it, since it does
not.

So I guess there is 2 different kinds of "validity" here.  One is: does
the iterator point to a valid element: is it dereferencable?  The other
is: does it point to the _same_ element it did before?

I believe it would be a constructive step to find a different word for
the "second type of validity".  Sorry, I cannot come up with a good
proposal just yet...  But I feel should be a right word for it.

By realizing that there is two different kinds of validity, and that the
second one is sort of subjective (if it is OK for me that the iterator
is "moved" or not) and incorporating this separate ideas into the design
of the standard we may have some clearer view and design, IMHO.

Attila


======================================= MODERATOR'S COMMENT:

You do not need to apologize for posting in this newsgroup
Everyone (not just "hardcore professionals") is welcome to
submit comments that fit the charter.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Stan Sulsky" <stan@sjssoftware.com> wrote in message news:3CA226A9.EAF4C13A@sjssoftware.com...

> Bill Wade wrote:
> ...
> >
> > PJP's answer is correct.  A reverse iterator is not an iterator.  However
> > there is another misconception here.  In your example the reverse iterator
> > did not become invalidated, even though it no longer points at the same
> > object.
> >
> > An iterator is invalid when it is no longer points in a valid [begin,end]
> > range.  In the cases where iterators remain valid, the standard makes no
> > requirements that they continue to be pointed at the same rvalue or object.
> >
>
> As a user, I find these assertions to be disconcerting, if not downright
> astonishing.
>
> "A reverse_iterator is not an iterator?"  What an odd choice of name inthat case.
> Could it really be true that reverse_iterators can't be used in places the
> standard calls for iterators, like in standard algorithms, for example? It's
> hard to believe that was anyone's intent.

The original observation was nowhere near this strong. Several places in
the discussion of containers one can find statements about what ``iterators''
get invalidated. In this context, and ONLY in this context, the sensible
interpretation of the term ``iterators'' is ``objects of type container<T>::
iterator or container<T>::const_iterator. The invalidation of objects of
type container<T>::reverse_iterator and container<T>::const_reverse_iterator
is determined from the definition of template class reverse_iterator, in
terms of which these are defined. I think it is well established by now
that there's too much colloquial looseness involved in the use of the term
iterators in the C++ Standard.

> "The standard makes no requirements that [iterators] continue to be pointed at the
> same rvalue or object?"  In my view, that makes guarantees about the continued
> validity of iterators entirely useless.

And I don't think I can support this viewpoint. But once again, there's a bit
too much colloquial looseness about the use of the term ``invalid'' as well.
And I'm not convinced that the rules for invalidating iterators are coherent.

> If it proved to be difficult to efficiently implement
> list::reverse_iterator
> in such a way that Scott's example worked as expected, I could easily live
> with relaxing the guarantees on list insertion to exclude reverse_iterators.

It's not necessarily difficult to give Scott what he hoped for with list and
map/set, but it CAN be difficult to describe when it's not difficult. And I
do oppose mining ambiguity for unintended functionality.

> For folks like me who actually have to use this stuff, bending the terminology
> to match existing practice is counter-productive.

That's not what's happening. I believe that the folks who described when
iterators get invalidated just didn't foresee the need to have a clearer
definition of the term ``iterators'' in this context.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"James Kuyper Jr." wrote:
>
> Bill Wade wrote:
...
> ... As PJ Plauger has already pointed
> out, a reverse iterator properly should store internally a normal
> iterator, but the particular iterator it should store is one which
> points one position earlier than the position it itself points at.
...

Is that a requirement of the standard or an implementation detail?

If the former, it's in conflict with the guarantee that insertion
into a list doesn't invalidate any iterators, which is where
we came in.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Stan Sulsky wrote:
>
> "James Kuyper Jr." wrote:
> >
> > Bill Wade wrote:
> ...
> > ... As PJ Plauger has already pointed
> > out, a reverse iterator properly should store internally a normal
> > iterator, but the particular iterator it should store is one which
> > points one position earlier than the position it itself points at.
> ...
>
> Is that a requirement of the standard or an implementation detail?

The standard specifies the existence of a protected member of
reverse_iterator<Iterator>, named 'current', of type Iterator. All
operations of reverse_iterator<> are defined in terms of 'current'. For
example, operator*() is defined as:

 Iterator tmp = current;
 return *--tmp;

The fact that it's protected means that you can derive from
reverse_iterator<> and access 'current' by name, and check whether the
operations have precisely the specified effect on that member.
Therefore, an implementation doesn't have much freedom to implement it
differently.

There's a section of the standard that says that when the standard
provides example code, that only defines the effects, an implementation
is free to use any code that produces the same effects. However, on the
rare occasions when the standard specifies a protected member of a
standard library template, I believe that the member must actually
exist, with exactly that name and a type compatible with the specified
one, else why specify that it's protected? However, I've never had
anyone authoritatively confirm or deny that interpretation.

> If the former, it's in conflict with the guarantee that insertion
> into a list doesn't invalidate any iterators, which is where
> we came in.

P.J. Plauger has argued that the invalidation requirements were meant to
refer only to Container::iterator and Container::const_iterator, and not
to the corresponding reverse iterators. Given how detailed the
specification of reverse_iterator is, that pretty much has to be the
case.

Note, in particular, that since the standard is so specific, there's a
good chance that a number of people have already written code that
depends upon those specifics, or will do so sometime between now and the
next release of the standard. As a result, it's going to be difficult to
justify changing the standard to allow implementations that are
incompatible with such code.

I think that the correct solution is to clarify that the invalidation
rules for a reverse iterator are precisely those rules that are implied
by the fact that it contains 'current', and works as specified.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Stan Sulsky" <stan@sjssoftware.com> wrote in message news:3CA32093.CED58918@sjssoftware.com...

> > ... As PJ Plauger has already pointed
> > out, a reverse iterator properly should store internally a normal
> > iterator, but the particular iterator it should store is one which
> > points one position earlier than the position it itself points at.
> ...
>
> Is that a requirement of the standard or an implementation detail?

It's a requirement of the C++ Standard.

> If the former, it's in conflict with the guarantee that insertion
> into a list doesn't invalidate any iterators, which is where
> we came in.

Once again, the use of the term ``iterators'' is too vague in the
discussions of invalidation. But if there's a movement afoot to take
the wording literally, then I welcome the opportunity to invalidate
ALL iterators throughout a program -- including object pointers, which
can serve as iterators -- after any insert into a deque. Better still,
maybe we implementors should each choose one obscure iterator at random
to clobber, just to keep the programmers honest. And of course I'd
expect the educators to warn about the proper style for writing truly
conforming programs...

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Stan Sulsky" <stan@sjssoftware.com> wrote in message

> "A reverse_iterator is not an iterator?"  What an odd choice of name in
> that case.
> Could it really be true that reverse_iterators can't be used in places
> the
> standard calls for iterators, like in standard algorithms, for example?
> It's
> hard to believe that was anyone's intent.

It would probably be better if the standard matched the practice and said
that the container requirements apply to container::iterator.

> "The standard makes no requirements that [iterators] continue to be
> pointed at the
> same rvalue or object?"  In my view, that makes guarantees about the
> continued
> validity of iterators entirely useless.

The standard says that vector::erase(iter) does not invalidate iter.
However, I certainly expect that after the erase, *iter is either illegal
(iter==end()) or is quite likely to yield a new rvalue.

> For folks like me who actually have to use this stuff, bending the
> terminology
> to match existing practice is counter-productive.

It is certainly better to have terminology that doesn't bite you when you're
not careful.


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Bill Wade" <wrwade@swbell.net> wrote in message news:NFap8.5662$o73.1739489461@newssvr11.news.prodigy.com...

> The standard says that vector::erase(iter) does not invalidate iter.
> However, I certainly expect that after the erase, *iter is either illegal
> (iter==end()) or is quite likely to yield a new rvalue.

That's not how I read 23.2.4.3:

: Invalidates all the iterators and references after the point of
: the erase.

though I agree that it is easy to read this as leaving iter itself
valid. Probably should be reworded.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Scott Meyers" <smeyers@aristeia.com> wrote in message
news:MPG.170a5fb6d8ffc9739896c5@news.hevanet.com...
> The program below creates a list, inserts an element, gets a
> reverse_iterator to that element, then inserts a second element.  On the
> five STL implementations I tested, insertion of the second element seems
to
> invalidate the reverse_iterator.

PJP's answer is correct.  A reverse iterator is not an iterator.  However
there is another misconception here.  In your example the reverse iterator
did not become invalidated, even though it no longer points at the same
object.

An iterator is invalid when it is no longer points in a valid [begin,end]
range.  In the cases where iterators remain valid, the standard makes no
requirements that they continue to be pointed at the same rvalue or object.

There are situations where an iterator is not invalidated, but becomes
un-dereferencable.  For instance, vector::erase(it) never invalidates it,
but it will certainly no longer point at the same value, and may not even be
dereferenceable after the operation.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Scott Meyers" <smeyers@aristeia.com> wrote in message news:MPG.170b07676bf44a539896c6@news.hevanet.com...

> On Tue, 26 Mar 2002 22:05:06 GMT, P.J. Plauger wrote:
> > ``Iterators'' here is obviously a colloquialism subsuming objects of
> > class container<T>::iterator and container<T>::const_iterator. It is
> > less obvious that the colloquialism should subsume objects of class
> > container<T>::reverse_iterator and container<T>::const_reverse_iterator.
> > And, in fact, it doesn't.
>
> The basis for this conclusion is...?

The last statement was a matter of observable fact. I didn't mean to
suggest that the term ``iterators'' has a clear definition. It doesn't.

> > > I have heard informally that it is widely known that this guarantee doesn't
> > > hold for reverse_iterators, though I fail to see why it is difficult to
> > > implement for node-based containers (such as list).
> >
> > It's difficult to implement because a reverse iterator has to store the
> > iterator ONE PAST the element it designates.
>
> For a node-based container?  Why?  Why can't a reverse_iterator for a list
> point to the appropriate list node?

Where does rend() point? For a bidirectional list implemented as a ring
with a head node, you can do what you want, at the cost of making reverse
iterators privy to the implementation of iterators. You can probably do
the same with trees (map and set). But you can't generalize this approach
to a singly linked list, which is waiting in the wings. And it's not
obvious whether hash tables are node based or not, so it's not clear
where they would fit in the taxonomy. At the moment, we have one template
class for all reverse iterators and uniform behavior, even if it's not the
behavior you'd like.

>                                    I understand the difficulty for a
> vector, but given a list L, why can't L.end()-- and L.rbegin() point to the
> same list node?

L.end() points OFF THE END of the list, L.rbegin() points to the LAST
element of the list. In fact, in the current implementation of template
class reverse_iterator, L.rbegin() STORES L.end(), but it DESIGNATES --L.end().
Once you get into the business of storing an iterator that designates a
neighboring node, you face the fact that insert or erase can invalidate
iterators that designate neighboring nodes.

> > This is simply another case of the C++ Standard being a bit too offhand
> > in its notation. The fix is to tighten up the wording to make clear that
> > reverse iterators are subject to different invalidation rules.
>
> Has this been filed as a possible defect?  I didn't see anything in rev 20
> of the LWG list.

Dunno. Easily fixed.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Bill Wade" <wrwade@swbell.net> wrote in message news:Xqbo8.71608$Su1.442076292@newssvr30.news.prodigy.com...
>
> "Scott Meyers" <smeyers@aristeia.com> wrote in message
> news:MPG.170a5fb6d8ffc9739896c5@news.hevanet.com...
> > The program below creates a list, inserts an element, gets a
> > reverse_iterator to that element, then inserts a second element.  On the
> > five STL implementations I tested, insertion of the second element seems to
> > invalidate the reverse_iterator.
>
> PJP's answer is correct.  A reverse iterator is not an iterator.

After my last post, I found some supporting verbiage for this notion.
The containers define their reverse iterators in terms of template class
reverse_iterator. The definition of that template class is quite clear
that it stores a (conventional?) iterator one past the element designated
by the reverse iterator. I still believe that we should tighten up the
definition of the term iterator, as used in discussions of invalidation
among the containers; but this added data should reinforce an inclination
to make the new definition describe the current reality.

>                                                                   However
> there is another misconception here.  In your example the reverse iterator
> did not become invalidated, even though it no longer points at the same
> object.
>
> An iterator is invalid when it is no longer points in a valid [begin,end]
> range.  In the cases where iterators remain valid, the standard makes no
> requirements that they continue to be pointed at the same rvalue or object.

The problem here, once again, is that the term ``invalid'' also has more
than one colloquial meaning. And its usage within the C++ Standard is
arguably inconsistent. Clearly, erasing a list element renders invalid any
iterators that designate the erased element. But it is less clear whether
changing the elements designated by the predecessor and/or successor of
an iterator renders it invalid. The C++ Standard takes one position on
respliced elements (the iterators become invalid), another on swapped
elements (the iterators magically become valid for a different container),
and yet another on elements in a deque, vector, or string (the iterators
become invalid even if you can predict exactly what the newly designated
element, and the new neighbor(s), might be.) And for the moment, I don't
want to look too closely at the wording on references and pointers.

> There are situations where an iterator is not invalidated, but becomes
> un-dereferencable.  For instance, vector::erase(it) never invalidates it,
> but it will certainly no longer point at the same value, and may not even be
> dereferenceable after the operation.

I guess I would say that the iterator becomes invalid. But I'd hate to
have to find support in the C++ Standard for an arbitrary statement of
that ilk.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Wed, 27 Mar 2002 09:59:11 CST, Bill Wade wrote:
> PJP's answer is correct.  A reverse iterator is not an iterator.  However

And the basis for this claim is...what?

21.3.2/3:  string::rbegin() returns an ITERATOR which is semantically
           equivalent to reverse_iterator(end()).

Table 66, first line:  the expression X::reverse_iterator has a return type
of "ITERATOR type pointing to T".

Section 24.4 is labeled "Predefined ITERATORS."  The text immediately
following that is subsection 24.4.1, which is entitled "Reverse ITERATORS."

All emphases above are mine.  Where in the Standard is there evidence for
the claim that reverse iterators are not iterators?

Scott

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Bill Wade wrote:
...
>
> PJP's answer is correct.  A reverse iterator is not an iterator.  However
> there is another misconception here.  In your example the reverse iterator
> did not become invalidated, even though it no longer points at the same
> object.
>
> An iterator is invalid when it is no longer points in a valid [begin,end]
> range.  In the cases where iterators remain valid, the standard makes no
> requirements that they continue to be pointed at the same rvalue or object.
>

As a user, I find these assertions to be disconcerting, if not downright
astonishing.

"A reverse_iterator is not an iterator?"  What an odd choice of name in
that case.
Could it really be true that reverse_iterators can't be used in places
the
standard calls for iterators, like in standard algorithms, for example?
It's
hard to believe that was anyone's intent.

"The standard makes no requirements that [iterators] continue to be
pointed at the
same rvalue or object?"  In my view, that makes guarantees about the
continued
validity of iterators entirely useless.

If it proved to be difficult to efficiently implement
list::reverse_iterator
in such a way that Scott's example worked as expected, I could easily
live
with relaxing the guarantees on list insertion to exclude
reverse_iterators.
For folks like me who actually have to use this stuff, bending the
terminology
to match existing practice is counter-productive.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Bill Wade wrote:
....
> PJP's answer is correct.  A reverse iterator is not an iterator.  However

That's not quite what he meant (I hope). A reverse iterator is indeed an
iterator - it meets all of the bidirectional iterator requirements. If
Iterator is a random-access iterator, reverse_iterator<Iterator> will
also meet all of the random-access iterator requirements.

What is not the case, is that a reverse iterator derived from a normal
iterator is governed by the same validity constraints as the iterator it
was derived from. This is required by As PJ Plauger has already pointed
out, a reverse iterator properly should store internally a normal
iterator, but the particular iterator it should store is one which
points one position earlier than the position it itself points at. The
result is that it become invalid when the stored iterator becomes
invalid.

> there is another misconception here.  In your example the reverse iterator
> did not become invalidated, even though it no longer points at the same
> object.
>
> An iterator is invalid when it is no longer points in a valid [begin,end]
> range.  In the cases where iterators remain valid, the standard makes no
> requirements that they continue to be pointed at the same rvalue or object.

I'm afraid it does; if you look carefully at the rules governing the
validity of iterators in the standard library's containers, you'll find
that they become invalid whenever the natural implementation of the
container might need to change the physical memory location of the
referenced element.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Wed, 27 Mar 2002 18:23:16 GMT, P.J. Plauger wrote:
> The containers define their reverse iterators in terms of template class
> reverse_iterator. The definition of that template class is quite clear
> that it stores a (conventional?) iterator one past the element designated
> by the reverse iterator.

This looks to me like overspecification by essentially dictating
implementation, but it is, alas, what the Standard says.  FWIW, I hold
little hope that the Standard will be modified to say that reverse
iterators are iterators and hence the iterator invalidation rules apply to
them, too, but I do think that the current situation is extremely
confusing.  Not that it's breaking any new ground in that regard.

> an iterator renders it invalid. The C++ Standard takes one position on
> respliced elements (the iterators become invalid), another on swapped
> elements (the iterators magically become valid for a different container),

Except for strings, sigh.

Scott

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

The program below creates a list, inserts an element, gets a
reverse_iterator to that element, then inserts a second element.  On the
five STL implementations I tested, insertion of the second element seems to
invalidate the reverse_iterator.  This is in conflict with 23.1.2/8:

  The insert members shall not affect the validity of iterators and
  references to the container...

I have heard informally that it is widely known that this guarantee doesn't
hold for reverse_iterators, though I fail to see why it is difficult to
implement for node-based containers (such as list).

What is the situation regarding invalidation of reverse_iterators when an
element is inserted into a node-based container?  The standard seems to say
that they are not invalidated.  Existing implementations seem to ignore
that constraint.  Presumably, one of these must be made to conform to the
other.  Anybody have any insights as to which will be forced to blink?

Thanks,

Scott


#include <iostream>
#include <list>

int main()
{
  std::list<int> int_list;
  int_list.push_back(1);
  std::list<int>::reverse_iterator iter = int_list.rbegin();
  std::cout << *iter;           // prints "1"
  int_list.push_back(2);
  std::cout << *iter;           // should print "1", but prints "2"
}

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Scott Meyers" <smeyers@aristeia.com> wrote in message news:MPG.170a5fb6d8ffc9739896c5@news.hevanet.com...

> The program below creates a list, inserts an element, gets a
> reverse_iterator to that element, then inserts a second element.  On the
> five STL implementations I tested, insertion of the second element seems to
> invalidate the reverse_iterator.  This is in conflict with 23.1.2/8:
>
>   The insert members shall not affect the validity of iterators and
>   references to the container...

``Iterators'' here is obviously a colloquialism subsuming objects of
class container<T>::iterator and container<T>::const_iterator. It is
less obvious that the colloquialism should subsume objects of class
container<T>::reverse_iterator and container<T>::const_reverse_iterator.
And, in fact, it doesn't.

> I have heard informally that it is widely known that this guarantee doesn't
> hold for reverse_iterators, though I fail to see why it is difficult to
> implement for node-based containers (such as list).

It's difficult to implement because a reverse iterator has to store the
iterator ONE PAST the element it designates. Otherwise, you can't represent
the values returned by rbegin() and rend(). Clobber the stored iterator and
you clobber the reverse iterator.

> What is the situation regarding invalidation of reverse_iterators when an
> element is inserted into a node-based container?  The standard seems to say
> that they are not invalidated.  Existing implementations seem to ignore
> that constraint.  Presumably, one of these must be made to conform to the
> other.  Anybody have any insights as to which will be forced to blink?

This is simply another case of the C++ Standard being a bit too offhand
in its notation. The fix is to tighten up the wording to make clear that
reverse iterators are subject to different invalidation rules. It would be
rather hard to ``fix'' the invalidation of reverse iterators. And they may
not always be unique in this regard. Our implementation of slist, for example,
stores a pointer to the forward link to the designated node, not a pointer to
the node proper. The benefit of this approach is that insert and erase can
occur in constant time -- no need for linear time versions, or the kludgy
insert_after and before_begin of other versions. The cost of this approach is
that more iterators get invalidated whenever the controlled sequence changes.
But that's a problem we already have to live with given reverse iterators,
which have been in STL since 1994.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Tue, 26 Mar 2002 22:05:06 GMT, P.J. Plauger wrote:
> ``Iterators'' here is obviously a colloquialism subsuming objects of
> class container<T>::iterator and container<T>::const_iterator. It is
> less obvious that the colloquialism should subsume objects of class
> container<T>::reverse_iterator and container<T>::const_reverse_iterator.
> And, in fact, it doesn't.

The basis for this conclusion is...?

> > I have heard informally that it is widely known that this guarantee doesn't
> > hold for reverse_iterators, though I fail to see why it is difficult to
> > implement for node-based containers (such as list).
>
> It's difficult to implement because a reverse iterator has to store the
> iterator ONE PAST the element it designates.

For a node-based container?  Why?  Why can't a reverse_iterator for a list
point to the appropriate list node?  I understand the difficulty for a
vector, but given a list L, why can't L.end()-- and L.rbegin() point to the
same list node?

> This is simply another case of the C++ Standard being a bit too offhand
> in its notation. The fix is to tighten up the wording to make clear that
> reverse iterators are subject to different invalidation rules.

Has this been filed as a possible defect?  I didn't see anything in rev 20
of the LWG list.

Scott

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]