"Andy Sawyer" <news@evo6.com> wrote ...
> In article <qgJE9.102561$up.1110505@news.chello.at>,
>  on Tue, 26 Nov 2002 15:45:48 +0000 (UTC),
>  markus.mauhart@nospamm.chello.at ("Markus Mauhart") wrote:
>
[...]
> Can you please specifiy exactly (section, paragraph) which
> wording in the standard you're referring to?
[...]
> I can't find the wording which you claim supports this expectation,

IMHO a misunderstanding. I did not want to claim that any existing
wording supports this expectation.
Mayby my grammatical error was the comma in the sentence ...
 "But against the current stdc++ wording,... one should be allowed
  to expect".
This was intended to express that ...
(1) ... AFAICS the current wording does not support this expectation[s]
(2) ... I do not like (1) and currently think that the wording could and
  should be improved.
I think we completly agree w.r.t. (1).

> > ... cause this is what we have with normal pointers,
>
> How is this relevant? Not all iterators are pointers   , although they
> do have some very similar properties.

IMHO the similarities did not happen by chance but are intended.
IMHO the properties of pointers have been very relevant during
the design of stdc++.iterators.
Therefore IMHO any significant incompatibility between raw pointers
and certain iterator types needs the justifacation that it (the
incompatibility) might allow to write better programs (faster, easier
to understand or maintain).
I still havn't found an example of a random access iterator which
profits from not providing the following pointer-properties:

  iter i = iter();//defined behaviour even when RHS is singular
  i == i         ;//defined behaviour, result is true.
  iter j = i     ;//defined behaviour
  j == i         ;//defined behaviour, result is true.
  j != i         ;//defined behaviour, result is false.
  iter k = iter();//defined behaviour even when RHS is singular
  k == i         ;//defined behaviour, result is true.
  k != i         ;//defined behaviour, result is false.

> Footnotes:
>      And not all pointers are iterators.

What pointer violates what requirements ?

> In particular, this isn't required to "work":
>
> Iterator iter = Iterator();
> assert( iter == iter );
>
> Since a singular iterator isn't _required_ to compare equal to itself
> (since the results of operator== on a singular value are undefined),

AFAICS even the initialization in the 1st line is not required to work,
cause a potentially singular def-constructed Iterator may be the LHS
of an assignment but not necessary the RHS of copy initialization
(or direct initialization or assignment).
Please note your own cite:
  "Results of most expressions are undefined for singular values;
   the only exception is an assignment of a nonsingular value to
   an iterator that holds a singular value."
For singular values i, *i is likely to be undefined behaviour.
Is "Iterator iter = Iterator();" undefined behaviour or does it only
produce an object with undefined value, like "Iterator iter;" ?

[...]
> > and (for random access iterators) allocator requirements
> > + LWG199's description do refer to entities called
> > '0' or 'null' or '[non-]null pointer',
>
> Allocator requirements and LWG199 refer to allocators, not
> iterators. How is this relevant?

allocator.allocate(..) is required to return a ra-iterator.
(i.e. allocator_type::pointer is a ra-iterator)
Every 20.1.5-dependent library relies on ra-iterator properties.
20.1.5 itself and LWG199 and probably not only my compilers
stdc++ library depend on 'pointers' called '0' or 'null' or
'[non-]null pointer' or initialized with 0 and later compared
with each other and being copyable. So IMHO either all the former
must remove this naive assumptions, or 20.1.5 is missing an
essential requirement, or [lib.iterator.requirements] 24.1 is
missing essential requirements or refined iterator categories.

> > and my compiler's library sometimes initializes ranges,
> > pointers or iterators with '0' (which could be replaced
> > by "0-iterator/pointer" if one had such entity),
>
> It's reasonable for a library implementation to do so - but
> it's not required.

Actually it breaks the libraries expressed intent to do what
20.1.5 suggests:
 "Implementors are encouraged to supply libraries that can accept
  allocators that encapsulate more general memory models"
  (AFAICS 'more general memory models' means alloc::pointer being
  not a raw pointer (but still a ra-iterator))
And about "it's not required" ... how would you implement
std::vector<T,alloc> w/o relying on either alloc::pointer(0)
or better alloc::pointer() having some 0-pointer properties ?
Or what should ~tree_node() do with its maybe-indeterminate
members ?

> Some libraries - quite reasonably - skip this step for performance
> reasons.

IMHO you are wrong here. AFAICS in the cases where the mentioned
library uses 'null pointers' together with type allocator::pointer
(initialization, assignment, equality compare against 0) it's for
better performance or even inavoiadable. The next better option
would be to rely on a dedicated constant static non-singular
pointer/iterator object (called "g_null" ;-). The worst option,
potentially singular objects with indeterminate value, would
need additional expensive and error prone logic (like in many
other cases when one has members of iterator/pointer type).
IMHO there is a long tradition of excellent high performant C and
c++ code carefully using the difference between pointers with
indeterminate value and zero-initialized pointers.

[...]
> I'm not really sure what you're trying to say here. If you want to
> ensure that an iterator may be meaningfully compard to another
> iterator,

Not to _any_ other iterator: all I want is for a 'value-initialized'
iterator to equ-compare reliably to copies of itself or any other
'value-initialized' object of same type, and it should be a reliable
RHS of initialization or assignment of same type.
And for allocators I want "alloc::pointer() == alloc::const_pointer()"
to be true.

> Iterators are not required to have a "0" or "null" representation.

