Iterator/pointer arithmetic

[Marc Schellens]

I have a:

vector<A> V;

an

A* a;

which might point to one element of V.

How to check this most quickly?

I am using for now something like

if( V.size() > 0 && a >= &V[0] && a <= &V[ V.size()] ) { it_is_in();}

which works fine for me, but is this standard conform?
And if not: My application will never run on an embedded system.
Does anybody know any existing standard conform compiler on lets
say any unix-workstation, windows system, mac or even VMS
where the above code would produce not the expected?

thanks,
marc

 

[Thomas Matthews]

I have a:

vector<A> V;

an

A* a;

which might point to one element of V.

How to check this most quickly?

I am using for now something like

if( V.size() > 0 && a >= &V[0] && a <= &V[ V.size()] ) { it_is_in();}

which works fine for me, but is this standard conform?
And if not: My application will never run on an embedded system.
Does anybody know any existing standard conform compiler on lets
say any unix-workstation, windows system, mac or even VMS
where the above code would produce not the expected?

thanks,
marc

Pointer arithmetic depends on the properties of the pointer.
All pointers can be compared to NULL (== and !=). Other
comparisons are not guaranteed and may have unexpected behavior.
A pointer can be moved via addition or subtraction. Any other
arithmetic operations (e.g. multiplication, division, shifting)
may induce unexpected behavior.

In many embedded systems, pointers are converted to integers
and compared as integers. This assumes a flat and linear
addressing space, though.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[Andrew Koenig]

I have a:

vector<A> V;

an

A* a;

which might point to one element of V.

How to check this most quickly?

There is no portable way to determine whether a completely unknown pointer
points at a particular object.

 

[Peter Koch Larsen]

I have a:

vector<A> V;

an

A* a;

which might point to one element of V.

How to check this most quickly?

I am using for now something like

if( V.size() > 0 && a >= &V[0] && a <= &V[ V.size()] ) { it_is_in();}

which works fine for me, but is this standard conform?
And if not: My application will never run on an embedded system.
Does anybody know any existing standard conform compiler on lets
say any unix-workstation, windows system, mac or even VMS
where the above code would produce not the expected?

thanks,
marc

To my knowledge, this can not be done in a standards-conforming way. If,
however, You target a known platform (such as Windows), I would not worry to
much about it if it is debug-code (and it looks very much as it is). You
forgot, however to check if a points to a boundary (eg. at V[0], V[1] or...)
and not to some random place (a = (A*)V[0].field). This requires even
dirtier code ;-)
If your code is not debug-code, I suggest you reconsider if your design is
ok.

Kind regards
Peter

 

[Andrew Koenig]

Pointer arithmetic depends on the properties of the pointer.

All pointers can be compared to NULL (== and !=). Other
comparisons are not guaranteed and may have unexpected behavior.

Not true. Two pointers that point to objects (or one past objects) can
always be compared for == and !=.

The trouble is that there are some pointers that are indeterminate -- they
are not null, and they do not point to objects. Such pointers cannot be
compared, or, for that matter, copied.

 

[Karl Heinz Buchegger]

Not true. Two pointers that point to objects (or one past objects) can
always be compared for == and !=.

Maybe my memory serves me wrong right now. But what about < and >? If I
remember correctly there is also a guarantee if the pointers point into
the same array.

 

[Andrew Koenig]

Not true. Two pointers that point to objects (or one past objects) can

Maybe my memory serves me wrong right now. But what about < and >? If I
remember correctly there is also a guarantee if the pointers point into
the same array.

Two pointers to elements of the same array can be compared with <, >, <=,
and >= as well as == and !=. But unless you already know that the pointers
point to elements of the same array, you can't count on the results from
order comparisons.

 

[Eugene Alterman]

There is no portable way to determine whether a completely unknown pointer
points at a particular object.

So you are saying that according to the standard a pointer may compare
equal to the address of an object
without actually pointing to any object, aren't you?
Can this actually happen on any existing platform?

 

[Eugene Alterman]

