15

The section §24.1/5 from the C++ Standard (2003) reads,

Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element of the array, so for any iterator type there is an iterator value that points past the last element of a corresponding container. These values are called past-the-end values. Values of an iterator i for which the expression *i is defined are called dereferenceable. The library never assumes that past-the-end values are dereferenceable. 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 non-singular value to an iterator that holds a singular value. In this case the singular value is overwritten the same way as any other value. Dereferenceable values are always nonsingular.

I couldn't really understand the text shown in bold?

  • What is singular value and nonsingular value? How are they defined? And where?
  • How and why dereferenceable values are always nonsingular?
Nawaz
  • 353,942
  • 115
  • 666
  • 851

4 Answers4

10

If I understand this correctly, a singular value for an iterator is essentially the equivalent of an unassigned pointer. It's an iterator that hasn't been initialized to point anywhere and thus has no well-defined element it's iterating over. Declaring a new iterator that isn't set up to point to an element of a range, for example, creates that iterator as a singular iterator.

As the portion of the spec alludes to, singular iterators are unsafe and none of the standard iterator operations, such as increment, assignment, etc. can be used on them. All you can do is assign them a new value, hopefully pointing them at valid data.

I think the reason for having this definition is so that statements like

set<int>::iterator itr;

Can be permitted by the spec while having standardized meaning. The term "singular" here probably refers to the mathematical definition of a singularity, which is also called a "discontinuity" in less formal settings.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • Can a default-constructed `istream_iterator` be considered singular? – Björn Pollex Mar 26 '11 at 11:34
  • 1
    I don't think so. It's a valid past-the-end iterator. If it were singular, you couldn't use it to define the enf of a stream, since you couldn't compare it to any other iterators. – templatetypedef Mar 26 '11 at 17:36
8

Iterators can also have singular values that are not associated with any container.

I suppose that's its definition.

How and why dereferenceable values are always nonsingular?

Because if they wouldn't, dereferencing them would be undefined behavior.

Johannes Schaub - litb
  • 496,577
  • 130
  • 894
  • 1,212
2

Have a look at What is an iterator's default value?.

As the quote indicates, singular values are iterator values that are not associated with any container. A singular value is almost useless: you can't advance it, dereference it, etc. One way (the only way?) of getting a singular iterator is by not initializing it, as shown in templatetypedef's answer.

One of the useful things you can do with a singular iterator, is assign it a non-singular value. When you do that you can do whatever else you want with it.

The non-singular values are, almost by definition, iterator values that are associated with a container. This answers why dereferenceable values are always non-singular: iterators that do not point to any container cannot be dereferenced (what element would this return?).

As Matthieu M. correctly noted, non-singular values may still be non-dereferenceable. An example is the past-the-end iterator (obtainable by calling container.end()): it is associated with a container, but still cannot be referenced.

I can't say where these terms are defined. However, Google has this to say about "define: singular" (among other definitions):

remarkable: unusual or striking

I suppose this can explain the terminology.

Community
  • 1
  • 1
telewin
  • 1,102
  • 8
  • 17
  • 1
    Watch out! Non-singular values include the past the end iterator, this one cannot be dereferenced. – Matthieu M. Mar 26 '11 at 11:42
  • @Matthieu: you're 100% right. I have updated my answer to reflect that non-singular values may still be non-dereferenceable. Thanks! – telewin Mar 26 '11 at 12:18
2

What is singular value and nonsingular value? How are they defined? And where?

Let us use the simplest incarnation of an Iterator: the pointer.

For a pointer:

  • the singular value alluded to is the NULL value an uninitialized value.
  • a non-singular value is an explicitly initialized value, it may not be dereferencable still (the past-the-end pointer shall not be dereferenced)

I would say that the NULL pointer is a singular value, though not the only one, since it represents the absence of value.

What is the equivalence for regular iterators ?

std::vector<int>::iterator it;, the default constructor of most iterators (those linked to a container) create a singular value. Since it's not tied to a container, any form of navigation (increment, decrement, ...) is meaningless.

How and why dereferenceable values are always nonsingular ?

Singular values, by definition, represent the absence of a real value. They appear in many languages: Python's None, C#'s null, C's NULL, C++'s std::nullptr. The catch is that in C or C++, they may also be simple garbage... (whatever was there in memory before)

Is a default constructed iterator a singular value ?

Not necessarily, I guess. It is not required by the standard, and one could imagine the use of a sentinel object.

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
  • I was thinking on the same lines as you did, with *singular* iterators referring to things like a null pointer or `std::istream_iterator()`, but then I reread a couple of times the quote and came to the conclusion that this might not be the case. There is a guarantee that you cannot only assign to, but also compare null pointers (or `std::istream_iterator()` So I am no longer convinced that this interpretation holds. – David Rodríguez - dribeas Mar 26 '11 at 11:57
  • @David: I think that the standard is unclear here. The use of *most of* follow by *the only exception* is dubious, why not *all*/*except* ? It seemed they were willing to account for unitialized values as well (like the example) and not only null values. – Matthieu M. Mar 26 '11 at 12:01
  • "the singular value alluded to" is actually _not_ `NULL`. The example text quoted is clear: "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.". Now, an uninitialized pointer is not `NULL`. You can't even compare it to `NULL`. – MSalters Mar 28 '11 at 09:42
  • @MSalters: it was supposed to be corrected but I had missed a `/` to close the `strike` tag :) – Matthieu M. Mar 28 '11 at 13:16