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

On Feb 26, 10:31am, REH <spamj...@stny.rr.com> 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

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.

In message
<642614c3-c77d-4b10-9293-ce095dd66ec5@28g2000hsw.googlegroups.com>,
Lance Diduck <lancediduck@nyc.rr.com> writes
>On Feb 26, 10:31am, REH <spamj...@stny.rr.com> 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

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

On Feb 26, 10:45 am, Lance Diduck <lancedid...@nyc.rr.com> 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

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

On Feb 26, 10:44 am, Fei Liu <fei....@gmail.com> 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

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

On Feb 26, 4:44 pm, Fei Liu <fei....@gmail.com> 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:james.kanze@gmail.com
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

On Feb 26, 7:03 pm, Juha Nieminen <nos...@thanks.invalid> 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 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:james.kanze@gmail.com
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

REH wrote:
> On Feb 26, 10:44 am, Fei Liu <fei....@gmail.com> 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 wrote:
> REH wrote:
>> On Feb 26, 10:44 am, Fei Liu <fei....@gmail.com> 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

On Feb 26, 4:21 pm, Fei Liu <fei....@gmail.com> 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

On Feb 26, 10:33 pm, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:
> Fei Liu wrote:
> > REH wrote:
> >> On Feb 26, 10:44 am, Fei Liu <fei....@gmail.com> 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:james.kanze@gmail.com
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

In message <47c4504d$0$23834$4f793bc4@news.tdc.fi>, Juha Nieminen
<nospam@thanks.invalid> 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