Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > set of pointers

Reply
Thread Tools

set of pointers

 
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      02-26-2008
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
 
Reply With Quote
 
 
 
 
James Kanze
Guest
Posts: n/a
 
      02-26-2008
On Feb 26, 4:44 pm, Fei Liu <(E-Mail Removed)> 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:(E-Mail Removed)
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
 
Reply With Quote
 
 
 
 
James Kanze
Guest
Posts: n/a
 
      02-26-2008
On Feb 26, 7:03 pm, Juha Nieminen <(E-Mail Removed)> 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:(E-Mail Removed)
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
 
Reply With Quote
 
Fei Liu
Guest
Posts: n/a
 
      02-26-2008
REH wrote:
> On Feb 26, 10:44 am, Fei Liu <(E-Mail Removed)> 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
 
Reply With Quote
 
Victor Bazarov
Guest
Posts: n/a
 
      02-26-2008
Fei Liu wrote:
> REH wrote:
>> On Feb 26, 10:44 am, Fei Liu <(E-Mail Removed)> 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


 
Reply With Quote
 
REH
Guest
Posts: n/a
 
      02-26-2008
On Feb 26, 4:21 pm, Fei Liu <(E-Mail Removed)> 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
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      02-27-2008
On Feb 26, 10:33 pm, "Victor Bazarov" <(E-Mail Removed)> wrote:
> Fei Liu wrote:
> > REH wrote:
> >> On Feb 26, 10:44 am, Fei Liu <(E-Mail Removed)> 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:(E-Mail Removed)
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
 
Reply With Quote
 
Richard Herring
Guest
Posts: n/a
 
      02-27-2008
In message <47c4504d$0$23834$(E-Mail Removed)>, Juha Nieminen
<(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
pointers, pointers, pointers... cerr C Programming 12 04-07-2011 11:17 PM
Does deleting a container of pointers also delete the (contained) pointers? Xamalek C++ 7 11-04-2003 04:17 PM
c++: pointers to pointers A C++ 3 10-29-2003 01:15 PM
pointers to pointers // exception handling error muser C++ 3 09-18-2003 06:19 PM
Template specialization of pointers with function pointers Phil C++ 1 09-16-2003 02:17 AM



Advertisments