c++ - Does casting pointers to integers define a total order on pointers? -

(related my previous question)

in qt, qmap documentation says:

the key type of qmap must provide operator<() specifying total order.

however, in qmap.h, seem use similar std::less compare pointers:

/*     qmap uses qmaplessthankey() compare keys. default     implementation uses operator<(). pointer types,     qmaplessthankey() casts pointers integers before     compares them, because operator<() undefined on pointers     come different memory blocks. (in practice,     problem when running program such     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 cast pointers quintptrs (which qt-version of uintptr_t, is, unsigned int capable of storing pointer) , compare results.

the following type designates unsigned integer type property valid pointer void can converted type, converted pointer void, , result compare equal original pointer: uintptr_t

do think implementation of qmaplessthankey() on pointers ok?

of course, there total order on integral types. think not sufficient conclude operation defines total order on pointers.

i think true if p1 == p2 implies quintptr(p1) == quintptr(p2), which, afaik, not specified.

as counterexample of condition, imagine target using 40 bits pointers; convert pointers quintptr, setting 40 lowest bits pointer address , leaving 24 highest bits unchanged (random). sufficient respect convertibility between quintptr , pointers, not define total order pointers.

what think?

i think can't assume there total order on pointers. guarantees given standard pointer int conversions rather limited:

5.2.10/4: pointer can explicitly converted integral type large enough hold it. mapping function implementation-defined.

5.2.10/5: value of integral type or enumeration type can explicitly converted pointer. pointer converted integer of sufficient size (...) , same pointer type have original value; mappings between pointers , integers otherwise implementation-defined.

from practical point of view, of mainstream compilers convert pointer integer in bitwise manner, , you'll have total order.

the theoretical problem:

but not guaranteed. might not work on past platforms (x86 real , protected mode), on exotic platform (embedded systems ?) , , -who knows- on future platforms (?).

take example of segmented memory of 8086: real address given combination of segment (e.g. ds register data segment, ss stack segment,...) , offest:

segment:   xxxx yyyy yyyy yyyy 0000    16 bits shifted 4 bits offset:    0000 zzzz zzzz zzzz zzzz    16 bits not sifted            ------------------------ address:   aaaa aaaa aaaa aaaa aaaa    20 bits address                       

now imagine compiler convert pointer int, doing address math , put 20 bits in integer: safe , have total order.

but equally valid approach store segment on 16 upper bits , offset on 16 lower bits. in fact, way facilitate/accelerate load of pointer values cpu registers.

this approach compliant standard c++ requirements, each single address represented 16 different pointers: total order lost !!

**are there alternatives order ? **

one imagine using pointer arithmetics. there strong constraints on pointer arithmetics elements in same array:

5.7/6: when 2 pointers elements of same array object subtracted, result difference of subscripts of 2 array elements.

and subscripts ordered.

array can of maximum size_t elements. so, naively, if sizeof(pointer) <= sizof(size_t) 1 assume taking arbitrary reference pointer , doing pointer arithmetic should lead total order.

unfortunately, here also, standard prudent:

5.7.7: addition or subtraction, if expressions p or q have type “pointer cv t”, t different cv-unqualified array element type, behavior undefined.

so pointer arithmetic won't trick arbitrary pointers either. again, segmented memory models, helps understand: arrays have maximum 65535 bytes fit in 1 segment. different arrays use different segments pointer arithmetic wouldn't reliable total order either.

conclusion

there's subtle note in standard on mapping between pointer , interal value:

it intended unsurprising know addressing structure of underlying machine.

this means must be possible determine total order. keep in mind it'll non portable.