4

（与我之前的问题有关）

在 QT 中，QMap文档说：

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

但是，在 中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 （这是 的 QT 版本uintptr_t，即能够存储指针的无符号整数）并比较结果。

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

你认为这种qMapLessThanKey()on 指针的实现好吗？

当然，整数类型有一个总顺序。但我认为这不足以得出此操作定义了指针的总顺序的结论。

我认为只有在没有指定 AFAIKp1 == p2的情况下，它才是正确的。quintptr(p1) == quintptr(p2)

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

你怎么看？

4

2 回答 2

2

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

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

于 2015-06-04T21:22:14.757 回答
1

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

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

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

从实用的角度来看，大多数主流编译器都会按位将指针转换为整数，并且你会有一个全序。

理论问题：

但这不能保证。它可能不适用于过去的平台（x86 实模式和保护模式）、外来平台（嵌入式系统？），以及——谁知道——在某些未来的平台上（？）。

以 8086 的分段内存为例：实际地址由段（例如数据段的 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 个低位上。事实上，这种方式将显着促进/加速将指针值加载到 cpu 寄存器中。

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

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

可以想象使用指针算法。对同一数组中的元素的指针算法有严格的限制：

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

并且下标是有序的。

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

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

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

所以指针算术也不能解决任意指针的问题。再次回到分段内存模型，有助于理解：数组最多可以有 65535 个字节以完全适合一个段。但是不同的数组可以使用不同的段，因此指针算术对于总顺序也不可靠。

结论

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

对于那些知道底层机器的寻址结构的人来说，这并不奇怪。

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

于 2015-06-03T21:51:31.710 回答