Iterator/pointer arithmetic

Discussion in 'C++' started by Marc Schellens, Dec 5, 2003.

  1. 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
     
    Marc Schellens, Dec 5, 2003
    #1
    1. Advertising

  2. 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
     
    Thomas Matthews, Dec 5, 2003
    #2
    1. Advertising

  3. "Marc Schellens" <> wrote in message
    news:...
    > 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.
     
    Andrew Koenig, Dec 5, 2003
    #3
  4. "Marc Schellens" <> skrev i en meddelelse
    news:...
    > 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
     
    Peter Koch Larsen, Dec 5, 2003
    #4
  5. > 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.
     
    Andrew Koenig, Dec 5, 2003
    #5
  6. 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
     
    Karl Heinz Buchegger, Dec 5, 2003
    #6
  7. > > 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.
     
    Andrew Koenig, Dec 5, 2003
    #7
  8. "Andrew Koenig" <> wrote in message
    news:3m1Ab.395408$...
    > 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, Dec 6, 2003
    #8
  9. "Marc Schellens" <> wrote in message
    news:...
    > 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.
     
    Eugene Alterman, Dec 6, 2003
    #9
  10. Marc Schellens

    Jack Klein Guest

    On Fri, 5 Dec 2003 20:28:54 -0500, "Eugene Alterman"
    <> wrote in comp.lang.c++:

    > "Andrew Koenig" <> wrote in message
    > news:3m1Ab.395408$...
    > > 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
     
    Jack Klein, Dec 6, 2003
    #10
  11. 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
     
    Andrey Tarasevich, Dec 6, 2003
    #11
  12. > 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
     
    Marc Schellens, Dec 6, 2003
    #12
  13. Marc Schellens

    Pete Becker Guest

    Eugene Alterman wrote:
    >
    > "Andrew Koenig" <> wrote in message
    > news:3m1Ab.395408$...
    > > 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)
     
    Pete Becker, Dec 6, 2003
    #13
  14. Marc Schellens

    Dan W. Guest

    >> "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!
     
    Dan W., Dec 7, 2003
    #14
  15. 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.
     
    Marc Schellens, Dec 7, 2003
    #15
  16. Marc Schellens

    tom_usenet Guest

    On Sat, 06 Dec 2003 00:02:45 +0900, 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?


    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
     
    tom_usenet, Dec 8, 2003
    #16
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. joshc
    Replies:
    5
    Views:
    583
    Keith Thompson
    Mar 31, 2005
  2. Generic Usenet Account

    STL iterator arithmetic

    Generic Usenet Account, Nov 15, 2005, in forum: C++
    Replies:
    3
    Views:
    4,357
    Generic Usenet Account
    Nov 16, 2005
  3. Christopher
    Replies:
    0
    Views:
    776
    Christopher
    Jan 13, 2009
  4. Bo Persson
    Replies:
    1
    Views:
    638
    Marcel Müller
    Oct 11, 2009
  5. Christopher
    Replies:
    9
    Views:
    697
    Marcel Müller
    Nov 6, 2012
Loading...

Share This Page