Greg Herlihy wrote:
.
> Yes, because just four paragraphs earlier the Standard described how
> random access iterators are a special case for both std::distance()
> and std::advance(). Yet the special case described in paragraph 1 is
> completely forgotten by paragraph 5. Specifically:
>
>    - From    24.3.4/1, we can infer that std::distance() subtracts
> "first" from "last" to calculates the distance between two random
> access iterators
>    -    24.3.4/5 requires that that distance()'s "last" iterator be
> reachable from the "first" iterator (for any type of supported
> iterator)
>
> Now subtracting one random access iterator from another does not
> require that the subtrahend (right operand) be reachable from the
> minuend (left operand). As long as one operand is reachable from the
> other - the subtraction is well-defined. So Paragraph 5 misstates the
> requirements for random access iterator subtraction. Or more plainly:
> Paragraph 5 is wrong.

Just because those requirements for using std::distance()  re more
stringent than they need to be for random access iterators doesn't make
them wrong. Most standard templates have stricter requirements than they
need to have, because in general a complete description of the
absolutely least restrictive requirements is too complicated.

> The essential point being made here, though, is that    24.3.4 paragraph
> 5 cannot be reconciled with paragraph 1; and this inconsistency is -
> in my view - a defect.

I don't see an inconsistency; just restrictions that are stricter than
they could be. This strikes me as not only allowable, but reasonable. If
you know you have random access iterators, you should use binary '-'
directly. std::distance() is designed for precisely those cases (such as
inside a template function) where you can't be sure that your iterators
are random access. In precisely those cases, you shouldn't be attempting
to find the distance unless you know that 'last' is reachable from 'first'.

---
[ 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.comeaucomputing.com/csc/faq.html                      ]

The latest draft of the C++0x standard describes the effects and
requirements
of std::distance as follows:

  "Effects: Returns the number of increments or decrements needed to
get
  from first to last.
  Requires: last shall be reachable from first."

In 2000 Rintala Matti submitted an issue asking for clarification with
regard
to std::distance as used with bidirectional iterators when last
precedes
first:

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

The committee answered that "reachable" is defined in 24.1.6 only in
terms
of operator++, so that last is *not* reachable from first when last
precedes
first, even in the case of bidirectional or random access iterators. A
logical
conclusion of this is that std::distance always returns nonnegative
values.

This leaves the following issues open:

* Given that according to the constrainsts imposed by the standard
std::distance(...) is always >=0, why does the effects clause include
the superfluous "or decrements" bit?
* Current standard library implementations allow for std::distance to
be used when last < first if the iterators are random access, as the
implementation for this kind of iterators just evaluates last-first.
My hunch is that programmers also assume that they can use
std::distance in this way, so having the standard not covering this
situation is IMHO a bit dangerous.

I think the best way to handle this is to ammend the standard text
to cope with current usage, changing 24.3.4 paragraph 5 from:

  "Requires: last shall be reachable from first."

to:

  "Requires: last shall be reachable from first. For random access
iterators,
  last shall be reachable from first or first shall be reachable from
last."

Thank you,

Joaqu   n M L   pez Mu   oz
Telef   nica, Investigaci   n y Desarrollo


---
[ 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.comeaucomputing.com/csc/faq.html                      ]

Joaqu=EDn M L=F3pez Mu=F1oz <joaquin@tid.es> wrote:

>=20
> I think the best way to handle this is to ammend the standard text
> to cope with current usage, changing 24.3.4 paragraph 5 from:
>=20
>   "Requires: last shall be reachable from first."
>=20
> to:
>=20
>   "Requires: last shall be reachable from first. For random access
> iterators,
>   last shall be reachable from first or first shall be reachable from
> last."
>=20
> Thank you,
>=20
> Joaqu=EDn M L=F3pez Mu=F1oz
> Telef=F3nica, Investigaci=F3n y Desarrollo
   If your code assumes random access iterators , it fail to compile
with non random access iterators if you directly use operator -()
without a random access iterator, if you use std::disance in this case
it will compile with a forward iterator and run possibly until
'operator/os intervention", probably crashing etc.=20
   My advice is for code REQUIRING a random access iterator don't use
std::distance() just because it exists. If you use last-first idiom then
the code will not compile without a random access iterator or at least
an iterator with an operator -(cont Iterator &,const Iterator &)
overload.  It won't run off to 'La la land' when used accidently with
a forward iterator:)

 Use std::distance if your code works with forward iterators, but using
operator -() will be faster if it's really a random access iterator use
std::distance() as it becomes a 'free optimization' less the possible
unlining of std::distance().

---
[ 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.comeaucomputing.com/csc/faq.html                      ]

Joaqu=EDn M L=F3pez Mu=F1oz wrote:
> The latest draft of the C++0x standard describes the effects and
> requirements
> of std::distance as follows:
>=20
>   "Effects: Returns the number of increments or decrements needed to
> get
>   from first to last.
>   Requires: last shall be reachable from first."
>=20
[snip]


