将指针转换为整数是否定义了指针的总顺序？

Question

（与有关）

在 QT 中，QMap documentation 表示：

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

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

/*
    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 版本，即一个能够 storing a pointer 的无符号整数）并比较结果。

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() 在指针上的这种实现可以吗？

当然，整数类型是有总序的。但我认为这还不足以得出这个操作定义了指针的全序。

我认为仅当 p1 == p2 暗示 quintptr(p1) == quintptr(p2) 时才为真，据我所知，未指定。

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

你怎么看？

Answer 1

我认为你不能假设指针有一个总顺序。指针到 int 转换的标准提供的保证相当有限：

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

从实用的角度来看，主流的编译器大多会将指针按位转换为整数，你就有了总序。

理论问题：

但这并不能保证。它可能不适用于过去的平台（x86 real and protected mode）、异国情调的平台（嵌入式系统？），以及 - 谁知道 - 在某些未来的平台上（？）。

以8086的segmented memory为例：真实地址由一个段（例如数据段的DS寄存器，堆栈段的SS，...）和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 位放入整数中：您的安全和总订单。

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

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

**订单有替代品吗？ **

可以想象使用指针算法。同一数组中元素的指针算法有很强的约束：

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) 可以假设采用任意引用指针并进行一些指针算术应该导致总顺序。

不幸的是，这里也是，标准非常谨慎：

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 字节以完全适合一个段。但是不同的数组可以使用不同的段，因此指针算法对于总顺序也不可靠。

结论

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

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

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

Answer 2

标准保证将指针转换为 uintptr_t 将产生某个无符号类型的值，如果转换为原始指针类型，将产生原始指针。它还要求任何指针都可以分解为 unsigned char 值序列，并且使用这样的 unsigned char 值序列构造指针将产生原始指针。然而，这两种保证都不会禁止实现在指针类型中包含填充位，也不会保证要求填充位以任何一致的方式运行。

如果代码避免存储指针，而是将 uintptr_t 从 malloc 返回的每个指针转换为 uintptr_t，然后根据需要将这些值转换回指针，则生成的 uintptr_t 值将形成排名。排名可能与对象的创建顺序没有任何关系，也与它们在内存中的排列没有任何关系，但它会是一个排名。但是，如果任何指针多次转换为 uintptr_t，则结果值可能完全独立排名。

将指针转换为整数是否定义了指针的总顺序？

Does casting pointers to integers define a total order on pointers?

c++

qt

pointers

partial-ordering

undefined-behavior

理论问题：

结论