I have a:

vector<A> V;

an

A* a;

which might point to one element of V.

How to check this most quickly?

I am using for now something like

if( V.size() > 0 && a >= &V[0] && a <= &V[ V.size()] ) { it_is_in();}

You mean a <= &V[V.size() - 1] , don't you?
Or, better yet,
if(!V.empty() && a >= &V.front() && a <= &V.back())

which works fine for me, but is this standard conform?
And if not: My application will never run on an embedded system.
Does anybody know any existing standard conform compiler on lets
say any unix-workstation, windows system, mac or even VMS
where the above code would produce not the expected?

This is what guaranteed under the latest standard revision (and arguably by
all the known implementations):

"The elements of a vector are stored contiguosly, meaning that if v is a
vector <T, Allocator> where T is some type other that bool, then it obeys
the identity
&v[n] == &v[0] + n for all 0 <= n < v.size()."

The gurus, apparently, don't think it is enough. What do you know...

Still, I believe that in practice (and most certainly on systems with flat
memory model) you are fine.

 

[Jack Klein]

So you are saying that according to the standard a pointer may compare
equal to the address of an object
without actually pointing to any object, aren't you?
Can this actually happen on any existing platform?

No, that's not what he said, nor what he meant.

If you have an array of N objects of type T:

T t_array [N];

....and an unknown pointer to a type T object that you suspect might be
a pointer to one of the N elements of t_array:

T *A;

....then the code:

bool found_it = false;

for (int x = 0; x < N; ++x)
{
if (A == (t_array + x))
{
found_it = true;
}
}

....will have defined behavior and set found_it to true if and only if
A actually does point to one of the elements of t_array.

But if A points to a T object that is separate from t_array, each and
every one of the N comparisons in the loop has undefined behavior.

If the A pointer happened to point to a T object allocated with new,
and then deleted, it is now indeterminate, and just accessing the
pointer's value without dereferencing it could produce undefined
behavior. On a platform with virtual memory, the memory block that A
existed in might have been unmapped from the program's memory space,
and merely loading that value into a pointer register might trigger a
hardware trap that shuts down the program.

Two pointers may be compared only if they both point to elements of
the same array, or to one past the end of an array. What happens if
you break this rule can vary with the hardware platform involved, so
the language standard merely leaves it undefined.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

 

[Andrey Tarasevich]

...
If you have an array of N objects of type T:

T t_array [N];

...and an unknown pointer to a type T object that you suspect might be
a pointer to one of the N elements of t_array:

T *A;

...then the code:

bool found_it = false;

for (int x = 0; x < N; ++x)
{
if (A == (t_array + x))
{
found_it = true;
}
}

...will have defined behavior and set found_it to true if and only if
A actually does point to one of the elements of t_array.

But if A points to a T object that is separate from t_array, each and
every one of the N comparisons in the loop has undefined behavior.

What exactly do you understand under "T object that is separate from
t_array" ? If 'A' a valid pointer that points to some completely
independent object of type 'T', all comparisons n the above cycle are
valid and the behavior is perfectly defined. The result will be
'found_it == false', of course.

If the A pointer happened to point to a T object allocated with new,
and then deleted, it is now indeterminate, and just accessing the
pointer's value without dereferencing it could produce undefined
behavior. On a platform with virtual memory, the memory block that A
existed in might have been unmapped from the program's memory space,
and merely loading that value into a pointer register might trigger a
hardware trap that shuts down the program.

That's true.

Two pointers may be compared only if they both point to elements of
the same array, or to one past the end of an array. What happens if
you break this rule can vary with the hardware platform involved, so
the language standard merely leaves it undefined.

That's the case for _relatonal_ comparisons. But that's not the case for
_equality_ comparisons. In C++ equality comparisons are allowed even
between pointers that are pointing to elements of different arrays (in
this context standalone objects are treated as one-element arrays).

 

[Marc Schellens]

You mean a <= &V[V.size() - 1] , don't you?

