In article <3qvp4u$19fe@news.doit.wisc.edu>,
   khan@xraylith.wisc.edu (Mumit Khan) wrote:
>
>looks like another item for STL.newbie guide:
>
>STL_Container::begin() -- returns the *first* item in the container if
>    it exists or end() otherwise.
>STL_Container::end() -- returns one-past the end of the container.

If this is going in a newbie guide, let's replace "returns..." with "returns
an iterator positioned at...", else the newbie will get really confused.
:-)


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Herb Sutter                 2228 Urwin, Ste 102         voice (416) 618-0184
Connected Object Solutions  Oakville ON Canada L6L 2T2    fax (905) 847-6019

There have been some discussion on what vec.end() should return but
this is perhaps not so controversial, an iterator referring to the
element following the last in vec. In this case a pointer could be used
to represent the iterator.

More interesting (from an implementation point of view) is perhaps what
should be used to represent vec.rend(). To use a pointer to the element
preceeding the first would be illegal, if there was not a dummy (not
used) element first in the store used for vec. Other options are to
represent vec.rbegin() with 0 and handle the so by introduced
singularity in the code that moves around the iterator or one could
represent the iterator as an index to vec (type unsigned e.g.) which is
legal for any value it can contain.

It would be interesting to know what representation is used in real
implementations of stl iterators.


Jonas Nygren

In article <3qttn7$m8q@keystone.intergate.net> scherrey@proteus-tech.com (Benjamin Scherrey) writes:

     I'm having some difficulties using the set and multiset containers from
   the STL. I'm using HP's code with Borland's OS/2 C++ compiler 2.0. I've
   tracked down one of the problems to a possible misunderstanding of what the
   end() method is supposed to return.

What the end() function returns is (like the actual implementation of
the iterator) is an implementation detail.  The only requirement is
functional.  end() has to return a "past-the-end value".

(Don't confuse the STL spec with the free implementation/s available.)

Quoting the WP:

23.1  Container requirements              [lib.container.requirements]
[...]
4 begin() returns an iterator referring to the first element in the con
  tainer.  end() returns an iterator which is the past-the-end value.


24.1  Iterator requirements                [lib.iterator.requirements]
[...]
5 Just as a regular pointer to an  array  guarantees  that  there  is  a
  pointer  value pointing past the last element of the array, so for any
  iterator type there is an iterator value that  points  past  the  last
  element  of  a corresponding container.  These values are called past-
  the-end values.  Values of an iterator i for which the  expression  *i
  is defined are called dereferenceable.  The library never assumes that
  past-the-end values are dereferenceable.
[...]
 24.1.1  Input iterators                          [lib.input.iterators]
 Table 3--Input iterator requirements
[r is an iterator of type X]
------------------------------------------------------------------------------
expression    return type                     assertion/note
+----------------------------------------------------------------------------+
|++r          X&                              pre: r is dereferenceable.     |
|                                             post: r is dereferenceable or  |
|                                             r is past-the-end.             |
|                                             &r == &++r.                    |
+----------------------------------------------------------------------------+

[end extract]

Plus the (implicit in 24.1.[67]) requirement that the past-the-end iterator is
reachable (by a finite number of operator++() calls) from any
dereferenceable operator.

The past-the-end value can be implemented however the STL writer
desires: a flag in the iterator, a pointer to a global sentinal
object, address arithmetic trickery, whatever.

Nit for WP junkies: it doesn't appear to be explicit in the WP that
operator++() on an iterator pointing to the "last" item in a container
returns the past-the-end value.  And it doesn't specify whether the
past-the-end value is portable across containers - which it most
definitely is not, in general, even for containers of the same type.

Greg.
--
Gregory Bond <gnb@bby.com.au> Burdett Buckeridge & Young Ltd Melbourne Australia
  The "typical user" couldn't spell C1 if you spotted him a letter and
  offered to sell him the digit for a reasonable price.
 -- Casey Schaufler (<casey@orange.engr.sgi.com>), on C1 secure UNIX OS

In article <3r295v$b88@keystone.intergate.net>,
Benjamin Scherrey <scherrey@proteus-tech.com> wrote:
>
> I think the container/iterator should have an is_null() method. The
>container should have one default constructed instance of the class which the
>iterator would point to when it goes past the end. The is_null method should
>compare the address of the null object to determine its result. The "null
>object" would not actually be contained in the primitive container (list,
>tree, what ever) so you would not iterate through it, nor would it conflict
>with any items that might actually be default constructed instances. The main
>benifit of this would be the ability to dereference the null object without
>worrying about causing a memory fault.
>