Agreed, but for some kinds of iterators currently I am not sure
whether this is the result of carefull considerations or whether
it is an oversight.


Kind regards,
Markus.



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

Markus Mauhart wrote:
> "Andy Sawyer" <news@evo6.com> wrote ...
....
>>=B9  And not all pointers are iterators.
>=20
>=20
> What pointer violates what requirements ?

None. The iterator requirements were deliberately designed so they were=20
all satisfied by ordinary pointers.

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

"Markus Mauhart"" <markus.mauhart@nospamm.chello.at> wrote ...
>
> "Andy Sawyer" <news@evo6.com> wrote ...
> >
> > If you want to ensure that an iterator may be meaningfully
> >  compard to another iterator,
>
> Not to _any_ other iterator:

Actually you were right :-) while equ-comparing value-initialized
iterators only against each other is my 1st wish, my next
question then would be about equ-comparing them with _any_
non-singular iterator object.


Regards,
Markus.


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

kuyper@wizard.net ("James Kuyper Jr.") wrote in message news:<3DEFEFC2.9040802@wizard.net>...
> Markus Mauhart wrote:
> > "Andy Sawyer" <news@evo6.com> wrote ...
>  ....
> >>   And not all pointers are iterators.
> >
> >
> > What pointer violates what requirements ?
>
> None. The iterator requirements were deliberately designed so they were
> all satisfied by ordinary pointers.
>

This is one of those issues that just keeps coming up.  Pointers are
iterators, and folks keep expecting that the converse is true in that
iterators can be treated the same way that pointers can, which is true
to a large extent, but not completely.  Pointers have a single,
well-defined value that represents a NULL pointer.  That value allows
a pointer to convey an additional bit of information that an iterator
cannot.  It would be nice if every iterator class was required to
provide a zero ctor that would construct a NULL iterator, but,

1) This isn't likely to happen, and,
2) It really just reflects a desire to make iterators be more like
pointers.

The solution is to just stop expecting iterators to be exactly like
pointers and accept them for what they are: a useful abstraction that
is very similar to pointers, but that requires a slightly different
style of use due to the lack of a well-defined NULL value.

Randy.

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

In article <ppNH9.6191$A9.108922@news.chello.at>,
 on Thu, 5 Dec 2002 23:46:20 +0000 (UTC),
 markus.mauhart@nospamm.chello.at ("Markus Mauhart") wrote:


> IMHO a misunderstanding. I did not want to claim that any existing
> wording supports this expectation.
> Mayby my grammatical error was the comma in the sentence ...
>  "But against the current stdc++ wording,... one should be allowed
>   to expect".

If you're now saying what I think you're saying, the error is
(idiomatically) semantic in the use of the word "against".

> This was intended to express that ...
> (1) ... AFAICS the current wording does not support this
>     expectation[s]

In fact, the current wording explicitly says that your expectation is
not valid.

> (2) ... I do not like (1) and currently think that the wording could an=
d
>   should be improved.
> I think we completly agree w.r.t. (1).
>
> > > ... cause this is what we have with normal pointers,
> >
> > How is this relevant? Not all iterators are pointers=B9, although
> > they do have some very similar properties.
>=20
> IMHO the similarities did not happen by chance but are intended.

Of course the similarities are intended. But the fact that they are
similar does not mean that they are the same.

> IMHO the properties of pointers have been very relevant during
> the design of stdc++.iterators.

_Some_ of the properties of pointers, yas.

> Therefore IMHO any significant incompatibility between raw pointers
> and certain iterator types needs the justifacation that it (the
> incompatibility) might allow to write better programs (faster, easier
> to understand or maintain).
> I still havn't found an example of a random access iterator which
> profits from not providing the following pointer-properties:
>=20
>   iter i =3D iter();//defined behaviour even when RHS is singular
>   i =3D=3D i         ;//defined behaviour, result is true.
>   iter j =3D i     ;//defined behaviour
>   j =3D=3D i         ;//defined behaviour, result is true.
>   j !=3D i         ;//defined behaviour, result is false.
>   iter k =3D iter();//defined behaviour even when RHS is singular
>   k =3D=3D i         ;//defined behaviour, result is true.
>   k !=3D i         ;//defined behaviour, result is false.

All of those expressions are undefined if for uninitialised (and hence
singular) pointers. They are well-defined for null pointers (not at
all the same thing.)

> > =B9  And not all pointers are iterators.
>=20
> What pointer violates what requirements ?

I didn't say anything about violating requirements, I said not all
pointers are iterators.

 Of course, if you absolutely must have an example of  a pointer which
doesn't fulfil iterator requirements, how about (off the top of my head):

 const void * const p;

p is a pointer, but satisfies almost none of the iterator requirements
- for any category of iterator.

> > In particular, this isn't required to "work":
> >
> > Iterator iter =3D Iterator();
> > assert( iter =3D=3D iter );
> >
> > Since a singular iterator isn't _required_ to compare equal to itself
> > (since the results of operator=3D=3D on a singular value are undefine=
d),
>=20
> AFAICS even the initialization in the 1st line is not required to
> work,

Which means that none of the rest of it need to work, which means you're
agreeing with me. Thank you.

> allocator.allocate(..) is required to return a ra-iterator.

No. I suggest you read 20.4.1 - it's required to return
allocator::pointer, which in turn is required to be a pointer. What
you have written appears to be trying to suggest that it may return an
arbitrary random access iterator. I'm uncertain as to whether or not
this is your intent.

> (i.e. allocator_type::pointer is a ra-iterator)