> I think the best way to handle this is to ammend the standard text
> to cope with current usage, changing 24.3.4 paragraph 5 from:
>=20
>   "Requires: last shall be reachable from first."
>=20
> to:
>=20
>   "Requires: last shall be reachable from first. For random access
> iterators,
>   last shall be reachable from first or first shall be reachable from
> last."

If code is written in the knowledge that random access iterators
are being used, it has no reason to use std::distance instead of
using operator- directly.  I can't think of any use of extending
the specification of std::distance in this way, and the uniform
nature of the current specification has some merit.  Is anything
gained by making random access iterators a special case here?

-- James

---
[ 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.comeaucomputing.com/csc/faq.html                      ]

On Nov 10, 8:39 pm, Joaqu   n M L   pez Mu   oz <joaq...@tid.es> wrote:
> The latest draft of the C++0x standard describes the effects and
> requirements of std::distance

Isn't this solved by concept-based overloading?

template <InputIterator Iter>
Iter::difference_type distance(Iter First, Iter Last);

template <BidirectionalIterator Iter>
Iter::difference_type distance(Iter First, Iter Last);

template <RandomAccessIterator Iter>
Iter::difference_type distance(Iter First, Iter Last);

Regards,
Anders Dalvander


---
[ 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.comeaucomputing.com/csc/faq.html                      ]

"Anders Dalvander" <google@dalvander.com> wrote in message
news:1194784665.504748.42240@o80g2000hse.googlegroups.com...
> Isn't this solved by concept-based overloading?
>
> template <InputIterator Iter>
> Iter::difference_type distance(Iter First, Iter Last);
>
> template <BidirectionalIterator Iter>
> Iter::difference_type distance(Iter First, Iter Last);

Even with concepts just know an iterator is by directional does not allow a
safe implemenation. How would the implementation know if it should advance
First to get to Last or decrement it? It can not test if First is before
Last from what is provided by the BidirectionalIterator concept.

Something like this might work but has issues that make it a bad idea*:
template <BidirectionalIterator Iter>
Iter::difference_type broken::distance(Iter First, Iter Last)
{
  Iter FirstBack = First;
  Iter::difference_type count = 0;
  while (First != Last) {
    ++First;
    ++count;
    if (--FirstBack == Last) return -count;
  }
  return count;
}

Issue 1 - Operation just doubled in run-time cost.
Issue 2 - What happens if the first iterator is advanced past the end of
it's valid range or before it's start? (As said in 204 this is not safe)
  std::list<int> mylist;
  mylist.push_back(5);
  mylist.push_back(6);
  broken::distance(mylist.begin(),mylist.end()); // Oops tries to go back
from begin()
  broken::distance(mylist.end(),mylist.begin()); // Oops tries to go forward
from end()

* - that said I've provided a similar specialization in some of my STL like
implementions in the past but specialized to iterator types I knew where it
was safe.

> template <RandomAccessIterator Iter>
> Iter::difference_type distance(Iter First, Iter Last);


---
[ 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.comeaucomputing.com/csc/faq.html                      ]

On Nov 11, 9:25 pm, jdenn...@acm.org (James Dennett) wrote:
> Joaqu   n M L   pez Mu   oz wrote:
>
> > I think the best way to handle this is to ammend the standard text
> > to cope with current usage, changing 24.3.4 paragraph 5 from:
>
> >   "Requires: last shall be reachable from first."
>
> > to:
>
> >   "Requires: last shall be reachable from first. For random access
> > iterators,
> >   last shall be reachable from first or first shall be reachable from
> > last."
>
> If code is written in the knowledge that random access iterators
> are being used, it has no reason to use std::distance instead of
> using operator- directly.  I can't think of any use of extending
> the specification of std::distance in this way, and the uniform
> nature of the current specification has some merit.  Is anything
> gained by making random access iterators a special case here?

Yes, because just four paragraphs earlier the Standard described how
random access iterators are a special case for both std::distance()
and std::advance(). Yet the special case described in paragraph 1 is
completely forgotten by paragraph 5. Specifically:

   - From    24.3.4/1, we can infer that std::distance() subtracts
"first" from "last" to calculates the distance between two random
access iterators
   -    24.3.4/5 requires that that distance()'s "last" iterator be
reachable from the "first" iterator (for any type of supported
iterator)

Now subtracting one random access iterator from another does not
require that the subtrahend (right operand) be reachable from the
minuend (left operand). As long as one operand is reachable from the
other - the subtraction is well-defined. So Paragraph 5 misstates the
requirements for random access iterator subtraction. Or more plainly:
Paragraph 5 is wrong.

Moreover,    24.3.4 is right to "special case" random access iterators
in the first place - because they are different. Unlike other types of
iterators, there is distance between two random access iterators -
even when the second iterator is not reachable from the first. So the
Standard should be clear that distance() and advance() do handle (last
< first) - and do so in order that client code does not have to handle
this "special case" on its own. In other words, the logic of the
library routine is intentionally non-generic - so that the client code
can be written in a generic manner.

The essential point being made here, though, is that    24.3.4 paragraph
5 cannot be reconciled with paragraph 1; and this inconsistency is -
in my view - a defect.

Greg



---
[ 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.comeaucomputing.com/csc/faq.html                      ]