Yes, it would be nice under *some* circumstances to be able to *always*
dereference an iterator, but I don't see enough justification to make
the containers and iterators more complicated that these already are.
For example, with my own now-defunct-in-favor-of-STL container library,
I used to be able to do the following:

    void foo(Iterator<T> iter) {
 for(; iter.ok(); ++iter) {
     bar(*iter);
 }
    }

now, all I have to (and I find it more general because I can specify a
narrower range now) is:

    void foo(Iterator<T> start, Iterator<T> finish) {
 for(; start != finish; ++start) {
     bar(*start);
 }
    }

Unfortunately, the following bug is usually not detected by run-time
memory checkers:

    vector<int> vector1;
    vector1.push_back(5);

    cerr << "vector1[first]: " << *vector1.begin() << endl;
    cerr << "vector1[last]: " << *vector1.end() << endl;

because the vector container usually allocates more memory than it needs
to avoid new'ing everytime you add something to it. But having is_null(),
unless you change the end() semantics is not going help here. The only
hope here is that reasonable coding discipline should be able to
prevent bugs resulting from dereferencing an invalid iterator (and of
course I'm so disciplined that I never make these mistakes :-)

It'd be helpful for me if you could put together a simple example where
your proposed addition is essential.

regards,
mumit -- khan@xraylith.wisc.edu
http://www.xraylith.wisc.edu/~khan/

ps: I usually CC: the person(s) I'm responding to, but some (not you) have
mentioned that they find it offensive (and I do it out of courtesy), so I'll
refrain from doing so from now on.

In article <3qttn7$m8q@keystone.intergate.net>,
Benjamin Scherrey <scherrey@proteus-tech.com> wrote:
>
> I'm having some difficulties using the set and multiset containers from
>the STL. I'm using HP's code with Borland's OS/2 C++ compiler 2.0. I've
>tracked down one of the problems to a possible misunderstanding of what the
>end() method is supposed to return. Should it return an iterator pointing to
>the last item in the set or an iterator pointing to some "end of file" object?

 Neither.

 The "end()" iterator is not dereferencable -- you may
not dereference it. It has the property

 for (iterator i = begin(); i != end(); i++);

is guarranteed to terminate for a finite container. Thats it.
In English, if begin() isn't equal to end(), you can make it equal
by a finite number of increments.

The best way to understand "end()" is that it is exactly bit
needed to make the comparison of the above "for" loop work.

*** of course there is no requirement for finiteness if one
is reading a continuously open socket or something: then
the loop would (correctly) run forever.

--
        JOHN (MAX) SKALLER,         INTERNET:maxtal@suphys.physics.su.oz.au
 Maxtal Pty Ltd,
        81A Glebe Point Rd, GLEBE   Mem: SA IT/9/22,SC22/WG21
        NSW 2037, AUSTRALIA     Phone: 61-2-566-2189

 I'm having some difficulties using the set and multiset containers from
the STL. I'm using HP's code with Borland's OS/2 C++ compiler 2.0. I've
tracked down one of the problems to a possible misunderstanding of what the
end() method is supposed to return. Should it return an iterator pointing to
the last item in the set or an iterator pointing to some "end of file" object?
My assumption is that it *should* point to the last item in the container.
Unfortunately, it's pointing to some non-existent item *and* it definately
has not allocated any NULL instance of the class because my default
constructor for the item's class specifically initializes all the data to 0
and the item being returned has random data in it.
 Appreciate all replies!

//
// Benjamin Scherrey        Proteus Technologies, Inc.
// scherrey@proteus-tech.com       (404) 454-1013v 986-9876f
//

In article <3qttn7$m8q@keystone.intergate.net> scherrey@proteus-tech.com (Benjamin Scherrey) writes:

>  I'm having some difficulties using the set and multiset
> containers from the STL. I'm using HP's code with Borland's OS/2 C++
> compiler 2.0. I've tracked down one of the problems to a possible
> misunderstanding of what the end() method is supposed to
> return. Should it return an iterator pointing to the last item in
> the set or an iterator pointing to some "end of file" object?

It should return an iterator that is one element past the end of the
container.  That is: end() does not point to a valid container
element.

When you think about it, it has to be this way.  What would end() mean
for an empty container otherwise, and how would you use a pair of
iterators to represent an empty range?

--
Matt Austern          matt@physics.berkeley.edu
http://dogbert.lbl.gov/~matt

It returns "one past" the end of the container, which *not does* point to
a valid container item. This has to be this way for code like the
following to work:

    MyMap::const_iterator it = my_map.find(key);
    if (it == my_map.end())
 no_such_key();
    else
 found_key();

or,

    bool empty(const STL_Container& container) {
 return container.begin() == container.end();
    }

Remember that STL tries to emulate C pointer semantics (or at least as
faithfully as it possibly can), and end() returns something analogous
to a 0 pointer in C.

looks like another item for STL.newbie guide:

STL_Container::begin() -- returns the *first* item in the container if
    it exists or end() otherwise.
STL_Container::end() -- returns one-past the end of the container.

regards,
mumit -- khan@xraylith.wisc.edu
http://www.xraylith.wisc.edu/~khan/

In article <3qttn7$m8q@keystone.intergate.net>, scherrey@proteus-tech.com (Benjamin Scherrey) writes:
>
>  I'm having some difficulties using the set and multiset containers from
> the STL. I'm using HP's code with Borland's OS/2 C++ compiler 2.0. I've
> tracked down one of the problems to a possible misunderstanding of what the
> end() method is supposed to return. Should it return an iterator pointing to
> the last item in the set or an iterator pointing to some "end of file" object?
> My assumption is that it *should* point to the last item in the container.
> Unfortunately, it's pointing to some non-existent item *and* it definately
> has not allocated any NULL instance of the class because my default
> constructor for the item's class specifically initializes all the data to 0
> and the item being returned has random data in it.
>  Appreciate all replies!
>

 interator end()

 returns an interator positioned immediatedly after the last item
 in the container.

 this follows the semantics of vector interators:

 int example[5];
 for (int i=0;i != 5;i++) cout << example[i];

 the value of example[5] is also undefined.

jon borden
jabr technology corporation
component medical software

> //
> // Benjamin Scherrey        Proteus Technologies, Inc.
> // scherrey@proteus-tech.com       (404) 454-1013v 986-9876f
> //
>

In article <3r07sm$1a9@keystone.intergate.net>,
Benjamin Scherrey <scherrey@proteus-tech.com> wrote:
>In message <3qvp4u$19fe@news.doit.wisc.edu> - khan@xraylith.wisc.edu (Mumit
>Khan) writes:
>:>Remember that STL tries to emulate C pointer semantics (or at least as
>:>faithfully as it possibly can), and end() returns something analogous
>:>to a 0 pointer in C.
>
> This seems reasonable but I wish it would return a default constructed
>object. This obviously isn't happening and I'm getting complete garbage.
>Would be nice to have it return a "null" object, IMHO. Also, am I missing
>something or is this fact not documented in the ANSI draft? I couldn't find
>it (thus my previous message)!
>

Yes, it's documented in the ANSI draft. Take a look at secs. 23.1.4
[lib.containers.requirements] and 24.1.5 [lib.iterators.requirements].
The first one says that each container must support begin() and end()
and the corresponding meanings of what they are, and the second ref
gives a bit more info on past-the-end iterator value.

If end() were to return a default constructed object, how would you know
if you've reached the end? (I'm assuming you're checking to see if you've
reached the end of the container or some such thing) What if there are
other objects in the container that are not different than the default?

regards,
mumit -- khan@xraylith.wisc.edu
http://www.xraylith.wisc.edu/~khan/