Not only is it an ra-iterator, it's also a pointer. Some (most)
pointers are a special case or ra-iterators, but that doesn't mean
that everything that can be said about pointers holds true for random
access iterators.

> Every 20.1.5-dependent library relies on ra-iterator properties.
> 20.1.5 itself and LWG199 and probably not only my compilers
> stdc++ library depend on 'pointers' called '0' or 'null' or
> '[non-]null pointer' or initialized with 0 and later compared
> with each other and being copyable. So IMHO either all the former
> must remove this naive assumptions, or 20.1.5 is missing an
> essential requirement, or [lib.iterator.requirements] 24.1 is
> missing essential requirements or refined iterator categories.

You're continuing to make the assumption that iterators and pointers
are the same thing; they aren't. A null pointer is a pointer which has
a very special value, but it's not singular in the way that an
iterator may be singular. An uninitialised pointer might be singular,
but a null pointer clearly isn't.

> > > and my compiler's library sometimes initializes ranges,
> > > pointers or iterators with '0' (which could be replaced
> > > by "0-iterator/pointer" if one had such entity),
> >
> > It's reasonable for a library implementation to do so - but
> > it's not required.
>=20
> Actually it breaks the libraries expressed intent to do what
> 20.1.5 suggests:
>  "Implementors are encouraged to supply libraries that can accept
>   allocators that encapsulate more general memory models"

It also goes on to say:

 "In such implementations, any requirements imposed on allocators by
 containers beyond those requirements that appear in Table 32, and the
 semantics of containers and algorithms when allocator instances
 compare nonequal, are implementationdefined."

Note the words "BEYOND THOSE REQUIREMENTRS THAT APPEAR IN TABLE
32". Specifically BEYOND. In other words, all of the requirements in
table 32 still apply. And the first requirement in table 32 is:

     X::pointer             Pointer to T.

And of course, there is also 20.1.5p4, which says:

 "Implementations of containers described in this International
  Standard are permitted to assume that their Allocator template
  parameter meets the following two additional requirements beyond
  those in Table 32.

  - All instances of a given allocator type are required to be
    interchangeable and always compare equal to each other.

  - The typedef members pointer, const_pointer, size_type, and
    difference_type are required to be T*, T const*, size_t, and
    ptrdiff_t, respectively."

That, to me, is fairly unambiguous. It means that an implementation is
entitled to assume that X::pointer really is a pointer. A special case
of iterator, which has behaviour above and beyond that which an
iterator has.

>   (AFAICS 'more general memory models' means alloc::pointer being
>   not a raw pointer (but still a ra-iterator))

That's one interpretation.  I wonder how many library vendors agree
with it. Another (which was, historically, at least part of the
motivation for allocators) is that allocator::pointer might be a
"near" or "far" pointer. (IOW, it's still a pointer, but it might be a
different size and hence might require special treatment.).

Of course, this is "encouraged", not required. A library vendor is
permitted to implement a library which works for any allocator(s) they
choose - as long as it functions correctly for their own
std::allocator.

> And about "it's not required" ... how would you implement
> std::vector<T,alloc> w/o relying on either alloc::pointer(0)
> or better alloc::pointer() having some 0-pointer properties ?

I'm sorry, I really can't follow your logic. How is this relevant to
not being required to initialise ALL all pointers and iterators?

Since you've raised the existence of the null pointer, and given that
std::alloctor<T>::pointer is a pointer (and NOT as you seem to think
some generalised random access iterator), then not only is is safe to
assume std::allocator<T>::pointer(0) has null-pointer properties, it's
a requirement. Note again, that a null-pointer is *not* singular.

> Or what should ~tree_node() do with its maybe-indeterminate
> members ?

Whatever "tree_node"'s author chooses as an implementation
strategy. One reasonable - BUT NOT REQUIRED - strategy would be to
initialise pointers with the null value. An alternative might be to
supply a bunch of bit-fields to desceibe the expected behaviour.

> > Some libraries - quite reasonably - skip this step for performance
> > reasons.
>=20
> IMHO you are wrong here.

And, IMHO, you are wrong here. The standard seems to agree with me
though - specifcially, it allows for the concept of a singular
iterator. A common reason for leaving default-constructed iterators
uninitialised (and hence singular) is that there is no reason to
initialise them, since any further behaviour EXCEPT assignment of a
non-singular value is undefined.

> AFAICS in the cases where the mentioned library uses 'null pointers'
> together with type allocator::pointer (initialization, assignment,
> equality compare against 0) it's for better performance or even
> inavoiadable.

There are times when one approach is prefereable to another. There
isn't a single "one-size-fits-all" rule. I never said there was.

> The next better option would be to rely on a dedicated
> constant static non-singular pointer/iterator object (called
> "g_null" ;-). The worst option, potentially singular objects with
> indeterminate value, would need additional expensive and error prone
> logic (like in many other cases when one has members of
> iterator/pointer type).=20

Why? What extra logic is needed with:

void fu()
{
  std::list<int>::iterator foo;
}

foo needs no initialisation, no flags, no special values. It is, by
itself, singular.

If I later add:

foo =3D sone_list.begin();

Then foo becomes non-singular.=20

> IMHO there is a long tradition of excellent high performant C and
> c++ code carefully using the difference between pointers with
> indeterminate value and zero-initialized pointers.

That's as may be, but pointers !=3D iterators. Not everything that holds
true for pointers holds true for all iterators.

