This issue seems to break iterators.  Maybe someone can show me what
is wrong with my reasoning.

The term "singular" has two meanings.  In common use, it means unique.
In technical terms it means unusual or unusable.  A singular matrix
does not have an inverse.  The identity matrix is unique, but not
singular.  A function may have many singularities.

24.1/5 defines a singular iterator as having no usable value by
analogy to an uninitialized pointer.  The only operation allowed
for a singular iterator is assigning a non-singular value to it.

int i[10] = { 0 };
int* ib(i);          // dereferenceable
int* ie(i + 10);     // past-the-end
int* is;             // singular
int* in(0);          // null

typedef vector<int>::iterator iter;
vector<int> v(10, 42);
iter vb(v.begin());  // dereferenceable
iter ve(v.end());    // past-the-end
iter vs;             // singular
There is no concept of null iterator.

The only use of singular outside of this paragraph is in table 74 where
it states that a default constructed forward (bidirectional,
random_access) iterator might be singular.

The goal of this DR is to allow unique values to serve as past-the-end
iterators.  I find nothing in the standard to prohibit this.  In fact,
istream_iterator<int>() is a unique iterator which is a valid
past-the-end iterator for any istream_iterator<int> range, regardless of
the stream.  It is unique, not singular.

The rational notes that null pointers are clearly singular in
contradiction to the definition given.  An empty vector which uses
pointers for iterators may well provide a null pointer as an end
and begin iterator.  They are comparable which is not allowed for
singular iterators.  No problem.  It also mentions using a null
pointer for a singly linked list.  I doubt that a singly linked
list can use raw pointers as iterators.  The iterator type may
well use a null pointer internally for past-the-end much like
istream_iterator.

Given the definition of singular iterator, it is not possible to
return a past-the-end iterator which is singular for any container.

Why are past-the-end iterators now allowed to be singular (unusable)?

It may be a minor defect that "singular" is not in italics at its
first use where it is defined.

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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

John Potter wrote:
[Re: DR 208]
> Why are past-the-end iterators now allowed to be singular (unusable)?

For reference:
<http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#208>

That web page starts by saying "This document contains only library
issues which have been closed by the Library Working Group (LWG) after
being found to be defects in the standard." That sounds like report has
been accepted as valid, and that the proposed solution will be in the
next update to the standard. I hope not. You and I were the only ones to
respond on the newsgroup when Cleary first brought it up in February,
and we both spoke against it, but our comments would seem to have been
ignored. I'd like to know why, if anyone would care to explain it.

To save others the trouble of searching for our responses:

You (John Potter) said:
>  : Removing this restriction would allow, for example, a singly-linked list
>  : without a "footer" node.
>
>  I don't read the standard that way.  The example is
>    int* p;    // singular because it has no known value
>  however
>    int* q(0); // the nul pointer is not singular
>
>  The only operation allowed on a singular pointer/iterator is assignment to.  It may not be compared.
>
>  istream_iterator<char> it; // Not singular
>  It is a universal end iterator for all istream_iterator<char> regardless of the stream.
>
>  Forward_iterator requires a default constructor which _might_ produce a singular value.  It might also not produce a singular value.  That
>  does not mean that the end iterator for slist<T> is not allowed to contain a nul pointer which gives it a non-singular value.  AFAIK, the SGI slist
>  iterator meets all requirements for forward_iterator and uses a nul pointer within the end iterator.
>
>  : This would have an impact on existing code that expects past-the-end
>  : iterators obtained from different (generic) containers being not equal.
>
>  That code is already broken.  The standard does not say that the past the end iterator is unique for each container.

I (James Kuyper) said:
>  > containers with forward iterators (for example, a singly-linked list).  If
>  > the past-the-end value on such a container was a well-known singular value,
>  > it would still satisfy all forward iterator requirements.
>
>  Not really. The only operation that is defined for singular iterator values is their replacement by non-singular values (see 24.1 p6). In
>  particular, comparing a singular iterator to another iterator allows undefined behavior. It's certainly not safe to copy them or assign them. It
>  would be rather embarrasing to define a container where any operation user code performed on container.end() necessarily allowed
>  undefined behavior.
>
>  The canonical example of a singular value is not (T*)NULL. That's a non-singular iterator that happens to also not be dereferencable. The
>  canonical singular iterator is an unitialized pointer. There are real machines where loading an address value into an address register
>  causes that value to be validated. On those machines, loading an uninitialized pointer can causes immediate termination of your program.
>  This is a deliberate safety measure: any program which would attempt to use an uninitialized pointer is (IMO correctly) assumed to be so
>  poorly written that it can't be safely allowed to run.

In addition, a new problem has been added. The original report was aimed
only at forward iterators, and the initially proposed solution said that
containers with bidirectional and random-access iterators would still be
required to have non-singular past-the-end iterators. However, the
proposed solution listed on the web page removes that requirement for
all containers, even reversible ones. This is a problem, since if
c.end() is allowed to be a singular iterator, then the standard allows
--c.end() to have undefined results even if 'c' is a reversible
container with c.size()>0. I doubt that this was intended, or a good
idea.

