The need for a NULL iterator (more precisely, a default-constructed iterator
that can be legally compared with other iterators for equality) is a
legitimate one. Sometimes, there isn't an appropriate container handy from
which to extract end().

-Dave

"Bill Wade" <billwade@wt.net> wrote in message
news:39921378_5@data.wt.net...
> "Brian Parker" <brianjparker@ozemail.com.au> wrote
>
> > The problem I most recently needed a null value for was something like
> > this- [ example that needs many trivial iterators into a list (for
reasons
> that aren't entirely clear, but are plausible) or a NULL iterator
>
> For your example as given you can use B.end() for your NULL value.
> list::end() is not invalidated by erase(), and it is distinguished from
all
> of your "valid" trivial iterators.
>
> HTH
>
>
>
> ---
> [ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]
>

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

(my apologies for my delay in responding to this thread)

On Tue, 1 Aug 2000 21:04:00 CST, ark@research.att.com (Andrew Koenig)
wrote:

>In article <39856156.1414119@news.ozemail.com.au>,
>Brian Parker <brianjparker@ozemail.com.au> wrote:
>
>>Given that any iterator implementation will use pointers internally,
>>it should always be possible to implement a distinguished null value
>>for an STL iterator.
>
>Why do you think that iterator implementations will always use pointers?

I was thinking particularly of iterators into the standard library
containers. I should have been more specific- I don't think that the
requirement for a distinguished null value should be a requirement on
all iterators, but should be specified on a per container basis.

>
>And if they do use pointers, why do you think that a distinguished
>null value is always possible?  Consider an iterator over a singly linked
>list.  For such a data structure, a zero pointer is the logical
>off-the-end value.  If you want to mandate a separate null pointer,
>then the implementation problem just became much harder.

Good point. Perhaps I was also overspecifying when I said I needed a
distinguished singular value- in fact a distinguished value that may
also compare equal to the off-the-end iterator would also work for me
(I am not using the iterator to iterate over a range- I am simply
using it to point to a particular element).

>
>>One way this could be mandated is to have the standard ensure that
>>default constructed iterators always compare equal (or, equivalently,
>>that all iterators are default constructed to the distinguished null
>>value). although this would rule out using raw pointers to implement
>>iterators.
>
>Exactly.  So that possibility is ruled out.

Actually, as Bill Wade pointed out, I was wrong about that- it would
work fine for  raw pointer implementations as well.

>
>>Another possibility would be to define standard set_null(iterator&)
>>and is_null(iterator) functions.
>
>>Has anyone else similarly found a need for a null iterator value, or
>>is there some mechanism to achieve the same effect that I have
>>overlooked?
>
>How about showing us a small program that you think requires null
>iterators, and giving us a chance to rewrite it into one that doesn't?

The problem I most recently needed a null value for was something like
this-

I have a graph data structure consisting of a list of edges which
themselves point to vertex data structures

struct vertex;

struct edge {

 vertex* p;
};

struct vertex {

 // ....

 list<edge>::iterator multiple_edge;  // used to find duplicate
edges
};


// code to populate B elided

list<edge> B;

Now, I need to remove multiedges that point to the same vertex in
linear time from B  (i.e. I can't sort the list and then do an
adjacent_find), so I  iterate over B and p->multiple_edge is checked
and if it is null then it is set to point back to the edge; if
p->multiple_edge is not null then this must be the second occurrence
and so we can erase *(p->multiple_edge) to remove the duplicate edge.

i.e.
 for (list<edge>::iterator it = B.begin(); it != B.end();) {

 if (it->p->multiedge == list<edge>::iterator() ) {
 // assuming list<edge>::iterator() was required by the
standard to be the null value
  it->p->multiedge = it;
  ++it;
 } else {
  it = B.erase(it);
 }
}

Note: vertices number in the 100000's, so I would prefer not to add a
redundant bool flag to it indicating when the iterator was null.


The underlying problem here, I think, is that there are two distinct
iterator concepts used with container classes-

(1) An "iterator" used simply to locate an element e.g. the iterator
argument to erase( ) (what I call a "container trivial iterator"
(similar to the "trivial iterator" concept in the SGI STL except that
it must also point into a container); called an "item" in the LEDA
library).

(2) An iterator over a range (which can be subclassified into forward,
reverse etc).

,and the standard containers do not distinguish these two concepts and
use the same iterator type for both roles (quite correctly- there is
probably little benefit in distinguishing them for the standard
containers, whereas for other more complex container types such as
modifiable priority queues it is essential to distinguish them).

A null value is only useful when using iterators for concept (1)
above, whereas most uses of iterators in the standard containers are
(2), and so the benefit of a null value for role (1) has been
overlooked.

Of course, the lack of a null value is only a minor nuisance in the
grand scheme of things, but given that a null value could be easily
guaranteed for the standard library containers' iterators, I think it
would be a worthwhile addition.

,Brian Parker
(brianp@research.canon.com.au)

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Brian Parker" <brianjparker@ozemail.com.au> wrote

> The problem I most recently needed a null value for was something like
> this- [ example that needs many trivial iterators into a list (for reasons
that aren't entirely clear, but are plausible) or a NULL iterator

For your example as given you can use B.end() for your NULL value.
list::end() is not invalidated by erase(), and it is distinguished from all
of your "valid" trivial iterators.

HTH



---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Brian Parker <brianjparker@ozemail.com.au> a    crit dans le message :
399179ba.1616117@news.ozemail.com.au...
> On Thu,  3 Aug 2000 18:12:22 GMT, "Hicham BOUHMADI"
> <hicham@citeweb.net> wrote:
>
[...]
> >This raises another question:
> >    Is the iterator exist by itself without any range?
> >
> I think the answer is yes. There are two iterator concepts here
> (1) An "iterator" used simply to identify a single element (what I
> call a container trivial iterator) e.g. the iterator argument to
> erase( )

But this kind of iterators identify a single element over a range!
you get this kind of iterators from the container and not from the iterator
itself.

Hicham BOUHMADI                hicham@citeweb.net




---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Thu,  3 Aug 2000 18:12:22 GMT, "Hicham BOUHMADI"
<hicham@citeweb.net> wrote:

>Hi!
>I think if we use the iterators the way they was designed for, we should not
>need any null value.
>An iterator iterates over a range: a semi-opened interval.
>It is always valid unless it is past the end iterator (which is also valid
>but you should not dereference it).
>(To simplify things: I am talking only about ONE iterator over a range)
>
>This raises another question:
>    Is the iterator exist by itself without any range?
>
I think the answer is yes. There are two iterator concepts here
(1) An "iterator" used simply to identify a single element (what I
call a container trivial iterator) e.g. the iterator argument to
erase( )
(2) An iterator over a range.

The standard containers resuse the same type for both roles. A null
value is only needed for (1). I agree that for (2) it is of no use.

>If the answer is NO (which is my opinion). Then why iterators are default
>constructible?
>We should retrieve an iterator only from the range (in other words, the
>container).
>==> there is no NULL iterator. only valid or past-the-end iterator!!!

Brian Parker,
(brianp@research.canon.com.au)

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Wed, 2 Aug 2000 03:55:01 CST, "Bill Wade" <bill.wade@stoner.com>
wrote:

>I believe it is possible to provide distinguished values for any iterator
>implementation that does use pointers internally (since all
>pointer-to-structures "smell" alike, you can get distinguished pointers by
>pointing at static structures).  If you don't mind having an extra container
>around you can do this yourself for each container type:
>
>template<class Sequence> typename Sequence::iterator Null()
>{
>  static Sequence s(1);
>  return s.begin();
>}
>
>    if(my_iterator == Null<vector<int> >())
>       do_something_wonderfull();

Yes, quite clever. That would do in a pinch.

>
>However iterators don't necessarily contain pointers (although in practice
>almost all iterators do).  As a trivial example, I can write an input
>iterator that returns the infinite sequence 0,1,2,...255,0,1,2,... . My
>iterator doesn't need any internal pointers, and a requirement that it have
>a "distinguished" NULL value would cost me some space.  Likewise, an
>iterator into a singleton container doesn't need any pointers.

It's really only iterators into containers used simply to point to a
single element (what I call a container trivial iterator) that I am
concerned with having a null value, not more general range iterators.

>
>I suspect the main reason NULL iterators aren't mandated is that the STL
>authors didn't think they were worth the trouble.  They have very little
>benefit for the existing STL components.
>

The STL containers don't have a separate type for an iterator used
simply to locate an element (e.g. for deletion) and reuse the more
general range iterator for this- I agree that iterators over a range
have no use for a null value.

>> One way this could be mandated is to have the standard ensure that
>> default constructed iterators always compare equal (or, equivalently,
>> that all iterators are default constructed to the distinguished null
>> value). although this would rule out using raw pointers to implement
>> iterators.
>
>Raw pointers work with this notation:
>   vector<T>::iterator it = vector<T>::iterator();

Yes, and that is the syntax I was hoping to use. As you point out, it
will in fact work with iterators implemented as raw pointers
(actually, the current STL implementations probably do what I want
anyway- but I need a guarantee of the behaviour).

>
>Requiring default-constructed iterators to have a distinguished NULL value
>would break the istream iterators' interface, which uses
>default-construction to indicate end().

Yes, null values are really only relevant for trivial iterators into a
container.

>
>> Another possibility would be to define standard set_null(iterator&)
>> and is_null(iterator) functions.
>>
>> Has anyone else similarly found a need for a null iterator value, or
>> is there some mechanism to achieve the same effect that I have
>> overlooked?
>
>For any data type (int,string,double) there are times when you want one or
>more distinguished out-of-band values.  The only general solution seems to
>be a flag.

Unfortunately, that implies that using the standard container classes
and their iterators will be at a space disadvantage compared with an
implementation using raw pointers.

Thanks for your comments,
Brian Parker
(brianp@research.canon.com.au)

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Thu,  3 Aug 2000 14:10:02 CST, Anders Pytte <anders@milkweed.com>
wrote:

>Since a NULL iterator would break the semantics of the library, why not use
>a pair<bool, iterator> to express the same idea? There is already no
>guarantee that a "stale" iterator will be valid, so i don't see any added
>danger in this solution.

Unfortunately, this would double the memory cost over using a raw
pointer, which is very significant in the algorithm I am implementing.

,Brian Parker
(brianp@research.canon.com.au)

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

in article 3986108E.703A781C@research.canon.com.au, Brian Parker at
brianp@research.canon.com.au wrote on 8/1/00 11:58 AM:

> Tom wrote:
>
>>
>> It seems to me that if you store iterators, then it is because you will
>> use them to iterate. If this is the case, you will need to know the
>> valid range of each iterator (i.e. what the container's begin and end
>> are), to avoid over-iterating. So you can just store .end() as
>> the "null" iterator.
>>
>> If you will not be iterating (or using algorithms or whatever), then
>> just store pointers instead.
>>
>
> The problem is that the one-past-the-end iterator is not constant- it varies
> as elements are inserted into the container- and so can't take the place of a
> fixed null value.
>
> In my application I am not iterating, but I do need a full iterator into the
> container to do deletions etc. (i.e. I am using the iterators only as trivial
> iterators to use the SGI STL term, or items to use the LEDA term), and so raw
> pointers will not do.

Since a NULL iterator would break the semantics of the library, why not use
a pair<bool, iterator> to express the same idea? There is already no
guarantee that a "stale" iterator will be valid, so i don't see any added
danger in this solution.

Anders.

--
Anders Pytte                                   Milkweed Software
PO Box 32                                  voice: (802) 586-2545
Craftsbury, VT 05826                  email: anders@milkweed.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi!
I think if we use the iterators the way they was designed for, we should not
need any null value.
An iterator iterates over a range: a semi-opened interval.
It is always valid unless it is past the end iterator (which is also valid
but you should not dereference it).
(To simplify things: I am talking only about ONE iterator over a range)

This raises another question:
    Is the iterator exist by itself without any range?

If the answer is NO (which is my opinion). Then why iterators are default
constructible?
We should retrieve an iterator only from the range (in other words, the
container).
==> there is no NULL iterator. only valid or past-the-end iterator!!!

Hicham BOUHMADI                hicham@citeweb.net

PS: I liked the example given by Bill Wade about an iterator over an
infinite range. It's not a very common iterator :-)

Brian Parker <brianjparker@ozemail.com.au> a    crit dans le message :
39856156.1414119@news.ozemail.com.au...
> >From time to time I have found that I would like to have a
> distinguished singular value for iterators i.e. the equivalent to 0
> for a pointer, e.g. this need arises when iterators to a container are
> stored as part of a structure and these member iterators need to be
> flagged when they are uninitialised or otherwise invalid.
>
> If I was using raw pointers I could simply assign 0, but for iterators
> I need to add a redundant bool flag member to indicate this.
>
> Given that any iterator implementation will use pointers internally,
> it should always be possible to implement a distinguished null value
> for an STL iterator.
>
> One way this could be mandated is to have the standard ensure that
> default constructed iterators always compare equal (or, equivalently,
> that all iterators are default constructed to the distinguished null
> value). although this would rule out using raw pointers to implement
> iterators.
>
> Another possibility would be to define standard set_null(iterator&)
> and is_null(iterator) functions.
>
> Has anyone else similarly found a need for a null iterator value, or
> is there some mechanism to achieve the same effect that I have
> overlooked?
>
> ,Brian Parker
> (brianp@research.canon.com.au)
>
>
> ---
> [ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]
>


---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

>From time to time I have found that I would like to have a
distinguished singular value for iterators i.e. the equivalent to 0
for a pointer, e.g. this need arises when iterators to a container are
stored as part of a structure and these member iterators need to be
flagged when they are uninitialised or otherwise invalid.

If I was using raw pointers I could simply assign 0, but for iterators
I need to add a redundant bool flag member to indicate this.

Given that any iterator implementation will use pointers internally,
it should always be possible to implement a distinguished null value
for an STL iterator.

One way this could be mandated is to have the standard ensure that
default constructed iterators always compare equal (or, equivalently,
that all iterators are default constructed to the distinguished null
value). although this would rule out using raw pointers to implement
iterators.

Another possibility would be to define standard set_null(iterator&)
and is_null(iterator) functions.

Has anyone else similarly found a need for a null iterator value, or
is there some mechanism to achieve the same effect that I have
overlooked?

,Brian Parker
(brianp@research.canon.com.au)


---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <39856156.1414119@news.ozemail.com.au>,
  brianjparker@ozemail.com.au (Brian Parker) wrote:
> >From time to time I have found that I would like to have a
> distinguished singular value for iterators i.e. the equivalent to 0
> for a pointer, e.g. this need arises when iterators to a container are
> stored as part of a structure and these member iterators need to be
> flagged when they are uninitialised or otherwise invalid.
>
> If I was using raw pointers I could simply assign 0, but for iterators
> I need to add a redundant bool flag member to indicate this.
>
> Given that any iterator implementation will use pointers internally,
> it should always be possible to implement a distinguished null value
> for an STL iterator.
>
> One way this could be mandated is to have the standard ensure that
> default constructed iterators always compare equal (or, equivalently,
> that all iterators are default constructed to the distinguished null
> value). although this would rule out using raw pointers to implement
> iterators.
>
> Another possibility would be to define standard set_null(iterator&)
> and is_null(iterator) functions.
>
> Has anyone else similarly found a need for a null iterator value, or
> is there some mechanism to achieve the same effect that I have
> overlooked?

It seems to me that if you store iterators, then it is because you will
use them to iterate. If this is the case, you will need to know the
valid range of each iterator (i.e. what the container's begin and end
are), to avoid over-iterating. So you can just store .end() as
the "null" iterator.

If you will not be iterating (or using algorithms or whatever), then
just store pointers instead.

Tom


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Tom wrote:

>
> It seems to me that if you store iterators, then it is because you will
> use them to iterate. If this is the case, you will need to know the
> valid range of each iterator (i.e. what the container's begin and end
> are), to avoid over-iterating. So you can just store .end() as
> the "null" iterator.
>
> If you will not be iterating (or using algorithms or whatever), then
> just store pointers instead.
>

The problem is that the one-past-the-end iterator is not constant- it varies
as elements are inserted into the container- and so can't take the place of a
fixed null value.

In my application I am not iterating, but I do need a full iterator into the
container to do deletions etc. (i.e. I am using the iterators only as trivial
iterators to use the SGI STL term, or items to use the LEDA term), and so raw
pointers will not do.

,Brian Parker
(brianp@research.canon.com.au)


---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Brian Parker" <brianjparker@ozemail.com.au> wrote in message
news:39856156.1414119@news.ozemail.com.au...
> >From time to time I have found that I would like to have a
> distinguished singular value for iterators i.e. the equivalent to 0
> for a pointer, e.g. this need arises when iterators to a container are
> stored as part of a structure and these member iterators need to be
> flagged when they are uninitialised or otherwise invalid.
>
> If I was using raw pointers I could simply assign 0, but for iterators
> I need to add a redundant bool flag member to indicate this.
>
> Given that any iterator implementation will use pointers internally,
> it should always be possible to implement a distinguished null value
> for an STL iterator.

I believe it is possible to provide distinguished values for any iterator
implementation that does use pointers internally (since all
pointer-to-structures "smell" alike, you can get distinguished pointers by
pointing at static structures).  If you don't mind having an extra container
around you can do this yourself for each container type:

template<class Sequence> typename Sequence::iterator Null()
{
  static Sequence s(1);
  return s.begin();
}

    if(my_iterator == Null<vector<int> >())
       do_something_wonderfull();

However iterators don't necessarily contain pointers (although in practice
almost all iterators do).  As a trivial example, I can write an input
iterator that returns the infinite sequence 0,1,2,...255,0,1,2,... . My
iterator doesn't need any internal pointers, and a requirement that it have
a "distinguished" NULL value would cost me some space.  Likewise, an
iterator into a singleton container doesn't need any pointers.

I suspect the main reason NULL iterators aren't mandated is that the STL
authors didn't think they were worth the trouble.  They have very little
benefit for the existing STL components.

> One way this could be mandated is to have the standard ensure that
> default constructed iterators always compare equal (or, equivalently,
> that all iterators are default constructed to the distinguished null
> value). although this would rule out using raw pointers to implement
> iterators.

Raw pointers work with this notation:
   vector<T>::iterator it = vector<T>::iterator();

Requiring default-constructed iterators to have a distinguished NULL value
would break the istream iterators' interface, which uses
default-construction to indicate end().

> Another possibility would be to define standard set_null(iterator&)
> and is_null(iterator) functions.
>
> Has anyone else similarly found a need for a null iterator value, or
> is there some mechanism to achieve the same effect that I have
> overlooked?

For any data type (int,string,double) there are times when you want one or
more distinguished out-of-band values.  The only general solution seems to
be a flag.

HTH


---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]