指针如何完全排序？ [英] How can pointers be totally ordered?

问题描述

C ++中的指针通常只能比较相等。相比之下，小于比较只允许指向同一完整对象（例如数组元素）的子对象的两个指针。

所以给定 T * p，* q ，通常评估 p < c

标准库包含函子类模板 std :: less< T> 等，它包装内置的操作符< 。但是，标准有这样的说法指针类型（20.8.5 / 8）：

对于模板 ，少， greater_equal 和 less_equal ，任何指针类型的专业化产生总次序，即使内置运算符< ，> ， <= ，> = 不要。

< blockquote>

如何实现呢？

我看了一下GCC 4.7.2和Clang 3.2，它们不包含任何专业化用于指针类型。它们似乎依赖于< 在所有支持的平台上无条件有效。

解决方案

指针可以完全排序吗？不在便携式，标准C ++。这是
为什么标准需要实现来解决问题，而不是
。对于指针的任何给定的表示，应当可能的是
定义任意的总排序，但是如何做将取决于
指针的表示。

对于具有平坦地址空间和字节寻址的机器，只需
将指针看作是类似大小的整数或无符号
整数就足够了;这是大多数编译器将处理
比较在一个对象中，所以在这样的机器，没有
需要的库专门化 std :: less et al。

对于字处理机器（至少有一个仍在
生产中） ），在编译器本机比较可以工作之前，可能需要将指针转换为 void *
。

对于具有分段架构的机器，可能需要更多的工作。
在这样的机器上，典型地需要一个数组完全在一个
段，只是比较段中的偏移;这意味着如果
a 和 b 是两个任意指针，您可能会得到！（a< b）&&
！（b< a），但不是 a == b 。在这种情况下，编译器必须为指针提供
特殊化的 std :: less<> 等，这可能是
提取段

编辑：

p>在其他值得一提的地方，也许：C ++
标准中的保证只适用于标准C ++，或者在这种情况下，指针从标准C ++获得
。在大多数现代系统上，很容易将 mmap
同一个文件分配到两个不同的地址范围，并且有两个指针 p
和 q ，它们比较不等号，但指向同一个对象。

Pointers in C++ may in general only be compared for equality. By contrast, less-than comparison is only allowed for two pointers that point to subobjects of the same complete object (e.g. array elements).

So given T * p, * q, it is illegal in general to evaluate p < q.

The standard library contains functor class templates std::less<T> etc. which wrap the built-in operator <. However, the standard has this to say about pointer types (20.8.5/8):

For templates greater, less, greater_equal, and less_equal, the specializations for any pointer type yield a total order, even if the built-in operators <, >, <=, >= do not.

How can this be realised? Is it even possible to implement this?

I took a look at GCC 4.7.2 and Clang 3.2, which don't contain any specialization for pointer types at all. They seem to depend on < being valid unconditionally on all their supported platforms.

解决方案

Can pointers be totally ordered? Not in portable, standard C++. That's why the standard requires the implementation to solve the problem, not you. For any given representation of a pointer, it should be possible to define an arbitrary total ordering, but how you do it will depend on the the representation of a pointer.

For machines with a flat address space and byte addressing, just treating the pointer as if it were a similarly sized integer or unsigned integer is usually enough; this is how most compilers will handle comparison within an object as well, so on such machines, there's no need for the library to specialize std::less et al. The "unspecified" behavior just happens to do the right thing.

For word addressed machines (and there is at least one still in production), it may be necessary to convert the pointers to void* before the compiler native comparison will work.

For machines with segmented architectures, more work may be necessary. It's typical on such machines to require an array to be entirely in one segment, and just compare the offset in the segment; this means that if a and b are two arbitrary pointers, you may end up with !(a < b) && !(b < a) but not a == b. In this case, the compiler must provide specializations of std::less<> et al for pointers, which (probably) extract the segment and the offset from the pointer, and do some sort of manipulation of them.

EDIT:

On other thing worth mentionning, perhaps: the guarantees in the C++ standard only apply to standard C++, or in this case, pointers obtained from standard C++. On most modern systems, it's rather easy to mmap the same file to two different address ranges, and have two pointers p and q which compare unequal, but which point to the same object.

这篇关于指针如何完全排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！