> It may be a minor defect that "singular" is not in italics at its
> first use where it is defined.

Putting it in italics would make that first use a definition, and it
doesn't have quite the right form to be one. It doesn't define singular
iterators, it merely states that most operations are undefined on
singular iterators. It would need a re-write.

---
[ 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                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

In article <3a3c619c.134280050@news.csrlink.net>,
  jpotter@falcon.lhup.edu (John Potter) wrote:

> This issue seems to break iterators.  Maybe someone can show me what
> is wrong with my reasoning.

> The term "singular" has two meanings.  In common use, it means
> unique.  In technical terms it means unusual or unusable.  A
> singular matrix does not have an inverse.  The identity matrix is
> unique, but not singular.  A function may have many singularities.

In computer science, the most frequent use of singular that I know of
is for an impossible, but testable result -- a function will return a
singular value to indicate an error, for example.  Past the end
iterators are singular, in this sense.

> 24.1/5 defines a singular iterator as having no usable value by
> analogy to an uninitialized pointer.  The only operation allowed
> for a singular iterator is assigning a non-singular value to it.

This sounds like a misuse of singular.  An uninitialized pointer is
NOT a singular value, and I suspect that the intent here is that the
default constructor be allowed to not initialize the internal data of
the iterator.  The only singular pointer is a null pointer, at least
in sense that I understand singular.

I would replace the word "singular" with "invalid", or even
"uninitialized" values in this paragraph.  (Normally, I would prefer
"uninitialized", but this word has a very special meaning in C++ -- a
variable is never "uninitialized" if a constructor has been called on
it.)  "Unusable" might be another alternative.

> int i[10] = { 0 };
> int* ib(i);          // dereferenceable
> int* ie(i + 10);     // past-the-end
> int* is;             // singular
> int* in(0);          // null

> typedef vector<int>::iterator iter;
> vector<int> v(10, 42);
> iter vb(v.begin());  // dereferenceable
> iter ve(v.end());    // past-the-end
> iter vs;             // singular
> There is no concept of null iterator.

> The only use of singular outside of this paragraph is in table 74
> where it states that a default constructed forward (bidirectional,
> random_access) iterator might be singular.

It might be.  It might also be anything else, I think.  I imagine what
they wanted to say is that the value of a default constructed iterator
isn't specified, and might not be valid/initialized/usable.

Having used singular for this in the preceding paragraph, the use here
is only being consistant.

> The goal of this DR is to allow unique values to serve as
> past-the-end iterators.  I find nothing in the standard to prohibit
> this.  In fact, istream_iterator<int>() is a unique iterator which
> is a valid past-the-end iterator for any istream_iterator<int>
> range, regardless of the stream.  It is unique, not singular.

So where is the defect?  Any use of a default constructed iterator
(except assigning to it) is undefined behavior, which means that the
implementation can do whatever it wants.  Including recognizing it as
a past-the-end iterator.  For the moment, no implementation does
this.  Even if one did, you couldn't use the fact in portable code.
And the fact that an implementation did it won't make user defined
iterators follow the rule.

I'm not sure what you want.  I like the idea, but it would only be
usable if it were added to the iterator requirements: an iterator
constructed with the default constructor must compare equal to all
past-the-end iterators.  At which point, we'd probably want to reflect
on what equality means for iterators -- just introducing this rule,
without changing anything else, means that == is no longer an
equivalence relationship over the iterators.  (Is == guaranteed to be
an equivalence relationship now?  What if I compare iterators from
different containers?)  It will definitely introduce some complexity
into the implementation of an iterator.  And of course, introducing
this rule means that pointers are NOT legal iterators, since you
cannot compare a default constructed pointer, and even a null pointer
will not normally compare equal to a past-the-end pointer.

> The rational notes that null pointers are clearly singular in
> contradiction to the definition given.

But in agreement with the usual use of the word:-).

> An empty vector which uses pointers for iterators may well provide a
> null pointer as an end and begin iterator.  They are comparable
> which is not allowed for singular iterators.

It is impossible for a program to know whether an iterator is "valid"
or not unless it creates the iterator itself.  If the implementation
defines certain behavior for a specific, otherwise invalid iterator,
it is free to exploit this behavior, as long as a conforming program
cannot tell the difference.

I'm not sure how far this freedom really goes.  C++ has more or less
adopted the philosophy of C in this regard.  But with template
meta-programming, it is possible to find out much more about the
implementation than in C.  A conforming program CAN tell whether
vector<int>::iterator is a pointer or not, and if it is a pointer, the
implementation can then determine whether it has a null pointer.  But
my impression is that this doesn't matter here.  For an empty vector,
a null pointer supports all of the legal operations, so it is a legal
implementation.  An interesting question would be if the
implementation used reinterpret_cast< int* >( 42 ), for example,
knowing that in fact, copying and comparing the resulting pointer does
not cause strange effects, but given that a conforming program can
acquire the resulting pointer, as a pointer.

