On Tue, 22 Feb 2011 16:57:59 -0000, Martin B. <0xCDCDCDCD@gmx.at> wrote:

> ...
>>
>> std::copy<char*,char*>( nullptr, nullptr, nullptr );
>>
>> *should* be illegal.
>
> But note that the (vague) way the standard uses the term 'singular',
> it does appear that a nullptr is *not* singular as it seems implied
> that you cannot even compare a singular value to another and you can
> do so with a nullptr.

:roll:

You're right. But that means a function *can* *never*, *ever*
tell if the iterator it has received is singular.

And since 24.2.1/5 puts forward an uninitialized pointer "int*
x;" as an example of a singular iterator, it MUST be that the
term 'singular' means "an iterator with undefined value which
cannot be told apart from an ordinary, valid iterator".

So the definition is pretty clear, I think.

*bangs head against desk until it bleeds*

Okay, here's a hasty proposal for singular iterators.

(And just as nullptrs may be used as past-the-end values,
so I've left open the door for singular iterators to
mark the end of a range.)

=Singular Iterators=

As iterators generalise pointers, so singular iterators
generalise nullptr. Therefore:

1. std::iterator_traits must have a nested typedef
'singular_type'. [--Or whatever people want to call it.--]

2. 'template<class T> struct iterator_traits<T*>' must typedef
'std::nullptr_t' as 'singular_type'.

3. 'template<class Iterator> struct iterator_traits' must use
SFINAE methods to detect the presence of 'typename
Iterator::singular_type', and typedef it to 'singular_type';
if this nested typedef is missing from Iterator then proceed as
if it were 'typedef Iterator singular_type;'.
[--I expect most iterators already fulfil the requirements I'm
laying out, so making the Iterator its own singular_type should
work 90% of time, and offer backwards compatibility.--]

singular_type must be DefaultConstructable. Assignment of a
value of type singular_type to an iterator makes the iterator
a 'singular iterator', as does construction of an iterator from a
value of type singular_type.  Singular iterators have the
following properties:

 - they may be assigned to or copied from.

 - they are not dereferenceable or incrementable.

 - they are not decrementable (unless the singular iterator
  is used as a past-the-end value, and the iterator category
  requires the iterator be decrementable).

 - a user shall never attempt to measure the distance from an
  iterator to a singular iterator, or the distance between two
  singular iterators, however if a singular iterator is used
  as a past-the-end value, then the distance calculations (via
  std::distance, operator-, etc...) shall work as expected for
  a past-the-end-value.

 - Singular iterators can be compared with other non-singular
  iterators. By definition singular iterators are guaranteed
  not to equal any other /dereferenceable/ iterator
  *that*belongs*to*a*container*.  [--As noted above, the
  past-the-end value may or may not be a singular iterator, so
  a singular iterator /may/ compare equal to a past the end
  value.--]

 - Although it is valid to compare two singular iterators, the
  result is undefined (except where singular iterators are being
  used as past-the-end iterators, when they will always compare
  equal). [--That covers Daniel's example of a NaN being used as
  a singular iterator.--]

  However there must exist a free function
  'is_singular_iterator(Iterator const&)' that returns true iff
  an iterator is singular.

  An implementation equivalent to the follow is provided in
  namespace std

template <typename Iterator>
bool
is_singular_iterator( Iterator const& i )
{
  return i == Iterator(
     typename iterator_traits<Iterator>::singular_type()
  );
}

  Any iterator for which this is the correct implementation
  need not provide their own. [--So users must guarantee the
  above version can be found, before calling
  is_singular_iterator.--]

      [--The possibility that past-the-end values may be singular
  means algorithms must never reject ranges that have singular
  past-the-end iterators. For example, std::copy might
  look like:

template <typename InputIterator, typename OutputIterator>
OuputIterator
copy( InputIterator i, InputIterator end, OuputIterator o)
{
  /* this would be wrong:

  if ( is_singular_iterator( end ) )
     return o;
  */

  // this is fine:
  if ( !is_singular_iterator( i ) )
     while ( i != end )
        *(o++) = *(i++);

  return o;
}

  This approach guarantees the code will work when the
  past-the-end value is singular, and the range is non-empty.
  --]

