set of pointers

[REH]

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

 

[Fei Liu]

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

 

[Lance Diduck]

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

 

[red floyd]

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.

 

[Richard Herring]

In message

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.

 

[Andrew Koenig]

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.

 

[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

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]

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]

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

 

[Juha Nieminen]

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.

 

[Kai-Uwe Bux]

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

 

[James Kanze]

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]

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.

 

[Fei Liu]

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

 

[Victor Bazarov]

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

 

[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

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

 

[James Kanze]

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

 

[Richard Herring]

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.