(related to my previous question)
In QT, the QMap
documentation says:
The key type of a QMap must provide
operator<()
specifying a total order.
However, in qmap.h
, they seem to use something similar to std::less
to compare pointers:
/*
QMap uses qMapLessThanKey() to compare keys. The default
implementation uses operator<(). For pointer types,
qMapLessThanKey() casts the pointers to integers before it
compares them, because operator<() is undefined on pointers
that come from different memory blocks. (In practice, this
is only a problem when running a program such as
BoundsChecker.)
*/
template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
{
return key1 < key2;
}
template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
{
Q_STATIC_ASSERT(sizeof(quintptr) == sizeof(const Ptr *));
return quintptr(key1) < quintptr(key2);
}
They just cast the pointers to quintptr
s (which is the QT-version of uintptr_t
, that is, an unsigned int that is capable of storing a pointer) and compare the results.
The following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to a pointer to void, and the result will compare equal to the original pointer:
uintptr_t
Do you think this implementation of qMapLessThanKey()
on pointers is ok?
Of course, there is a total order on integral types. But I think this is not sufficient to conclude that this operation defines a total order on pointers.
I think that it is true only if p1 == p2
implies quintptr(p1) == quintptr(p2)
, which, AFAIK, is not specified.
As a counterexample of this condition, imagine a target using 40 bits for pointers; it could convert pointers to quintptr
, setting the 40 lowest bits to the pointer address and leaving the 24 highest bits unchanged (random). This is sufficient to respect the convertibility between quintptr
and pointers, but this does not define a total order for pointers.
What do you think?
I think that you can't assume that there is a total order on pointers. The guarantees given by the standard for pointer to int conversions are rather limited:
From a practical point of view, most of the mainstream compilers will convert a pointer to an integer in a bitwise manner, and you'll have a total order.
The theoretical problem:
But this is not guaranteed. It might not work on past platforms (x86 real and protected mode), on exotic platform (embedded systems ?) , and -who knows- on some future platforms (?).
Take the example of segmented memory of the 8086: The real address is given by the combination of a segment (e.g. DS register for data segment, an SS for stack segment,...) and an offest:
Now imagine that the compiler would convert the pointer to int, by simply doing the address math and put 20 bits in the integer: your safe and have a total order.
But another equally valid approach would be to store the segment on 16 upper bits and the offset on the 16 lower bits. In fact, this way would significantly facilitate/accelerate the load of pointer values into cpu registers.
This approach is compliant with standard c++ requirements, but each single address could be represented by 16 different pointers: your total order is lost !!
**Are there alternatives for the order ? **
One could imagine using pointer arithmetics. There are strong constraints on pointer arithmetics for elements in a same array:
And subscripts are ordered.
Array can be of maximum
size_t
elements. So, naively, ifsizeof(pointer) <= sizof(size_t)
one could assume that taking an arbitrary reference pointer and doing some pointer arithmetic should lead to a total order.Unfortunately, here also, the standard is very prudent:
So pointer arithmetic won't do the trick for arbitrary pointers either. Again, back to the segmented memory models, helps to understand: arrays could have maximum 65535 bytes to fit completely in one segment. But different arrays could use different segments so that pointer arithmetic wouldn't be reliable for a total order either.
Conclusion
There's a subtle note in the standard on the mapping between pointer and interal value:
This means that must be be possible to determine a total order. But keep in mind that it'll be non portable.