Or, better yet,
if(!V.empty() && a >= &V.front() && a <= &V.back())

Well, thats what I meant. Thanks.

which works fine for me, but is this standard conform?
And if not: My application will never run on an embedded system.
Does anybody know any existing standard conform compiler on lets
say any unix-workstation, windows system, mac or even VMS
where the above code would produce not the expected?

This is what guaranteed under the latest standard revision (and arguably by
all the known implementations):

"The elements of a vector are stored contiguosly, meaning that if v is a
vector <T, Allocator> where T is some type other that bool, then it obeys
the identity
&v[n] == &v[0] + n for all 0 <= n < v.size()."

And from other posts I got that >= and <= are valid, if *a is an element
of V. So if its 'true', its even guaranteed to work.

The gurus, apparently, don't think it is enough. What do you know...

Still, I believe that in practice (and most certainly on systems with flat
memory model) you are fine.

I will go with it. I also cannot believe that there is any existing
workstation/PC system where it would fail.
If I run into trouble, I can switch to the one by one comparisson anyway.
Maybe it would make sense if there would be a more relaxed
'sub'-standard for 'regular' hardware.

And thanks to everybody who answered.
Indeed I know, that
A* a;
points to a valid object.

The code is not debugging code. It's part of the real program.
Therfore performance matters.
So as I understood, a comparisson against every element of
V would be conform. But slow.

Maybe the standard should provide a contains_element(...) method for the
containers...

marc

 

[Pete Becker]

So you are saying that according to the standard a pointer may compare
equal to the address of an object
without actually pointing to any object, aren't you?

Or it could point to a different object.

Can this actually happen on any existing platform?

Yes. Mixing near and far pointers on segmented architectures can do this
(16-bit Windows, for example).

 

[Dan W.]

"The elements of a vector are stored contiguosly, meaning that if v is a

vector <T, Allocator> where T is some type other that bool, then it obeys
the identity
&v[n] == &v[0] + n for all 0 <= n < v.size()."

And from other posts I got that >= and <= are valid, if *a is an element
of V. So if its 'true', its even guaranteed to work.

If you take the address of an object and 'immediately' compare it with
the boundary addresses of the vector, it should work. However, if
your pointer is a few minutes old, the vector may have been resized,
which in most if not all cases means reallocated, and the test will be
false even though your object is in the vector, just that the vector
moved.
Careful!

 

[Marc Schellens]

"The elements of a vector are stored contiguosly, meaning that if v is a
vector <T, Allocator> where T is some type other that bool, then it obeys
the identity
&v[n] == &v[0] + n for all 0 <= n < v.size()."

And from other posts I got that >= and <= are valid, if *a is an element
of V. So if its 'true', its even guaranteed to work.

If you take the address of an object and 'immediately' compare it with
the boundary addresses of the vector, it should work. However, if
your pointer is a few minutes old, the vector may have been resized,
which in most if not all cases means reallocated, and the test will be
false even though your object is in the vector, just that the vector
moved.
Careful!

Well, first it isn't resized (in this case)
and second this would apply to any vector iterator anyway.

 

[tom_usenet]

I have a:

vector<A> V;

an

A* a;

which might point to one element of V.

How to check this most quickly?

If it must be portable, the quickest way is to use std::find to
perform a linear search, == comparing the address of each element. If
portability doesn't matter then:

bool inVector = (v.size() > 0 && a >= &v.front() && a <= &v.back());

This works on most, but not all, platforms (some platforms have
inconsistent pointer comparisons for objects from different

I am using for now something like

if( V.size() > 0 && a >= &V[0] && a <= &V[ V.size()] ) { it_is_in();}

which works fine for me, but is this standard conform?
And if not: My application will never run on an embedded system.
Does anybody know any existing standard conform compiler on lets
say any unix-workstation, windows system, mac or even VMS
where the above code would produce not the expected?

I suspect some libraries might assert if you pass V.size() to
operator[]. DOS (DJGPP) might produce odd results when the code is
corrected (e.g. false trues!).

Tom

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html