Pointer Difference Arithmetic - C++ language, library and standards

C++Talk.NET
C++ language newsgroups

Archives

FAQ

Memberlist

Usergroups

Profile

Pointer Difference Arithmetic

C++Talk.NET Forum Index -> C++ language, library and standards

View previous topic :: View next topic

Author

Message

Frederick Gotham
Guest

Posted: Tue Aug 08, 2006 5:06 pm Post subject: Pointer Difference Arithmetic

Over on comp.lang.c++.moderated, Matthias Hofmann has noticed a technicality
in the Standard:

Quote:

Strangely, section 5.7/6 does not explicitly guarantee that this is
legal C++: "When two pointers to elements of the same array object are
subtracted, the result is the difference of the subscripts of the two
array elements."

This paragraph brings into doubt whether the following code is OK:

int array[5];

int *p = array + 5;

ptrdiff_t i = p - &array[0];

Is this code legal? Strictly speaking, "p" doesn't point to an element of the
array.

Perhaps the next Standard should clarify this matter?

--

Frederick Gotham

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

Greg Herlihy
Guest

Posted: Wed Aug 09, 2006 4:42 pm Post subject: Re: Pointer Difference Arithmetic

Frederick Gotham wrote:

Quote:

Over on comp.lang.c++.moderated, Matthias Hofmann has noticed a technicality
in the Standard:

Strangely, section 5.7/6 does not explicitly guarantee that this is
legal C++: "When two pointers to elements of the same array object are
subtracted, the result is the difference of the subscripts of the two
array elements."

This paragraph brings into doubt whether the following code is OK:

int array[5];

int *p = array + 5;

ptrdiff_t i = p - &array[0];

Is this code legal? Strictly speaking, "p" doesn't point to an element of the
array.

The code is legal. The question perhaps is whether "i" has a defined
value. The unsurprising answer is that i does have a defined value. And
here's how we can prove it:

First, we'll introduce a "q" pointer variable into the original program
that points to the last element of the array.

int array[5];

int *p = array + 5;
int *q = array + 4;

Now, the plan is simple: use q in two pointer arithmetic expressions
whose value is defined and then add them together.

(p - q) + (q - array);

Next we take advantage of the fact that the additive operators are
associative for built-in types to transform the above calculation into:

p + (-q + q) - array;

Since the Standard tells us that a pointer subtracted from itself is
zero, and that zero added to a pointer does not change that pointer's
value - we can safely eliminate the middle portion of this calculation,
leaving just:

p - array;

So via substitution, the last line in the original program could be
written as:

ptr_diff i = (p - q) + (q - array);

meaning that i's value is defined (as the sum of two defined, integral
values).

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 ]

Guest

Posted: Wed Aug 09, 2006 10:36 pm Post subject: Re: Pointer Difference Arithmetic

Frederick Gotham wrote:

Quote:

5.7/6 addresses this in the fourth sentence after the one you quote:

Moreover, if the expression P points either to an element of an
array object or one past the last element of an array object,
and the expression Q points to the last element of the same
array object, the expression ((Q) + 1) - (P) has the same value
as ((Q) - (P)) + 1 and as - ((P) - ((Q) + 1)), and has the value
zero if the expression P points one past the last element of
the array object, even though the expression (Q) + 1 does not
point to an element of the array object.

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

Greg Herlihy
Guest

Posted: Wed Aug 09, 2006 10:38 pm Post subject: Re: Pointer Difference Arithmetic

Seungbeom Kim wrote:

Quote:

Greg Herlihy wrote:

(p - q) + (q - array);

Next we take advantage of the fact that the additive operators are
associative for built-in types to transform the above calculation into:

p + (-q + q) - array;

Additive operators are associative? Not true in general.

Additive operators are associative for all real numbers. And I would
consider the set of all reals, a pretty "general" case.

Now the sets of numbers particular to C++
they are certainly associative in this example

Quote:

Only if there is a risk of overflow. Given the following relation:

array < q < p;