7. There is NO requirement that iterators be
DefaultConstructable. Iterators must only be constructed by
moving or copying existing iterators, or by
default- or copy-initialisation from a value of type
'singular_type'.
[--Obviously containers will have access to other private
constructors--]


That wasn't hard. So where've I gone wrong?


Peter
--
Using Opera's best of a worst bunch mail reader.


[ comp.std.c++ is moderated.  To submit articles, try posting with your ]
[ newsreader.  If that fails, use mailto:std-cpp-submit@vandevoorde.com ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

[First submission failed, therefore this second one]

On 2011-03-04 10:14, peter miller wrote:
>
> On Tue, 22 Feb 2011 16:57:59 -0000, Martin B. <0xCDCDCDCD@gmx.at> wrote:
>
>> ...
>>>
>>> std::copy<char*,char*>( nullptr, nullptr, nullptr );
>>>
>>> *should* be illegal.
>>
>> But note that the (vague) way the standard uses the term 'singular',
>> it does appear that a nullptr is *not* singular as it seems implied
>> that you cannot even compare a singular value to another and you can
>> do so with a nullptr.
>
> :roll:
>
> You're right. But that means a function *can* *never*, *ever*
> tell if the iterator it has received is singular.

This is correct, the generally applies to all values that correspond
to a "partially formed state" (This is nomenclature from the book
"Elements of Programming"). Usually there does not exist a query
is_well_formed. This makes sense, because we also have no
(portable/standardized) way to ask a pointer value whether it points
to valid memory or an int object whether it contains a well-formed
int value.

> And since 24.2.1/5 puts forward an uninitialized pointer "int*
> x;" as an example of a singular iterator, it MUST be that the
> term 'singular' means "an iterator with undefined value which
> cannot be told apart from an ordinary, valid iterator".

This is not completely true: I agree that every non-initialized object
state matches this definition, but I think the intend is to support
NaN-like special values as well. Note that a null pointer value is *not*
a NaN-like iterator value, because it perfectly supports equality
comparisons and relational comparisons as well.

> So the definition is pretty clear, I think.
>
> *bangs head against desk until it bleeds*
>
> Okay, here's a hasty proposal for singular iterators.
>
> (And just as nullptrs may be used as past-the-end values,
> so I've left open the door for singular iterators to
> mark the end of a range.)

A singular iterator cannot define a past-the-end value, at least not
according to the original intention of what a singular iterator value
is. Singular iterator values provide no guarantee to be comparable by
==, for example. This is exactly the reason why I consider the
decision of

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#208

as incorrect. It deviates from the intention for which the idea of
singular iterator values was invented.

> =Singular Iterators=
>
> As iterators generalise pointers, so singular iterators
> generalise nullptr. Therefore:

I don't see any reason why iterator should provide a
null-pointer-concept. The working draft has introduced a requirements
set NullablePointer to mark a pointer-like type that can be compared /
assigned with/from nullptr_t objects, though.

> 1. std::iterator_traits must have a nested typedef
> 'singular_type'. [--Or whatever people want to call it.--]

This would increase the number of associated types of iterator_traits
were I see no good reason for. Why do we need a null-state for
iterators? Iterators don't even have any concept of null values.

> 2. 'template<class T> struct iterator_traits<T*>' must typedef
> 'std::nullptr_t' as 'singular_type'.

But nulltpr_t is no singular iterator value - it supports very similar
functionality as other null pointer values. I can use it in
comparsions with pointers, for example.

> 3. 'template<class Iterator> struct iterator_traits' must use
> SFINAE methods to detect the presence of 'typename
> Iterator::singular_type', and typedef it to 'singular_type';
> if this nested typedef is missing from Iterator then proceed as
> if it were 'typedef Iterator singular_type;'.
> [--I expect most iterators already fulfil the requirements I'm
> laying out, so making the Iterator its own singular_type should
> work 90% of time, and offer backwards compatibility.--]
>
> singular_type must be DefaultConstructable.Assignment of a
> value of type singular_type to an iterator makes the iterator
> a 'singular iterator', as does construction of an iterator from a
> value of type singular_type. Singular iterators have the
> following properties:
>
> - they may be assigned to or copied from.

"Copied from" is essentially something which is *not* supported for
singular iterator values.

> - they are not dereferenceable or incrementable.

Agreed.

> - they are not decrementable (unless the singular iterator
> is used as a past-the-end value, and the iterator category
> requires the iterator be decrementable).

Agreed.

> - a user shall never attempt to measure the distance from an
> iterator to a singular iterator, or the distance between two
> singular iterators, however if a singular iterator is used
> as a past-the-end value, then the distance calculations (via
> std::distance, operator-, etc...) shall work as expected for
> a past-the-end-value.

This clearly deviates from the original idea of singular values.
I don't think that adding this requirement is useful. It does not work
for singular pointer values, for example. E.g. consider:

int* p = new int;
delete p; // From this point on p is singular
         // iterator, if interpreted as iterator value.

> - Singular iterators can be compared with other non-singular
> iterators. By definition singular iterators are guaranteed
> not to equal any other /dereferenceable/ iterator
> *that*belongs*to*a*container*. [--As noted above, the
> past-the-end value may or may not be a singular iterator, so
> a singular iterator /may/ compare equal to a past the end
> value.--]

I disagree, as explained above.

> - Although it is valid to compare two singular iterators, the
> result is undefined (except where singular iterators are being
> used as past-the-end iterators, when they will always compare
> equal). [--That covers Daniel's example of a NaN being used as
> a singular iterator.--]

This seems like a use-less operation then. If the result is undefined,
I cannot use it in any meaningful way.

> However there must exist a free function
> 'is_singular_iterator(Iterator const&)' that returns true iff
> an iterator is singular.

This cannot be guaranteed. Example: built-in pointers don't provide
this "detector" function.

> An implementation equivalent to the follow is provided in
> namespace std
>
> template <typename Iterator>
> bool
> is_singular_iterator( Iterator const& i )
> {
> return i == Iterator(
> typename iterator_traits<Iterator>::singular_type()
> );
> }
>
> Any iterator for which this is the correct implementation
> need not provide their own. [--So users must guarantee the
> above version can be found, before calling
> is_singular_iterator.--]
>
> [--The possibility that past-the-end values may be singular
> means algorithms must never reject ranges that have singular
> past-the-end iterators. For example, std::copy might
> look like:
>
> template <typename InputIterator, typename OutputIterator>
> OuputIterator
> copy( InputIterator i, InputIterator end, OuputIterator o)
> {
> /* this would be wrong:
>
> if ( is_singular_iterator( end ) )
> return o;
> */
>
> // this is fine:
> if ( !is_singular_iterator( i ) )
> while ( i != end )
> *(o++) = *(i++);
>
> return o;
> }
>
> This approach guarantees the code will work when the
> past-the-end value is singular, and the range is non-empty.
> --]

I don't think that we need this additional layer. It should be
sufficient, if any algorith can work with either derefrencable or
past-the-end iterators. Why should we need a third form?

> 7. There is NO requirement that iterators be
> DefaultConstructable. Iterators must only be constructed by
> moving or copying existing iterators, or by
> default- or copy-initialisation from a value of type
> 'singular_type'.
> [--Obviously containers will have access to other private
> constructors--]
>
>
> That wasn't hard. So where've I gone wrong?

I tried to answer to that question above.

HTH & Greetings from Bremen,

Daniel Kr   gler


--
[ comp.std.c++ is moderated.  To submit articles, try posting with your ]
[ newsreader.  If that fails, use mailto:std-cpp-submit@vandevoorde.com ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]