> No problem.  It also mentions using a null pointer for a singly
> linked list.  I doubt that a singly linked list can use raw pointers
> as iterators.  The iterator type may well use a null pointer
> internally for past-the-end much like istream_iterator.

> Given the definition of singular iterator, it is not possible to
> return a past-the-end iterator which is singular for any container.

> Why are past-the-end iterators now allowed to be singular (unusable)?

> It may be a minor defect that "singular" is not in italics at its
> first use where it is defined.

The question is whether the correct word is singular.  Of course,
within the standard, it is often necessary to redefine words, for
precision.  If this is the case here, I would feel happier if there
were at least a sentence to the effect that "within this International
Standard, the word singular, when applied to an iterator, means..."
This would make it 100% clear that we are not talking about the
classic sense, in which null pointers are singular (and in which in a
specific context, the past-the-end iterator is singular).

--
James Kanze                               mailto:kanze@gabi-soft.de
Conseils en informatique orient   e objet/
                  Beratung in objekt orientierter Datenverarbeitung
Ziegelh   ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627


Sent via Deja.com
http://www.deja.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                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

James.Kanze@dresdner-bank.com wrote:
> In article <3a3c619c.134280050@news.csrlink.net>,
>   jpotter@falcon.lhup.edu (John Potter) wrote:
...
> > 24.1/5 defines a singular iterator as having no usable value by
> > analogy to an uninitialized pointer.  The only operation allowed
> > for a singular iterator is assigning a non-singular value to it.
>
> This sounds like a misuse of singular.  An uninitialized pointer is
> NOT a singular value, and I suspect that the intent here is that the
> default constructor be allowed to not initialize the internal data of
> the iterator.  The only singular pointer is a null pointer, at least
> in sense that I understand singular.

Which seems to be a different sense than the one used in the standard.

> I would replace the word "singular" with "invalid", or even
> "uninitialized" values in this paragraph.  (Normally, I would prefer
> "uninitialized", but this word has a very special meaning in C++ -- a
> variable is never "uninitialized" if a constructor has been called on
> it.)  "Unusable" might be another alternative.

I think that the prototypical singular iterator, as the term is
currently used in the standard is indeed an unitialized one. If you
default construct a "T*", you get an uninitialized value, and I think
that's exactly what the standard is intending to allow: for some
containers, the iterator_type can be a "T*". By analogy, a class object
used as an iterator is permitted to have a default constructor that
creates an object without bothering to initialize any of its data
members, making it unusable for any purpose except as a destination for
an assignment operation.

...
> > The goal of this DR is to allow unique values to serve as
> > past-the-end iterators.  I find nothing in the standard to prohibit
> > this.  In fact, istream_iterator<int>() is a unique iterator which
> > is a valid past-the-end iterator for any istream_iterator<int>
> > range, regardless of the stream.  It is unique, not singular.
>
> So where is the defect?  Any use of a default constructed iterator

He's pointing out that there is no defect, contrary to the implication
of the "DR" status that's been assigned to issue 208.

...
> I'm not sure what you want.  I like the idea, but it would only be

I believe that he wants the DR to be retroactively labeled not-a-defect,
and that there be no change to the standard. That's certainly my desire.

It probably wouldn't hurt to clarify the matter by replacing the phrase
"singular iterator" with some more appropriate one, such as "unusable
iterator". With this rewording, there would be no need for a separate,
more conventional definition of a "singular iterator" - I don't think
that's there's anything the standard needs to say that would require the
use of that phrase, with it's more conventional definition.

---
[ 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                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

James.Kanze@dresdner-bank.com wrote:
>

>
> The question is whether the correct word is singular.  Of course,
> within the standard, it is often necessary to redefine words, for
> precision.  If this is the case here, I would feel happier if there

The sense that I understood it was as in
http://www.sgi.com/Technology/STL/trivial.html but the standard does not
contain quite the same wording and perhaps either a clarification or a
change in terminology is in order.


Regards, 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On Tue, 19 Dec 2000 18:05:04 GMT, James.Kanze@dresdner-bank.com wrote:

> In article <3a3c619c.134280050@news.csrlink.net>,
>   jpotter@falcon.lhup.edu (John Potter) wrote:
>
> > This issue seems to break iterators.  Maybe someone can show me what
> > is wrong with my reasoning.

> So where is the defect?

That is the question.  I think the defect is accepting issue 208.

> I'm not sure what you want.

I want the standard back where it makes sense.  It seems that this
issue makes past-the-end iterators unusable in an attempt to fix
problems which never existed.

Since it was accepted, maybe someone can show me the error in my
reasoning.  That one sentence taken out of context may seem to be
a defect.  In context, it seems consistent.

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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]