Hello!

My question is short and simple: is the member function end() of the
standard containers supposed to return a constant iterator, i.e. one
that does never change even if the container is changed?

To make it perhaps clearer: I don't want to ask whether end() is the
same
for all container instances, but whether it retains the same value for
each
specific container instance during program execution.

I've found nothing in the Standard that treates end() as a special
case. So I'm inclined to think that end() is an ordinary iterator that
may be invalidated when the specification allows iterators to be
invalidated.

Can anyone confirm that?

Best regards,
  Christoph


---
[ 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                       ]

On Wed, 10 Sep 2003 09:18:04 +0000, Christoph Schulz wrote:

> Hello!
>
> My question is short and simple: is the member function end() of the
> standard containers supposed to return a constant iterator, i.e. one
> that does never change even if the container is changed?
>

No, it can change . So, you cannot cache the value in a loop when
you know that it may get potentially invalidated. the rules for
invalidation are pretty clear. I usually steer clear clear of the standard
in this aspect, and refer to the SGI manual that states very clearly when
a container's iterators may be invalidated. So, the normal rules for
iterator invalidation are applicable even to end().

Regards,
-Dhruv.







---
[ 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                       ]

""Christoph Schulz"" <kristov@arcor.de> wrote in message news:bjmfgd$kavuc$1@ID-175807.news.uni-berlin.de...
> Hello!
>
> My question is short and simple: is the member function end() of the
> standard containers supposed to return a constant iterator, i.e. one
> that does never change even if the container is changed?

It returns an value of type iterator for a non-const container, and
a value of type const_iterator for a const constainer.


> I've found nothing in the Standard that treates end() as a special
> case. So I'm inclined to think that end() is an ordinary iterator that
> may be invalidated when the specification allows iterators to be
> invalidated.
>
That is true.   For example, vector iterators can be implemented as
pointers to the contiguous internal storage of the vector.   end() simply
returns the pointer to one-past-the-end of the internal array.   Any reallocation
or even just changing the size of the vector will invalidate it.


---
[ 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                       ]

""Christoph Schulz"" <kristov@arcor.de> wrote in message
news:bjmfgd$kavuc$1@ID-175807.news.uni-berlin.de...
>
> My question is short and simple: is the member function end() of the
> standard containers supposed to return a constant iterator, i.e. one
> that does never change even if the container is changed?

Nope.  It gets invalidated just like any other iterator.  Otherwise,
implementations that used T* for vector<T> iterators wouldn't work.

Ken


---
[ 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                       ]

kristov@arcor.de ("Christoph Schulz") wrote in message news:<bjmfgd$kavuc$1@ID-175807.news.uni-berlin.de>...
> Hello!
>
> My question is short and simple: is the member function end() of the
> standard containers supposed to return a constant iterator, i.e. one
> that does never change even if the container is changed?

No, it can change. The most obvious case is vector<T>::end(). It can
return a T*, which obviously will change even when shrinking a vector
(in which case no allocation happens).

In general, all random access containers have size()==end()-begin()
which means that when size() changes, either end() or begin()
is likely to change. It can be avoided ( special-casing in
operator- ) but that's unnecessarily complex.

---
[ 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                       ]