>=20
> [...]
> > I'm not really sure what you're trying to say here. If you want to
> > ensure that an iterator may be meaningfully compard to another
> > iterator,
>=20
> Not to _any_ other iterator: all I want is for a 'value-initialized'
> iterator to equ-compare reliably to copies of itself or any other
> 'value-initialized' object of same type, and it should be a reliable
> RHS of initialization or assignment of same type.

If I understand what you're asking for, you want a change in the
standard. A change, I might add, which for no good reason would cause
some library implementations to become non conforming.

> And for allocators I want "alloc::pointer() =3D=3D alloc::const_pointer=
()"
> to be true.

The standard already requires that to be true for std::allocator. It
does not (nor can it) impose that requirement on allocators outside of
the standard library. It then becomes an implementation issue as to
whether std::containers work with non_std::allocators.

> > Iterators are not required to have a "0" or "null" representation.
>=20
> Agreed, but for some kinds of iterators currently I am not sure
> whether this is the result of carefull considerations or whether
> it is an oversight.

The former.

Regards,
 Andy S.
--=20
"Light thinks it travels faster than anything but it is wrong. No matter
 how fast light travels it finds the darkness has always got there first,
 and is waiting for it."                  -- Terry Pratchett, Reaper Man

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

"Andy Sawyer" <news@evo6.com> wrote ...
>
> > This was intended to express that ...
> > (1) ... AFAICS the current wording does not support this
> >     expectation[s]
>
> In fact, the current wording explicitly says that your expectation is
> not valid.

Yes, but strictly speaking not "my expectations".

> > I still havn't found an example of a random access iterator which
> > profits from not providing the following pointer-properties:
> >
> >   iter i = iter();//defined behaviour even when RHS is singular
> >   i == i         ;//defined behaviour, result is true.
> >   iter j = i     ;//defined behaviour
> >   j == i         ;//defined behaviour, result is true.
> >   j != i         ;//defined behaviour, result is false.
> >   iter k = iter();//defined behaviour even when RHS is singular
> >   k == i         ;//defined behaviour, result is true.
> >   k != i         ;//defined behaviour, result is false.
>
> All of those expressions are undefined if for uninitialised (and hence
> singular) pointers.

But actually I did not leave room for any uninitialized pointers.


Reading all your arguments about allocators and allocator_type::pointer,
you obviously made the same error that I did on November 7th in my
posting to comp.std.c++ under the subject "types in table 32
[lib.allocator.requirements]":

"Andy Sawyer" <news@evo6.com> wrote ...
>
> Note the words "BEYOND THOSE REQUIREMENTRS THAT APPEAR IN TABLE
> 32". Specifically BEYOND. In other words, all of the requirements in
> table 32 still apply. And the first requirement in table 32 is:
>
>      X::pointer             Pointer to T.

I had made the same wrong assumption, but James Kuyper Jr.
corrected me:

"James Kuyper Jr."" <kuyper@wizard.net> wrote ...
>
> No. The term "Pointer to" is deliberately meant to allow for other
> possibilities.

Some indirect hints to support his interpretation:

1) Table 32 also says:
  expression: a.allocate(n), a.allocate(n,u)
  return type: X::pointer
  assertion/note pre/postcondition: Memory is allocated for n objects
    of type T but objects are not constructed.
    allocate may raise an appropriate exception.
    The result is a random access iterator.

2) If your interpretation (my old one) concerning table32 was right,
then what you cited from 20.1.5/par4 would be completly redundant:

>  "Implementations of containers described in this International
>   Standard are permitted to assume that their Allocator template
>   parameter meets the following two additional requirements beyond
>   those in Table 32.
>
>   - [...]
>
>   - The typedef members pointer, const_pointer, size_type, and
>     difference_type are required to be T*, T const*, size_t, and
>     ptrdiff_t, respectively."

3) Last month in c.l.c++.m, "Memory allocation by standard containers"
(you participated in this thread)
"P.J. Plauger" <pjp@dinkumware.com> wrote ...
>
> Our Standard C++ library containers use the allocator<T>::
> pointer_type, even to the point of constructing and destructing
> any such pointers in case they're not simple scalars. But we're

.... indicating that for P.J. Plauger it makes sense for a stdc++ library
implementation to be prepared for non-trivial allocator<T>::pointer.
Btw, despite all efforts, even DinkumWare's implementation currently
cant live without frequent conversions between 0 and alloc::pointer:
Is this an argument against their current implementation or
for adding 0-pointer requirements to alloc::pointer ?

IMHO now it is clear that the one line of table32 ,...
>      X::pointer             Pointer to T.
is not indended to mean "pointer to T" in the sense of c++98.core-lang.
If you consider this a defect, I agree with you.
The solution would be to move the term "random access iterator"
from the later notes into X::pointer's line, and removing the
incorrect description "Pointer to T".

Therefore whatever you said about non-pointer ra-iterators
used to represent some allocator_type::pointer is probably
necessary to be re-written and corrected.


> A library vendor is permitted
> to implement a library which works for any allocator(s) they
> choose - as long as it functions correctly for their own
> std::allocator.

This is wrong. A conforming library implementation must support
any custom allocator type the respects the specifications and
requirements for stdc++-library-impl compatible allocators.
E.g. boost::[fast_]pool_allocator<T> doku says ...
 "These types both satisfy the Standard Allocator requirements
  [20.1.5] and the additional requirements in [20.1.5/4], so they
  can be used with Standard or user-supplied containers"


