473,322 Members | 1,409 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

Iterator/pointer arithmetic

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

Jul 22 '05 #1
15 1871
Marc Schellens wrote:
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

Jul 22 '05 #2

"Marc Schellens" <m_*********@hotmail.com> wrote in message
news:3F**************@hotmail.com...
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.
Jul 22 '05 #3

"Marc Schellens" <m_*********@hotmail.com> skrev i en meddelelse
news:3F**************@hotmail.com...
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
Jul 22 '05 #4
> 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.
Jul 22 '05 #5
Andrew Koenig wrote:
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 !=.


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.

--
Karl Heinz Buchegger
kb******@gascad.at
Jul 22 '05 #6
> > 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.


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.
Jul 22 '05 #7
"Andrew Koenig" <ar*@acm.org> wrote in message
news:3m***********************@bgtnsc04-news.ops.worldnet.att.net...
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?
Jul 22 '05 #8

"Marc Schellens" <m_*********@hotmail.com> wrote in message
news:3F**************@hotmail.com...
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.
Jul 22 '05 #9
On Fri, 5 Dec 2003 20:28:54 -0500, "Eugene Alterman"
<Eu*************@autodesk.com> wrote in comp.lang.c++:
"Andrew Koenig" <ar*@acm.org> wrote in message
news:3m***********************@bgtnsc04-news.ops.worldnet.att.net...
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?


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
Jul 22 '05 #10
Jack Klein wrote:
...
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).

--
Best regards,
Andrey Tarasevich

Jul 22 '05 #11
> 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


Jul 22 '05 #12
Eugene Alterman wrote:

"Andrew Koenig" <ar*@acm.org> wrote in message
news:3m***********************@bgtnsc04-news.ops.worldnet.att.net...
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?


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).

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Jul 22 '05 #13
>> "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!
Jul 22 '05 #14
Dan W. wrote:
"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.

Jul 22 '05 #15
On Sat, 06 Dec 2003 00:02:45 +0900, Marc Schellens
<m_*********@hotmail.com> wrote:
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
Jul 22 '05 #16

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

12
by: Roel | last post by:
Hello all, The following will not compile under gcc 3.2.2: #include <string> #include <vector> #include <iostream> #include <ctype.h> class A
29
by: Hagen | last post by:
Hello, in a recent thread "speed of vector vs array" I read about the problem of the slow acces by addressing vector elements by indexing, unfortunately I see no workaround in my case. My...
13
by: Mike Austin | last post by:
Hi all. Just working on a small virtual machine, and thought about using vector iterators instead of pointer arithmetic. Question is, why does an iterator plus any number out of range not...
13
by: jois.de.vivre | last post by:
Hi All, I'm trying to write a wrapper class for std::vector to extend some of its functionality. The problem I'm getting into is returning an iterator type from a member function. Here is the...
2
by: ul | last post by:
Hello, Just wonder what is faster for std::vector, const_iterator od iterator? Or is this stl-realisation-dependent? Target compilator gcc platform is Linux. Thanks
0
by: mailforpr | last post by:
Hi. Let me introduce an iterator to you, the so-called "Abstract Iterator" I developed the other day. I actually have no idea if there's another "Abstract Iterator" out there, as I have never...
16
by: Juha Nieminen | last post by:
I'm actually not sure about this one: Does the standard guarantee that if there's at least one element in the data container, then "--container.end()" will work and give an iterator to the last...
12
by: Howard | last post by:
Is there an easy way to get an iterator (*not* a reverse-iterator) to the last element in a list? The last() function returns the element itself, not an iterator. Thanks, -Howard
4
by: pandit | last post by:
Hello i dont understand how to Deal with iterator. its little bit confusing ? how they work??
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.