On Wed, 10 Sep 2003 09:18:04 +0000 (UTC), kristov@arcor.de ("Christoph
Schulz") wrote:

>Hello!
>
>My question is short and simple: is the member function end() of the
>standard containers supposed to return a constant iterator, i.e. one
>that does never change even if the container is changed?
>
>To make it perhaps clearer: I don't want to ask whether end() is the
>same
>for all container instances, but whether it retains the same value for
>each
>specific container instance during program execution.
>
>I've found nothing in the Standard that treates end() as a special
>case. So I'm inclined to think that end() is an ordinary iterator that
>may be invalidated when the specification allows iterators to be
>invalidated.
>
>Can anyone confirm that?

"end" is invalidated just like other iterators. However, end is never
invalidated for node based containers (because of the invalidation
rules on such containers), so you can rely on end() iterators for
list, map, etc. never being invalidated. However, with vector and
deque, end() is often invalidated.

Tom

---
[ 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                       ]

Hi,

Christoph Schulz wrote:

> I've found nothing in the Standard that treates end() as a special
> case. So I'm inclined to think that end() is an ordinary iterator that
> may be invalidated when the specification allows iterators to be
> invalidated.
>
> Can anyone confirm that?

Yes.
end() can be invalidated as any other iterator, if a given operation
asserts that it invalidates iterators. On the other hand, if some
operation asserts that it does not invalidate iterators, then end() also
remains "stable".

It is sometimes viable to make end() "const" in the sense that it always
remains the same (for example in list), but sometimes the cost of
maintaining it and the cost of performing operator== with other
iterators would be too big (for example in vector).

--
Maciej Sobczak
http://www.maciejsobczak.com/

Distributed programming lib for C, C++, Python & Tcl:
http://www.maciejsobczak.com/prog/yami/

---
[ 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                       ]

On Wed, 10 Sep 2003 09:18:04 +0000 (UTC), kristov@arcor.de ("Christoph
Schulz") wrote:

> I've found nothing in the Standard that treates end() as a special
> case. So I'm inclined to think that end() is an ordinary iterator that
> may be invalidated when the specification allows iterators to be
> invalidated.

You are correct.  You should note that there is nothing in the
specification of the associatives or list which allows an end iterator
to be invalidated.  All invalidations apply only to dereferencable
iterators and end is not one.

Stated simply.  Node based containers have end iterators which remain
valid for the life of the container and array based containers have
end iterators which self destruct on most modifications of the
container.

John

---
[ 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                       ]

kristov@arcor.de ("Christoph Schulz") writes:

> Hello!
>
> My question is short and simple: is the member function end() of the
> standard containers supposed to return a constant iterator, i.e. one
> that does never change even if the container is changed?
>
> To make it perhaps clearer: I don't want to ask whether end() is the
> same
> for all container instances, but whether it retains the same value for
> each
> specific container instance during program execution.
>
> I've found nothing in the Standard that treates end() as a special
> case. So I'm inclined to think that end() is an ordinary iterator that
> may be invalidated when the specification allows iterators to be
> invalidated.
>
> Can anyone confirm that?
[snip]

I think an iterator returned from end() can be invalidated whenever
    the specification allows other iterators to be invalidated.

I know of more than one vector<> implementation which changes end()
    each time it resizes, and would not be surprised if all current
    vector<> implementations do this.


---
[ 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                       ]

Christoph> My question is short and simple: is the member function
Christoph> end() of the standard containers supposed to return a
Christoph> constant iterator, i.e. one that does never change even if
Christoph> the container is changed?

No.

Christoph> To make it perhaps clearer: I don't want to ask whether
Christoph> end() is the same for all container instances, but whether
Christoph> it retains the same value for each specific container
Christoph> instance during program execution.

Not in general.  It is easy to imagine implementations that would
cause the value of end() to remain constant, but nothing in the standard
requires implementations to work that way.


--
Andrew Koenig, ark@acm.org

---
[ 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                       ]

Christoph Schulz wrote:
> Hello!
>
> My question is short and simple: is the member function end() of the
> standard containers supposed to return a constant iterator, i.e. one
> that does never change even if the container is changed?
>
> To make it perhaps clearer: I don't want to ask whether end() is the
> same
> for all container instances, but whether it retains the same value for
> each
> specific container instance during program execution.
>
> I've found nothing in the Standard that treates end() as a special
> case. So I'm inclined to think that end() is an ordinary iterator that
> may be invalidated when the specification allows iterators to be
> invalidated.
>
> Can anyone confirm that?
>

Yep, the end() pointer can certainly be invalidated. For example in the
most obvious representation of std::vector, end() points to a piece of
memory one past the end of the assigned variables, so that ++ to an
interator is a simple operation. If end() was treated specially whenever
  ++ was applied to an iterator we would have to perform a special test
to see if we had reached the end of the vector.

Chris

---
[ 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                       ]