> > And about "it's not required" ... how would you implement
> > std::vector<T,alloc> w/o relying on either alloc::pointer(0)
> > or better alloc::pointer() having some 0-pointer properties ?
>
> I'm sorry, I really can't follow your logic. How is this relevant to
> not being required to initialise ALL all pointers and iterators?

This question (and your still pending answer) is relevant to my
impression that ra-iterators might be underspecified without any
obvious reason, at least w.r.t. alloc::pointers.
I would implement it similar as dinkumware's c++ library does it:
Initialize the 'pointers' for the range with alloc::pointer().
How would you implement vector's constructor when you have no
null-pointer like alloc::pointer(), and when even alloc::pointer()
might result in a singular non-copyable and non-readable object ?

> > The next better option would be to rely on a dedicated
> > constant static non-singular pointer/iterator object (called
> > "g_null" ;-). The worst option, potentially singular objects with
> > indeterminate value, would need additional expensive and error prone
> > logic (like in many other cases when one has members of
> > iterator/pointer type).
>
> Why? What extra logic is needed with:
>
> void fu()
> {
>   std::list<int>::iterator foo;
> }
>
> foo needs no initialisation, no flags, no special values. It is, by
> itself, singular.
>
> If I later add:
>
> foo = sone_list.begin();
>
> Then foo becomes non-singular.

Your sample shows initializing an automatic iterator object,
later assigning a valid value to it and then using it during
one function only - w/o extra logic.
But I claimed that maintaining members of pointer/iterator type
without initializing them to comparable and readable default
values would need additional expensive and error prone
logic.


> > Not to _any_ other iterator: all I want is for a 'value-initialized'
> > iterator to equ-compare reliably to copies of itself or any other
> > 'value-initialized' object of same type, and it should be a reliable
> > RHS of initialization or assignment of same type.
>
> If I understand what you're asking for, you want a change in the
> standard. A change, I might add, which for no good reason

"for no good reason" ?
That is you dont know any reasonable usage of 0-pointers
or 0-iterators that are copyable and equ-comparable at least
with their copies, better with any pointer or iterator ?

> would cause some library implementations to become non conforming.

I'm not sure. Do you know any library implementation containing
a ra-iterator were value-initialization doesnt yield 0-values ?
Or any still supported implementation that doesnt get patched
frequently ?
W.r.t. adding requirements to non-raw-pointer alloc::pointer:
this definitely wouldnt break any library implementation.

> > And for allocators I want "alloc::pointer() == alloc::const_pointer()"
> > to be true.
>
> The standard already requires that to be true for std::allocator. It
> does not (nor can it) impose that requirement on allocators outside of
> the standard library. It then becomes an implementation issue as to
> whether std::containers work with non_std::allocators.

Sounds very convincing, nevertheless you didnt explain why the
requirement "alloc::pointer() == alloc::const_pointer()" cant be
added to the existing other requirements in 20.1.5.

> > > Iterators are not required to have a "0" or "null" representation.
> >
> > Agreed, but for some kinds of iterators currently I am not sure
> > whether this is the result of carefull considerations or whether
> > it is an oversight.
>
> The former.

Even for non-raw-pointer ra-iterators used for alloc::pointer ?


Regards,
Markus.

---
[ 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 Mon, 25 Nov 2002 18:36:11 +0000 (UTC), gregc@cgl.ucsf.edu (Greg
Couch) wrote:

> I was recently surprised by the following code failing:
>
>  Range func(key)
>   for i in a bunch of multimaps
>    Range r = i->equal_range(key)
>    if r is not empty
>     return r
>   return Range()  // -- bug was here
> It failed because the naive implementation of returning an empty range fails:

It's a feature, see 24.1/5.

>  typedef std::multimap<...> M;
>  typedef std::pair<M:iterator, M::iterator> Range;

>  Range range;

The default ctor for pair uses first(T1()), second(T2()).

>  assert(range.first == range.second); // assertion fails!!
>  return range;

> It turns out that with different containers types it sometimes works.  The
> compilers I checked were the SGI 7.3.1.3m, gcc 3.2, Compaq 6.5.  All failed
> with multimaps, the SGI compiler works with multisets, and all worked with
> vectors.

Forward iterators are required to have default ctors, but default
constructed iterators are allowed to be singular.  The fact that
your tests passed with vector is likely because vector iterator is
a pointer in those libraries and P() is null for any pointer type P.

You should never do anything other than assign a new value with a
default constructed iterator.  It is just like int* p;

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                       ]

In article <qgJE9.102561$up.1110505@news.chello.at>,
 on Tue, 26 Nov 2002 15:45:48 +0000 (UTC),
 markus.mauhart@nospamm.chello.at ("Markus Mauhart") wrote:

> "Andy Sawyer" <news@evo6.com> wrote ...
> >
> > What I wouldn't (necessarily) expect to work is:
> >
> >  some_container::iterator a, b;
> >  assert( a =3D=3D b );
>=20
> But against the current stdc++ wording

Can you please specifiy exactly (section, paragraph) which wording in
the standard you're referring to?

> for forward /biirectional/randomaccess iterators one should be
> allowed to expect that the following works ...
>=20
>   Iter a =3D Iter(), b =3D Iter();
>   assert( a =3D=3D b );


I can't find the wording which you claim supports this expectation,
but what I can find is:

24.1p5, which says, in part:
,----
| Iterators can also have singular values that are not associated with
| any container. [Example: After the declaration of an uninitialized
| pointer x (as with int* x;), x must always be assumed to have a
| singular value of a pointer. ] Results of most expressions are
| undefined for singular values; the only exception is an assignment of
| a nonsingular value to an iterator that holds a singular value. In
| this case the singular value is overwritten the same way as any other
| value.
`----

Note especially the part which says "Results of most expressions are
undefined for singular values".

and

24.1.3 Table 74 says, in part:
,----
| X u;                note: u might have a singular value.
| X()                 note: X() might be singular.
`----
This describes Forward Iterators, but also applies to Bidirectional
and Random Access Iterators. Note especially the note that "X() might
be singular".

In other words, default constructed iterators may be singular, and
thus the comparison of such iterators is undefined.

> ... cause this is what we have with normal pointers,

How is this relevant? Not all iterators are pointers=B9, although they
do have some very similar properties.

> and it would solve the OP's problem,

The OP's problem would also be solved by not making the assumption
that potentially singular iterators can be assumed to compare
equal. In particular, this isn't required to "work":

Iterator iter =3D Iterator();
assert( iter =3D=3D iter );

Since a singular iterator isn't _required_ to compare equal to itself
(since the results of operator=3D=3D on a singular value are undefined),
it certainly can't be required to compare equal to another
singular iterator.

> and (for random access iterators) allocator requirements
> + LWG199's description do refer to entities called
> '0' or 'null' or '[non-]null pointer',

Allocator requirements and LWG199 refer to allocators, not
iterators. How is this relevant?

> and my compiler's library sometimes initializes ranges,
> pointers or iterators with '0' (which could be replaced
> by "0-iterator/pointer" if one had such entity),

It's reasonable for a library implementation to do so - but it's not
required. Some libraries - quite reasonably - skip this step for
performance reasons. That's one of the reasons we have a standard - on
the one hand it tells library implementors what they can and can't do,
and on the other hand it tells library users what they can and can't
expect library implementations to do.

> and I too would like to know whether some ra- or bidi-
> iterator object is equ-comparable and equal to '0' or
> any other 'comparable iterator value', or otherwise points
> to some data I have to destruct or process otherwise
> (currently a memberfunction isnt allowed to even compare
> two members of type iterator whithout knowing that both
> have been assigned from 'comparable' iterator values,
> actually RAII isnt possible w/o an additional logical
> flag per pointer/iterator).

I'm not really sure what you're trying to say here. If you want to
ensure that an iterator may be meaningfully compard to another
iterator, then you need to ensure that they are both non-singular. The
way to do that is to acquire non-singular iterators from the
collection to which the iterators refer. Iterators are not required to
have a "0" or "null" representation.

Regards,
 Andy S.

Footnotes:=20
=B9  And not all pointers are iterators.
--=20
"Light thinks it travels faster than anything but it is wrong. No matter
 how fast light travels it finds the darkness has always got there first,
 and is waiting for it."                  -- Terry Pratchett, Reaper Man

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

Andrew Koenig wrote:
> Greg>  typedef std::multimap<...> M;
> Greg>  typedef std::pair<M:iterator, M::iterator> Range;
>
> Greg>  Range range;
> Greg>  assert(range.first == range.second); // assertion fails!!
> Greg>  return range;
>
> Greg> It turns out that with different containers types it sometimes
> Greg> works.  The compilers I checked were the SGI 7.3.1.3m, gcc 3.2,
> Greg> Compaq 6.5.  All failed with multimaps, the SGI compiler works
> Greg> with multisets, and all worked with vectors.
>
> Why are you surprised?  Remember that pointers are iterators, and
> think about the consequence of changing your example as follows:
>
>         typedef std::pair<int*, int*> Range;
>
>         Range range;
>         assert(range.first == range.second);
>
> Do you still expect it to work?  If so, why?
>

I think a lot of people might be surprised to learn that iterators are
uninitialized when constructed.

After all, writing a constructor that initializes the object is one of
the basic good practices of object oriented programming right?  And yet,
the C++ Standard classes, like iterators, do not require this.  Of
course this is no doubt done because initialization has a price:
increased code size and decreased performance.

The C++ Standard Library is great and I love it.  However it is all too
easy to get things wrong.  Iterators are probably a main source of
problems because they can be:
1. uninitialized
2. invalid
3. used with the incorrect container (type safety only helps if you have
containers of a different type)

It would be nice if implementations of the C++ Standard Library had a
debug flag which could catch these errors.  Admittedly, this would not
prevent errors, but only help to debug them more quickly.


Gawain

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

In article <3DE78239.7010803@computer.org>,
 on Fri, 29 Nov 2002 15:07:26 +0000 (UTC),
 gp.bolton@computer.org (Gawain Bolton) wrote:

> Andrew Koenig wrote:
> > Greg>  typedef std::multimap<...> M;
> > Greg>  typedef std::pair<M:iterator, M::iterator> Range;
> > Greg>  Range range;
>
> > Greg>  assert(range.first == range.second); // assertion fails!!
> > Greg>  return range;
> > Greg> It turns out that with different containers types it sometimes
>
> > Greg> works.  The compilers I checked were the SGI 7.3.1.3m, gcc 3.2,
> > Greg> Compaq 6.5.  All failed with multimaps, the SGI compiler works
> > Greg> with multisets, and all worked with vectors.
> > Why are you surprised?  Remember that pointers are iterators, and
>
> > think about the consequence of changing your example as follows:
> >         typedef std::pair<int*, int*> Range;
>
> >         Range range;
>
> >         assert(range.first == range.second);
> > Do you still expect it to work?  If so, why?
>
> I think a lot of people might be surprised to learn that iterators are
> uninitialized when constructed.