there is no chance that measuring the distance between array and q or
between p and q would overflow if the distance from p to array does not
overflow. And that is all that shown above. The value i will have the
same (possibly implementation-defined value) as (p - q) + (q - array).

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 ]

Seungbeom Kim
Guest

Posted: Wed Aug 09, 2006 11:23 pm Post subject: Re: Pointer Difference Arithmetic

Greg Herlihy wrote:

Quote:

(p - q) + (q - array);

Next we take advantage of the fact that the additive operators are
associative for built-in types to transform the above calculation into:

p + (-q + q) - array;

Additive operators are associative? Not true in general.

See 1.9/15; it says certain restrictions apply for associativity or
commutativity to hold, but it's basically a rephrase of the as-if rule,
and we may just as well say that operators are not associative or
commutative.

--
Seungbeom Kim

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

Frederick Gotham
Guest

Posted: Thu Aug 10, 2006 12:26 am Post subject: Re: Pointer Difference Arithmetic

Seungbeom Kim posted:

Quote:

Do you not mean commutative? Only unsigned arithmetic is commutative.

The following may produce undefined behaviour:

65535 + 5 - 400

while the following is perfectly sound:

65535 - 400 +5

--

Frederick Gotham

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

Guest

Posted: Thu Aug 10, 2006 6:12 am Post subject: Re: Pointer Difference Arithmetic

Greg Herlihy wrote:

Quote:

Seungbeom Kim wrote:
Greg Herlihy wrote:

(p - q) + (q - array);

Next we take advantage of the fact that the additive operators are
associative for built-in types to transform the above calculation into:

p + (-q + q) - array;

Additive operators are associative? Not true in general.

Additive operators are associative for all real numbers. And I would
consider the set of all reals, a pretty "general" case.

There's key differences between mathematical operators acting on real
numbers, and C++ operators acting on representations of arithmetic
types. The C++ operators operations are not, in general, either
associative nor commutative. They have finite upper and lower limits,
and for floating point numbers they have a finite precision that varies
depending upon the value being represented. They are associated and
commutative, when the values involved in the operations allow them to
be, as accurately as those values allow them to be, but it's not
possible for them to be associative for all sets of values, and for
floating point values they can't be exactly associative even for some
sets of values where it's possible for them to be approximately
associative.

Pointer arithmetic is another matter entirely. It's connected to math
only because it's defined in terms of positions in an array. That
connection means it's closely realited to integer arithmetic. However,
that definition only applies to pointers to positions within the array,
and by dint of special rules, it has been extended to include positions
one past the end of the array. Those rules say nothing that allow you
to extend associativity to include pointers that don't point into the
array, and don't point one past the end of the array. Instead, it
explicit says that simply creating such pointers has undefined
behavior; it says that for the simple reason that there are real, and
popular, architectures where creation of such pointers can cause your
program to abort.

Quote:

Now the sets of numbers particular to C++
they are certainly associative in this example
See 1.9/15; it says certain restrictions apply for associativity or
commutativity to hold, but it's basically a rephrase of the as-if rule,
and we may just as well say that operators are not associative or
commutative.

Only if there is a risk of overflow. Given the following relation:

array < q < p;

there is no chance that measuring the distance between array and q or
between p and q would overflow if the distance from p to array does not
overflow. And that is all that shown above. The value i will have the
same (possibly implementation-defined value) as (p - q) + (q - array).

There's no gurantee what it will have. All uses of p and q in either
expression, (p-q)+(q-array) or p-array, make the behavior of your
program undefined.

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

Guest

Posted: Thu Aug 10, 2006 2:48 pm Post subject: Re: Pointer Difference Arithmetic

Greg Herlihy wrote:
..

Quote:

Next we take advantage of the fact that the additive operators are
associative for built-in types ...

Citation, please?

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

skaller
Guest

Posted: Fri Aug 11, 2006 9:10 am Post subject: Re: Pointer Difference Arithmetic

On Thu, 10 Aug 2006 00:12:58 -0600, kuyper wrote:

Quote:

Greg Herlihy wrote:
Seungbeom Kim wrote:

The C++ operators operations are not, in general, either
associative nor commutative. They have finite upper and lower limits,

For unsigned types, addition and multiplication are necessarily
associative and commutative for all values. This follows directly
from the fact that they're cyclic groups with respect to both
addition and multiplication (group operators are always associative).

For signed types, I believe the correct qualifier to use is 'locally'.
This rough meaning of locally is: for suitably small compact
sets near zero. To be precise:

For small enough d > 0, then for all | i1 | < d and | i2 | < d
and | i3 | < d then

i1 + (i2 + i3) = (i1 + i2) + i3

and similarly for commutative, and similarly for multiplication.
In all these cases, we can actually calculate the largest possible
value of d. Clearly, adding a set of n integers and getting the
same result independently of order of addition will increasingly
constrain the bound d. In fact, for addition, the bound is easily
calculated and close to MAXINT/n. For multiplication of course,
the bound rapidly drops to 1.

In fact in many 'pragmatic' calculations, programmers assume
associativity. We use 'int' and calculate things without carefully
considering whether we need to order the calculations to avoid
overflow, because usually all the possible partial results are
well within the reasonable bounds.

Unfortunately, in some cases, there's a difference between
the expected data, and what is possible. For a classic error
in a classic textbook: Foley and van Dam get this wrong
in the Beshnam (sp?) line drawing algorithm. This is an algorithm
to draw a line on a 2 dimensional grid: their calculation
is actually incorrect when the line is almost infinitely
steep, because addition and division only distribute locally:

(a + b)/2

is NOT the same as

a/2 + b/2

The latter cannot overflow. The former calculation can.
What's more .. the two give different results even when they
do not overflow:

(3 + 3)/2 = 3
3/2 + 3/2 = 2

It is not so easy to calculate (a+b)/2 correctly without overflow!

--
John Skaller <skaller at users dot sf dot net>
Try Felix, the successor to C++ http://felix.sf.net

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

Guest

Posted: Fri Aug 11, 2006 4:25 pm Post subject: Re: Pointer Difference Arithmetic

skaller wrote:

Quote:

On Thu, 10 Aug 2006 00:12:58 -0600, kuyper wrote:
..
The C++ operators operations are not, in general, either
associative nor commutative. They have finite upper and lower limits,

For unsigned types, addition and multiplication are necessarily
associative and commutative for all values. This follows directly
from the fact that they're cyclic groups with respect to both
addition and multiplication (group operators are always associative).

That's why I used the qualifier "generally". Since the context was
pointer arithmetic, which is not an exception, I didn't want to go into
the details of the cases that are exceptions,.

..

Quote:

For signed types, I believe the correct qualifier to use is 'locally'.
This rough meaning of locally is: for suitably small compact
sets near zero. To be precise:

For small enough d > 0, then for all | i1 | < d and | i2 | < d
and | i3 | < d then

i1 + (i2 + i3) = (i1 + i2) + i3

Note that while this is possible for integers, there's no value you can
choose for 'd' that will make that exactly true for floating point
types. The best you can do is have it be approximately true, and to
place upper limits on the size of the discrepancy.

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

Harald van DÄ³k
Guest

Posted: Fri Aug 11, 2006 9:13 pm Post subject: Re: Pointer Difference Arithmetic

skaller wrote:

Quote:

In fact in many 'pragmatic' calculations, programmers assume
associativity. We use 'int' and calculate things without carefully
considering whether we need to order the calculations to avoid
overflow, because usually all the possible partial results are
well within the reasonable bounds.

Unfortunately, in some cases, there's a difference between
the expected data, and what is possible. For a classic error
in a classic textbook: Foley and van Dam get this wrong
in the Beshnam (sp?) line drawing algorithm. This is an algorithm
to draw a line on a 2 dimensional grid: their calculation
is actually incorrect when the line is almost infinitely
steep, because addition and division only distribute locally:

(a + b)/2

is NOT the same as

