将指针转换为整数是否定义了指针的总顺序? [英] Does casting pointers to integers define a total order on pointers?

问题描述

(与我之前的问题有关)

在 QT 中，QMap 文档 说:

In QT, the QMap documentation says:

QMap 的键类型必须提供 operator<() 指定总顺序.

The key type of a QMap must provide operator<() specifying a total order.

然而，在qmap.h中，他们似乎使用了类似于std::less的东西来比较指针:

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);
}

他们只是将指针投射到quintptrs(这是uintptr_t 的QT 版本，即一个能够存储指针) 并比较结果.

They just cast the pointers to quintptrs (which is the QT-version of uintptr_t, that is, an unsigned int that is capable of storing a pointer) and compare the results.

以下类型指定了一个无符号整数类型，其特性是任何指向 void 的有效指针都可以转换为该类型，然后转换回指向 void 的指针，结果将与原始指针进行比较: uintptr_t

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

你认为 qMapLessThanKey() 在指针上的这个实现好吗?

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.

我认为只有当 p1 == p2 暗示 quintptr(p1) == quintptr(p2) 时它才是真的，AFAIK 没有指定.

I think that it is true only if p1 == p2 implies quintptr(p1) == quintptr(p2), which, AFAIK, is not specified.

作为这种情况的反例，想象一个目标使用 40 位的指针；它可以将指针转换为 quintptr，将最低 40 位设置为指针地址，而保持最高 24 位不变(随机).这足以尊重 quintptr 和指针之间的可转换性，但这并没有定义指针的总顺序.

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.

你怎么看?

推荐答案

我认为你不能假设指针有一个完整的顺序.标准为 int 转换的指针提供的保证相当有限:

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:

5.2.10/4: 指针可以显式转换为任何足够大的整数类型以容纳它.映射函数是实现定义.

5.2.10/4: A pointer can be explicitly converted to any integral type large enough to hold it. The mapping function is implementation-defined.

5.2.10/5: 整数类型或枚举类型的值可以显式转换为指针.转换为整数的指针足够大小 (...) 并返回到相同的指针类型将有它的原始价值；指针和整数之间的映射是否则由实现定义.

5.2.10/5: A value of integral type or enumeration type can be explicitly converted to a pointer. A pointer converted to an integer of sufficient size (...) and back to the same pointer type will have its original value; mappings between pointers and integers are otherwise implementation-defined.

从实际的角度来看，大​​多数主流编译器都会以按位方式将指针转换为整数，并且您将拥有一个全序.

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.

但这不能保证.它可能不适用于过去的平台(x86 真实和保护模式)、异国平台(嵌入式系统)?) ，以及 - 谁知道 - 在一些未来的平台上(?).

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

以8086的分段内存为例:真实地址由组合给出段的(例如数据段的 DS 寄存器，堆栈段的 SS，...)和一个偏移:

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:

Segment:   XXXX YYYY YYYY YYYY 0000    16 bits shifted by 4 bits
Offset:    0000 ZZZZ ZZZZ ZZZZ ZZZZ    16 bits not sifted
           ------------------------
Address:   AAAA AAAA AAAA AAAA AAAA    20 bits address                      

现在想象一下编译器将指针转换为 int，只需进行地址数学运算并将 20 位放入整数:您的保险箱并有一个总顺序.

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.

但另一种同样有效的方法是将段存储在高 16 位，并将偏移量存储在低 16 位.事实上，这种方式将显着促进/加速将指针值加载到 cpu 寄存器中.

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.

这种方法符合标准的 c++ 要求，但每个地址都可以由 16 个不同的指针表示:您的总订单丢失了！！

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:

5.7/6:当两个指向同一个数组对象元素的指针相减时，结果为两者下标之差数组元素.

5.7/6: When two pointers to elements of the same array object are subtracted, the result is the difference of the subscripts of the two array elements.

并且下标是有序的.

数组可以包含最大 size_t 个元素.因此，天真地，如果 sizeof(pointer) <= sizof(size_t) 可以假设采用任意引用指针并进行一些指针算术应该导致全序.

Array can be of maximum size_t elements. So, naively, if sizeof(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:

5.7.7:对于加法或减法，如果表达式 P 或 Q 的类型为指向 cv T 的指针"，其中 T 不同于cv-unqualified 数组元素类型，行为未定义.

5.7.7: For addition or subtraction, if the expressions P or Q have type "pointer to cv T", where T is different from the cv-unqualified array element type, the behavior is undefined.

所以指针算术也不会对任意指针起作用.再次回到分段内存模型，有助于理解:数组最多可以有 65535 个字节以完全适合一个段.但是不同的数组可以使用不同的段，因此指针算法对于全序也不可靠.

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.

标准中有一个关于指针和内部值之间映射的微妙注释:

There's a subtle note in the standard on the mapping between pointer and interal value:

对于知道地址的人来说，这并不奇怪底层机器的结构.

It is intended to be unsurprising to those who know the addressing structure of the underlying machine.

这意味着必须可以确定总订单.但请记住，它是不可移植的.

This means that must be be possible to determine a total order. But keep in mind that it'll be non portable.

这篇关于将指针转换为整数是否定义了指针的总顺序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！