That's probably because iterators *are* initialized when constructed,
although they may be initialized to a singular value. The standard is
very clear on what it means for an iterator to be singular (24.1/p5).

> The C++ Standard Library is great and I love it.  However it is all
> too easy to get things wrong.  Iterators are probably a main source of
> problems because they can be:
>
> 1. uninitialized
> 2. invalid
> 3. used with the incorrect container (type safety only helps if you
>    have containers of a different type)
>
>
> It would be nice if implementations of the C++ Standard Library had a
> debug flag which could catch these errors.  Admittedly, this would not
> prevent errors, but only help to debug them more quickly.

You probably ought to take a look at STLport (http://www.stlport.org) then.

Regards,
 Andy S.
--
"Light thinks it travels faster than anything but it is wrong. No matter
 how fast light travels it finds the darkness has always got there first,
 and is waiting for it."                  -- Terry Pratchett, Reaper Man

---
[ 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 Sun, 1 Dec 2002 18:45:14 +0000 (UTC), news@evo6.com (Andy Sawyer)
wrote:

> In article <3DE78239.7010803@computer.org>,
>  on Fri, 29 Nov 2002 15:07:26 +0000 (UTC),
>  gp.bolton@computer.org (Gawain Bolton) wrote:

> > I think a lot of people might be surprised to learn that iterators are
> > uninitialized when constructed.

> That's probably because iterators *are* initialized when constructed,
> although they may be initialized to a singular value. The standard is
> very clear on what it means for an iterator to be singular (24.1/p5).

void f () {
   int i;
   int* p;
   list<int>::iterator it;
   }

The standard is quite clear that all three of these may contain
singular values.  Singular as used in the standard is like 0 / 0.
You can't initialize something to a singularity, it is what happens
when there is no initialization.  List<>::iterator has a default
constructor, but there is no requirement that it initialize its data
member(s).

There is much confusion because null is considered a singular value by
many, but the standard uses singular to mean uninitialized which is
very different from null.

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                       ]

Gawain Bolton wrote:
....
> I think a lot of people might be surprised to learn that iterators are
> uninitialized when constructed.

You can't prevent people from jumping to unwarranted conclusions. It's
quite possible to meet the iterator requirements without having a
default constructor that actually initializes anything.

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

Markus Mauhart schrieb:
> But against the current stdc++ wording, for forward
> /biirectional/randomaccess iterators one should be
> allowed to expect that the following works ...
>
>   Iter a = Iter(), b = Iter();
>   assert( a == b );
>
> ... cause this is what we have with normal pointers,

is that true?  as far as i can remember, the statement

int* a;

leaves a with an unspecified value.  it could be NULL - but it
could as well be 0x0F00 or some other bit pattern.

regards

 robert

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

Greg Couch wrote:
> It failed because the naive implementation of returning an empty range fails:
>
>  typedef std::multimap<...> M;
>  typedef std::pair<M:iterator, M::iterator> Range;
>
>  Range range;
>  assert(range.first == range.second); // assertion fails!!
>  return range;

Of course, a default-constructed range consists in a pair of
default-constructed iterators. As specified in 24.1.3 (Forward
iterators), Table 5, a default-constructed iterator might hold a
singular value. In 24.1 (Iterator requirements), statement 5 reads:

"Results of most expressions are undefined for singular values; the only
exception is an assignment of a non-singular value to an iterator that
holds a singular value."

Thus comparison between two singular-valued iterators is undefined
behaviour. It's therefore no surprise that you are getting different
results with different containers and/or compilers.

It's hard to call it a feature :), but certainly it's not a defect.

Alberto Barbati



-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----

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

Greg>  typedef std::multimap<...> M;
Greg>  typedef std::pair<M:iterator, M::iterator> Range;

Greg>  Range range;
Greg>  assert(range.first == range.second); // assertion fails!!
Greg>  return range;

Greg> It turns out that with different containers types it sometimes
Greg> works.  The compilers I checked were the SGI 7.3.1.3m, gcc 3.2,
Greg> Compaq 6.5.  All failed with multimaps, the SGI compiler works
Greg> with multisets, and all worked with vectors.

Why are you surprised?  Remember that pointers are iterators, and
think about the consequence of changing your example as follows:

        typedef std::pair<int*, int*> Range;

        Range range;
        assert(range.first == range.second);

Do you still expect it to work?  If so, why?

--
Andrew Koenig, ark@research.att.com, http://www.research.att.com/info/ark

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

In article <arn2gt$5jc8$1@cgl.ucsf.edu>,
 on Mon, 25 Nov 2002 18:36:11 +0000 (UTC),
 gregc@cgl.ucsf.edu (Greg Couch) wrote:

> I was recently surprised by the following code failing:
>
>  Range func(key)
>   for i in a bunch of multimaps
>    Range r = i->equal_range(key)
>    if r is not empty
>     return r
>   return Range()  // -- bug was here
>
> It failed because the naive implementation of returning an empty range fails:
>
>  typedef std::multimap<...> M;
>  typedef std::pair<M:iterator, M::iterator> Range;
>
>  Range range;
>  assert(range.first == range.second); // assertion fails!!
>  return range;
>
> It turns out that with different containers types it sometimes works.  The
> compilers I checked were the SGI 7.3.1.3m, gcc 3.2, Compaq 6.5.  All failed
> with multimaps, the SGI compiler works with multisets, and all worked with
> vectors.

You're making the assumption that default-constructed iterators
compare equal, which isn't required to be the case. Many
implementations leave the "innards" of default constructed
uninitialized (presumably for the sake of performance).

 Given the choice offered by your subject line ("defect or feature"),
I have to choose "feature", although I'd rather say "that's the way it
is" (since I consider it to be neither a feature or a defect :-)

Regards,
 Andy S.
--
"Light thinks it travels faster than anything but it is wrong. No matter
 how fast light travels it finds the darkness has always got there first,
 and is waiting for it."                  -- Terry Pratchett, Reaper Man

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

In article <yu99n0nxbh61.fsf@europa.research.att.com>,
 on Mon, 25 Nov 2002 21:51:33 CST,
 Andrew Koenig <ark@research.att.com> wrote:

> Greg>  typedef std::multimap<...> M;
> Greg>  typedef std::pair<M:iterator, M::iterator> Range;
>=20
> Greg>  Range range;
> Greg>  assert(range.first =3D=3D range.second); // assertion fails!!
> Greg>  return range;
>=20
> Greg> It turns out that with different containers types it sometimes
> Greg> works.  The compilers I checked were the SGI 7.3.1.3m, gcc 3.2,
> Greg> Compaq 6.5.  All failed with multimaps, the SGI compiler works
> Greg> with multisets, and all worked with vectors.
>=20
> Why are you surprised?  Remember that pointers are iterators, and
> think about the consequence of changing your example as follows:
>=20
>         typedef std::pair<int*, int*> Range;
>=20
>         Range range;
>         assert(range.first =3D=3D range.second);
>=20
> Do you still expect it to work?  If so, why?

Actually, in this case I would, given either=B9 definition of std::pair's
default constructor. I'd also expect:

 assert( range.first =3D=3D 0 );
 assert( range.second =3D=3D 0 );

To hold true. In fact, my suspicion is that this is exactly the reason
that Greg had success with vectors (since, of course, vectors often
use raw pointers as iterators.)

What I wouldn't (necessarily) expect to work is:

 some_container::iterator a, b;
 assert( a =3D=3D b );

Although I wouldn't be surprised if it did. Iterators are allowed to
be singular, and the only thing you can do safely with a singular
iterator is assign to it.

Regards,
 Andy S.
Footnotes:=20
=B9  "Either" the Standard or LWG265/TC1.
--=20
"Light thinks it travels faster than anything but it is wrong. No matter
 how fast light travels it finds the darkness has always got there first,
 and is waiting for it."                  -- Terry Pratchett, Reaper Man

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

"Andy Sawyer" <news@evo6.com> wrote ...
>
> What I wouldn't (necessarily) expect to work is:
>
>  some_container::iterator a, b;
>  assert( a == b );

But against the current stdc++ wording, for forward
/biirectional/randomaccess iterators one should be
allowed to expect that the following works ...

  Iter a = Iter(), b = Iter();
  assert( a == b );

... cause this is what we have with normal pointers,
and it would solve the OP's problem,
and (for random access iterators) allocator requirements
+ LWG199's description do refer to entities called
'0' or 'null' or '[non-]null pointer',
and my compiler's library sometimes initializes ranges,
pointers or iterators with '0' (which could be replaced
by "0-iterator/pointer" if one had such entity),
and I too would like to know whether some ra- or bidi-
iterator object is equ-comparable and equal to '0' or
any other 'comparable iterator value', or otherwise points
to some data I have to destruct or process otherwise
(currently a memberfunction isnt allowed to even compare
two members of type iterator whithout knowing that both
have been assigned from 'comparable' iterator values,
actually RAII isnt possible w/o an additional logical
flag per pointer/iterator).


Regards,
Markus Mauhart.

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

I was recently surprised by the following code failing:

 Range func(key)
  for i in a bunch of multimaps
   Range r = i->equal_range(key)
   if r is not empty
    return r
  return Range()  // -- bug was here

It failed because the naive implementation of returning an empty range fails:

 typedef std::multimap<...> M;
 typedef std::pair<M:iterator, M::iterator> Range;

 Range range;
 assert(range.first == range.second); // assertion fails!!
 return range;

It turns out that with different containers types it sometimes works.  The
compilers I checked were the SGI 7.3.1.3m, gcc 3.2, Compaq 6.5.  All failed
with multimaps, the SGI compiler works with multisets, and all worked with
vectors.

 Thanks for your attention,

 Greg Couch
 UCSF Computer Graphics Lab
 gregc@cgl.ucsf.edu

-------
rangetest program
-------
#include <vector>
#include <map>
#include <set>
#include <iostream>

typedef std::multimap<int, int> M;
typedef std::multiset<int> S;
typedef std::vector<int> V;
typedef std::pair<M::iterator, M::iterator> MRange;
typedef std::pair<S::iterator, S::iterator> SRange;
typedef std::pair<V::iterator, V::iterator> VRange;

int
main(int, char **)
{
 MRange mr;
 bool mEmpty = (mr.first == mr.second);
 std::cout << "empty multimap range: " << (mEmpty ? "yes" : "no") << '\n';

 SRange sr;
 bool sEmpty = (sr.first == sr.second);
 std::cout << "empty multiset range: " << (sEmpty ? "yes" : "no") << '\n';

 VRange vr;
 bool vEmpty = (vr.first == vr.second);
 std::cout << "empty vector range: " << (vEmpty ? "yes" : "no") << '\n';

 return (mEmpty && sEmpty && vEmpty) ? 0 : 1;
}

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