a/2 + b/2

The latter cannot overflow. The former calculation can.

Actually, can't both overflow if INT_MIN is odd and division rounds down?
Rounding to zero is apparently recommended, and required in C99, but not
yet required in C++, right?

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

James Kanze
Guest

Posted: Wed Aug 16, 2006 12:08 am Post subject: Re: Pointer Difference Arithmetic

kuyper (AT) wizard (DOT) net wrote:

Quote:

Greg Herlihy wrote:
Seungbeom Kim wrote:
Greg Herlihy wrote:
(p - q) + (q - array);

Next we take advantage of the fact that the additive
operators are associative for built-in types to transform
the above calculation into:

p + (-q + q) - array;
Additive operators are associative? Not true in general.

Additive operators are associative for all real numbers. And
I would consider the set of all reals, a pretty "general"
case.

There's key differences between mathematical operators acting
on real numbers, and C++ operators acting on representations
of arithmetic types. The C++ operators operations are not, in
general, either associative nor commutative. They have finite
upper and lower limits, and for floating point numbers they
have a finite precision that varies depending upon the value
being represented. They are associated and commutative, when
the values involved in the operations allow them to be, as
accurately as those values allow them to be, but it's not
possible for them to be associative for all sets of values,
and for floating point values they can't be exactly
associative even for some sets of values where it's possible
for them to be approximately associative.

Pointer arithmetic is another matter entirely. It's connected
to math only because it's defined in terms of positions in an
array. That connection means it's closely realited to integer
arithmetic. However, that definition only applies to pointers
to positions within the array, and by dint of special rules,
it has been extended to include positions one past the end of
the array.

And it isn't always defined then. Given two pointers, p and q,
the results of p-q are defined only if they can be represented
in a ptrdiff_t. And on most machines, this isn't at all
guaranteed.

Still, of course, you've hit the nail on the head. Mathematics
doesn't deal with pointer arithmetic, because mathematics
doesn't know what a pointer is. All we have to go on with
regards to pointer arithmetic is what the standard says.

[...]

Quote:

See 1.9/15; it says certain restrictions apply for
associativity or commutativity to hold, but it's basically a
rephrase of the as-if rule, and we may just as well say that
operators are not associative or commutative.

Only if there is a risk of overflow. Given the following
relation:

array < q < p;

there is no chance that measuring the distance between array
and q or between p and q would overflow if the distance from
p to array does not overflow.

Define overflow for pointer arithmetic. (And of course, there
isn't the slightest guarantee that p - array will not overflow,
so your if doesn't hold.)

--
James Kanze kanze.james (AT) neuf (DOT) fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34

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

James Kanze
Guest

Posted: Wed Aug 16, 2006 4:08 am Post subject: Re: Pointer Difference Arithmetic

Greg Herlihy wrote:

Quote:

Seungbeom Kim wrote:
Greg Herlihy wrote:
(p - q) + (q - array);

Next we take advantage of the fact that the additive
operators are associative for built-in types to transform
the above calculation into:

p + (-q + q) - array;
Additive operators are associative? Not true in general.

Additive operators are associative for all real numbers. And I
would consider the set of all reals, a pretty "general" case.

We're talking about programming languages here, and particularly
C++. And no programming language supports the set of all reals.
Additive operators are NOT associative in C++, except for
unsigned integral types.

Quote:

Nonsense. That's only true for integral types, not for all
arithmetic types. And of course, we don't even know what
overflow means when applied to a pointer.

Quote:

Given the following relation:

array < q < p;

there is no chance that measuring the distance between array
and q or between p and q would overflow if the distance from p
to array does not overflow. And that is all that shown above.
The value i will have the same (possibly
implementation-defined value) as (p - q) + (q - array).

Only if the standard requires it to. Which, as far as I know,
isn't the case.

--
James Kanze kanze.james (AT) neuf (DOT) fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34

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

Display posts from previous:

	C++Talk.NET Forum Index -> C++ language, library and standards	All times are GMT
Page 1 of 1

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum