set of pointers

Discussion in 'C++' started by REH, Feb 26, 2008.

  1. REH

    REH Guest

    Is it well defined to use a std::set of pointers? I ask because of
    the restrictions on using relational operators with pointers. Does a
    set of pointers suffer from the same restrictions, or does the
    standard require it to be supported. I can't find any information one
    way or the other in the standard or from other sources.

    Thanks,
    REH
     
    REH, Feb 26, 2008
    #1
    1. Advertising

  2. REH

    Fei Liu Guest

    REH wrote:
    > Is it well defined to use a std::set of pointers? I ask because of
    > the restrictions on using relational operators with pointers. Does a
    > set of pointers suffer from the same restrictions, or does the
    > standard require it to be supported. I can't find any information one
    > way or the other in the standard or from other sources.
    >
    > Thanks,
    > REH


    std::set of pointers are well supported, pointers have value semantic,
    comparable.

    The relational operators you refer work fine because pointers can be
    compared by value.

    Fei
     
    Fei Liu, Feb 26, 2008
    #2
    1. Advertising

  3. REH

    Lance Diduck Guest

    On Feb 26, 10:31 am, REH <> wrote:
    > Is it well defined to use a std::set of pointers?  I ask because of
    > the restrictions on using relational operators with pointers.  Does a
    > set of pointers suffer from the same restrictions, or does the
    > standard require it to be supported.  I can't find any information one
    > way or the other in the standard or from other sources.
    >
    > Thanks,
    > REH


    Since pointers implement operator< as required by std::set, then it is
    possible to use pointers.
    Note that what is being compared is the actual address being stored in
    the pointer, and not what it points to.

    Lance
     
    Lance Diduck, Feb 26, 2008
    #3
  4. REH

    red floyd Guest

    REH wrote:
    > Is it well defined to use a std::set of pointers? I ask because of
    > the restrictions on using relational operators with pointers. Does a
    > set of pointers suffer from the same restrictions, or does the
    > standard require it to be supported. I can't find any information one
    > way or the other in the standard or from other sources.
    >


    In addition to what everyone here has discussed so far, you can provide
    a custom comparison functor for your set, so you can sort it based on
    what the pointers refer to, rather than the raw pointers themselves.
     
    red floyd, Feb 26, 2008
    #4
  5. In message
    <>,
    Lance Diduck <> writes
    >On Feb 26, 10:31 am, REH <> wrote:
    >> Is it well defined to use a std::set of pointers?  I ask because of
    >> the restrictions on using relational operators with pointers.  Does a
    >> set of pointers suffer from the same restrictions, or does the
    >> standard require it to be supported.  I can't find any information one
    >> way or the other in the standard or from other sources.


    Look again...

    >
    >Since pointers implement operator< as required by std::set,


    No. According to 5.9/2 [expr.rel], among other restrictions:

    "If two pointers p and q of the same type point to different objects
    that are not members of the same object or elements of the same array or
    to different functions, or if only one of them is null, the results of
    p<q, p>q, p<=q, and p>=q are unspecified."

    Putting it loosely, the effect is that operator< is only defined for
    pointers to elements of the same array, or (but not always) data members
    of the same object.

    But std::less (which is what std::set uses by default, not operator<) is
    required by 20.3.3/8 to define an ordering on pointers even when
    operator< does not.

    So this is still true:

    >then it is
    >possible to use pointers.



    >Note that what is being compared is the actual address being stored in
    >the pointer, and not what it points to.


    Not necessarily the "address". If the pointers aren't into the same
    array, std::less may have to use compiler magic to define an ordering.

    --
    Richard Herring
     
    Richard Herring, Feb 26, 2008
    #5
  6. > Since pointers implement operator< as required by std::set, then it is
    > possible to use pointers.


    The conclusion is correct, but the reasoning is wrong.

    If p and q are pointers, p<q is defined only if p and q point to elements of
    the same array. However, std::less(p,q) is defined as an order relation for
    all valid values of p and q, and is required to be consistent with p<q for
    all values of p and q for which p<q is defined.

    std::set, in turn, uses std::less, which means that it works with pointers
    even in those cases that p<q isn't required to work.
     
    Andrew Koenig, Feb 26, 2008
    #6
  7. REH

    REH Guest

    On Feb 26, 10:45 am, Lance Diduck <> wrote:
    > Since pointers implement operator< as required by std::set, then it is
    > possible to use pointers.
    > Note that what is being compared is the actual address being stored in
    > the pointer, and not what it points to.
    >
    > Lance


    Thanks for replying, but you are not correct. Pointers are not
    necessarily addresses, and the standard only allows pointers to be
    relationally compared if they come from the same object (i.e., the
    same struct or array).

    REH
     
    REH, Feb 26, 2008
    #7
  8. REH

    REH Guest

    On Feb 26, 11:32 am, Richard Herring <junk@[127.0.0.1]> wrote:

    > Putting it loosely, the effect is that operator< is only defined for
    > pointers to elements of the same array, or (but not always) data members
    > of the same object.
    >
    > But std::less (which is what std::set uses by default, not operator<) is
    > required by 20.3.3/8 to define an ordering on pointers even when
    > operator< does not.
    >


    Thanks Richard (and Andrew). I didn't think to look at what the
    standard says about less, and I should have.

    REH
     
    REH, Feb 26, 2008
    #8
  9. REH

    REH Guest

    On Feb 26, 10:44 am, Fei Liu <> wrote:
    > std::set of pointers are well supported, pointers have value semantic,
    > comparable.
    >
    > The relational operators you refer work fine because pointers can be
    > compared by value.
    >
    > Fei


    Your logic doesn't hold. Pointers can only be relationally compared
    if they are from the same struct, array, etc.

    REH
     
    REH, Feb 26, 2008
    #9
  10. Richard Herring wrote:
    > No. According to 5.9/2 [expr.rel], among other restrictions:
    >
    > "If two pointers p and q of the same type point to different objects
    > that are not members of the same object or elements of the same array or
    > to different functions, or if only one of them is null, the results of
    > p<q, p>q, p<=q, and p>=q are unspecified."


    I understand that to mean that if you have two pointers, there's no
    way of knowing if the first one will evaluate as "smaller than" the
    second one (other than actually testing with "p < q"). In other words,
    you can't assume that if you eg. allocated two blocks of memory to two
    pointers, the first pointer will evaluate to be "smaller than" the
    second one. It can be either way, there's no guarantee.

    However, if you have two pointers p and q, and p evaluates to be
    "smaller than" q, it will *always* do so. The "p < q" will not give
    random results, but it will always give true in this case.

    In other words, if the values of p and q don't change, then the value
    of "p < q" will never change either. This means that pointers can indeed
    be used in a set/map without any problems. You just can't know in which
    order they will end up there, that's all.

    The paragraph you quoted specifically mentions that two pointers
    pointing to elements in the same array have a well defined order. That's
    because arrays are defined as being one contiguous blocks of memory, and
    a later element in the array is guaranteed have a larger memory location
    than an earlier element. For this reason &array[6] will always be
    smaller than &array[10]. The same goes for struct/class member variables.
     
    Juha Nieminen, Feb 26, 2008
    #10
  11. REH

    Kai-Uwe Bux Guest

    Juha Nieminen wrote:

    > Richard Herring wrote:
    >> No. According to 5.9/2 [expr.rel], among other restrictions:
    >>
    >> "If two pointers p and q of the same type point to different objects
    >> that are not members of the same object or elements of the same array or
    >> to different functions, or if only one of them is null, the results of
    >> p<q, p>q, p<=q, and p>=q are unspecified."

    >
    > I understand that to mean that if you have two pointers, there's no
    > way of knowing if the first one will evaluate as "smaller than" the
    > second one (other than actually testing with "p < q"). In other words,
    > you can't assume that if you eg. allocated two blocks of memory to two
    > pointers, the first pointer will evaluate to be "smaller than" the
    > second one. It can be either way, there's no guarantee.
    >
    > However, if you have two pointers p and q, and p evaluates to be
    > "smaller than" q, it will *always* do so. The "p < q" will not give
    > random results, but it will always give true in this case.


    I don't find any language in the standard supporting that point of view. The
    standard defines "unspecified behavior" as follows [1.3.13]:

    behavior, for a well-formed program construct and correct data, that
    depends on the implementation. The implementation is not required to
    document which behavior occurs. [Note: usually, the range of possible
    behaviors is delineated by this International Standard. ]

    I don't find any delineation of possible behaviors for p<q in the
    unspecified case. Thus, nothing in the standard prevents the implementation
    from calling a random number generator when evaluating an unspecified p<q.


    > In other words, if the values of p and q don't change, then the value
    > of "p < q" will never change either. This means that pointers can indeed
    > be used in a set/map without any problems. You just can't know in which
    > order they will end up there, that's all.


    You say "which order they end up". Hm, I don't think you are guaranteed that
    p<q defines an order on pointers in the case of unspecified results (even
    assuming that the result is well-defined and does not randomly change from
    one evaluation of p<q to the next). In particular, if set/map were to use
    operator< for comparison, which they don't, pointers could not be used in
    set/map. That is the reason that the standard requires std::less<T*> to be
    an ordering.


    [snip]


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Feb 26, 2008
    #11
  12. REH

    James Kanze Guest

    On Feb 26, 4:44 pm, Fei Liu <> wrote:
    > REH wrote:
    > > Is it well defined to use a std::set of pointers? I ask
    > > because of the restrictions on using relational operators
    > > with pointers. Does a set of pointers suffer from the same
    > > restrictions, or does the standard require it to be
    > > supported. I can't find any information one way or the
    > > other in the standard or from other sources.


    > std::set of pointers are well supported, pointers have value
    > semantic, comparable.


    > The relational operators you refer work fine because pointers
    > can be compared by value.


    Pointers are only comparable for inequality (e.g. <) if they
    point into the same object or array. You can't expect to
    compare two arbitrary pointers and get anything meaningful. (It
    does actually work on a lot of machines, but not always on Intel
    architectures.)

    You can use pointers in std::set, however, since std::set
    doesn't use the < operator, but rather std::less, and the
    standard requires the implementation to make this work, even if
    the < operator doesn't work.

    --
    James Kanze (GABI Software) email:
    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
     
    James Kanze, Feb 26, 2008
    #12
  13. REH

    James Kanze Guest

    On Feb 26, 7:03 pm, Juha Nieminen <> wrote:
    > Richard Herring wrote:
    > > No. According to 5.9/2 [expr.rel], among other restrictions:


    > > "If two pointers p and q of the same type point to different objects
    > > that are not members of the same object or elements of the same array or
    > > to different functions, or if only one of them is null, the results of
    > > p<q, p>q, p<=q, and p>=q are unspecified."


    > I understand that to mean that if you have two pointers,
    > there's no way of knowing if the first one will evaluate as
    > "smaller than" the second one (other than actually testing
    > with "p < q"). In other words, you can't assume that if you
    > eg. allocated two blocks of memory to two pointers, the first
    > pointer will evaluate to be "smaller than" the second one. It
    > can be either way, there's no guarantee.


    I'm not sure that even that is guaranteed, but even if it is, it
    isn't enough to provide an ordering relationship. You also have
    the requirement (in the standard library) that if !(a<b) and
    !(b<a), a and b are equal. I've used implementation (of C---it
    was a long time ago) where a<b returned false for all pointers
    returned by malloc. Regardless of the order of the comparison.

    > However, if you have two pointers p and q, and p evaluates to
    > be "smaller than" q, it will *always* do so. The "p < q" will
    > not give random results, but it will always give true in this
    > case.


    > In other words, if the values of p and q don't change, then
    > the value of "p < q" will never change either.


    Which doesn't help if it's always false, regardless of the
    pointers.

    (It's interesting to note that this is different than in C,
    where the behavior is simply undefined.)

    > This means that pointers can indeed be used in a set/map
    > without any problems. You just can't know in which order they
    > will end up there, that's all.


    It means that the < operator doesn't define a strict ordering
    over pointers, and so it cannot be used when ordering is
    required in the standard.

    --
    James Kanze (GABI Software) email:
    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
     
    James Kanze, Feb 26, 2008
    #13
  14. REH

    Fei Liu Guest

    REH wrote:
    > On Feb 26, 10:44 am, Fei Liu <> wrote:
    >> std::set of pointers are well supported, pointers have value semantic,
    >> comparable.
    >>
    >> The relational operators you refer work fine because pointers can be
    >> compared by value.
    >>
    >> Fei

    >
    > Your logic doesn't hold. Pointers can only be relationally compared
    > if they are from the same struct, array, etc.
    >
    > REH


    It's implied that your 'pointers' are of the same type. Otherwise your
    question is ill formed. I was going to mention this but it's good that
    you understand that you must use same type of pointers in a single set.

    Fei
     
    Fei Liu, Feb 26, 2008
    #14
  15. Fei Liu wrote:
    > REH wrote:
    >> On Feb 26, 10:44 am, Fei Liu <> wrote:
    >>> std::set of pointers are well supported, pointers have value
    >>> semantic, comparable.
    >>>
    >>> The relational operators you refer work fine because pointers can be
    >>> compared by value.
    >>>
    >>> Fei

    >>
    >> Your logic doesn't hold. Pointers can only be relationally compared
    >> if they are from the same struct, array, etc.
    >>
    >> REH

    >
    > It's implied that your 'pointers' are of the same type. Otherwise your
    > question is ill formed. I was going to mention this but it's good that
    > you understand that you must use same type of pointers in a single
    > set.


    Pointers can only be compared using relational operators if the objects
    they point to belong the same [larger] object, for example, an array.
    If they pointers have the same type but aren't part of another, larger,
    object, using relational operators on them is undefined.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Feb 26, 2008
    #15
  16. REH

    REH Guest

    On Feb 26, 4:21 pm, Fei Liu <> wrote:
    > It's implied that your 'pointers' are of the same type. Otherwise your
    > question is ill formed. I was going to mention this but it's good that
    > you understand that you must use same type of pointers in a single set.
    >
    > Fei


    No, it has nothing to do with being the same type. Pointers must
    point to elements or fields of the same OBJECT to be relationally
    comparable.

    REH
     
    REH, Feb 26, 2008
    #16
  17. REH

    James Kanze Guest

    On Feb 26, 10:33 pm, "Victor Bazarov" <> wrote:
    > Fei Liu wrote:
    > > REH wrote:
    > >> On Feb 26, 10:44 am, Fei Liu <> wrote:
    > >>> std::set of pointers are well supported, pointers have value
    > >>> semantic, comparable.


    > >>> The relational operators you refer work fine because
    > >>> pointers can be compared by value.


    > >> Your logic doesn't hold. Pointers can only be relationally
    > >> compared if they are from the same struct, array, etc.


    > > It's implied that your 'pointers' are of the same type.
    > > Otherwise your question is ill formed. I was going to
    > > mention this but it's good that you understand that you must
    > > use same type of pointers in a single set.


    > Pointers can only be compared using relational operators if
    > the objects they point to belong the same [larger] object, for
    > example, an array. If they pointers have the same type but
    > aren't part of another, larger, object, using relational
    > operators on them is undefined.


    And if they're of different types, the compiler will try to find
    a common type, and use that. (I'm not sure of the exact rules,
    because I can't think of a general case where it would be
    useful. But cv qualifiers can definitely be discarded---you can
    compare a char const* with a char* without any problems, as long
    as they point into the same object.)

    --
    James Kanze (GABI Software) email:
    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
     
    James Kanze, Feb 27, 2008
    #17
  18. In message <47c4504d$0$23834$>, Juha Nieminen
    <> writes
    >Richard Herring wrote:
    >> No. According to 5.9/2 [expr.rel], among other restrictions:
    >>
    >> "If two pointers p and q of the same type point to different objects
    >> that are not members of the same object or elements of the same array or
    >> to different functions, or if only one of them is null, the results of
    >> p<q, p>q, p<=q, and p>=q are unspecified."

    >
    > I understand that to mean that if you have two pointers, there's no
    >way of knowing if the first one will evaluate as "smaller than" the
    >second one (other than actually testing with "p < q").


    I understand that to mean what it says.

    >In other words,
    >you can't assume that if you eg. allocated two blocks of memory to two
    >pointers, the first pointer will evaluate to be "smaller than" the
    >second one. It can be either way, there's no guarantee.
    >
    > However, if you have two pointers p and q, and p evaluates to be
    >"smaller than" q, it will *always* do so. The "p < q" will not give
    >random results, but it will always give true in this case.


    Where in the Standard is that guaranteed? "Unspecified" means just
    that. It doesn't say "unspecified but deterministic".
    >
    > In other words, if the values of p and q don't change, then the value
    >of "p < q" will never change either. This means that pointers can indeed
    >be used in a set/map without any problems.


    No. Use in a set also requires that p < q && q < r implies p < r, which
    is certainly not guaranteed if the individual comparisons are
    unspecified.

    >You just can't know in which
    >order they will end up there, that's all.


    It's much worse than that. If the comparison isn't a strict weak
    ordering, the set operations will have undefined behaviour.
    >
    > The paragraph you quoted specifically mentions that two pointers
    >pointing to elements in the same array have a well defined order. That's
    >because arrays are defined as being one contiguous blocks of memory, and
    >a later element in the array is guaranteed have a larger memory location
    >than an earlier element. For this reason &array[6] will always be
    >smaller than &array[10].


    I don't think anyone is arguing with that.

    >The same goes for struct/class member variables.


    Not if they are separated in the declaration by an access specifier.

    --
    Richard Herring
     
    Richard Herring, Feb 27, 2008
    #18
    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. Phil
    Replies:
    1
    Views:
    673
    llewelly
    Sep 16, 2003
  2. muser
    Replies:
    3
    Views:
    785
    Ron Natalie
    Sep 18, 2003
  3. A
    Replies:
    3
    Views:
    481
    Alan Kelon
    Oct 29, 2003
  4. Xamalek
    Replies:
    7
    Views:
    710
  5. cerr

    pointers, pointers, pointers...

    cerr, Apr 7, 2011, in forum: C Programming
    Replies:
    12
    Views:
    739
Loading...

Share This Page