C 是否具有 C++ 中的 std::less 等价物？

Question

我最近在回答一个关于在 C 中执行 p < q 的未定义行为的问题，当时 p 和 q 是指向不同 objects/arrays 的指针。这让我开始思考：在这种情况下，C++ 具有与 < 相同（未定义）的行为，但也提供了标准库模板 std::less，保证 return 与 < 当指针可以比较时，return 一些一致的顺序不能时。

C 是否提供具有类似功能的东西，可以安全地比较任意指针（指向同一类型）？我尝试查看 C11 标准但没有找到任何东西，但我在 C 方面的经验比在 C++ 中少了几个数量级，所以我很容易错过一些东西。

Answer 1

我并且我确实找到了适用于重叠对象的解决方案，并且在大多数其他情况下假设编译器执行 "usual" 事情。

您可以先实施 How to implement memmove in standard C without an intermediate copy? 中的建议，如果这不起作用，则转换为 uintptr（uintptr_t 或 unsigned long long 的包装类型，具体取决于关于 uintptr_t 是否可用）并获得最可能准确的结果（尽管它可能并不重要）：

#include <stdint.h>
#ifndef UINTPTR_MAX
typedef unsigned long long uintptr;
#else
typedef uintptr_t uintptr;
#endif

int pcmp(const void *p1, const void *p2, size_t len)
{
    const unsigned char *s1 = p1;
    const unsigned char *s2 = p2;
    size_t l;

    /* Check for overlap */
    for( l = 0; l < len; l++ )
    {
        if( s1 + l == s2 || s1 + l == s2 + len - 1 )
        {
            /* The two objects overlap, so we're allowed to
               use comparison operators. */
            if(s1 > s2)
                return 1;
            else if (s1 < s2)
                return -1;
            else
                return 0;
        }
    }

    /* No overlap so the result probably won't really matter.
       Cast the result to `uintptr` and hope the compiler
       does the "usual" thing */
    if((uintptr)s1 > (uintptr)s2)
        return 1;
    else if ((uintptr)s1 < (uintptr)s2)
        return -1;
    else
        return 0;
}

Answer 2

Does C offer something with similar functionality which would allow safely comparing arbitrary pointers.

没有

首先让我们只考虑对象指针。 函数指针 带来了一系列其他问题。

2 个指针 p1, p2 可以有不同的编码并指向相同的地址，所以 p1 == p2 即使 memcmp(&p1, &p2, sizeof p1) 不是 0。这种架构很少见。

然而，将这些指针转换为 uintptr_t 不需要导致 (uintptr_t)p1 != (uinptr_t)p2 的相同整数结果。

(uintptr_t)p1 < (uinptr_t)p2 本身是很好的合法代码，可能无法提供所希望的功能。

如果代码确实需要比较不相关的指针，形成一个辅助函数 less(const void *p1, const void *p2) 并在那里执行特定于平台的代码。

也许：

// return -1,0,1 for <,==,> 
int ptrcmp(const void *c1, const void *c1) {
  // Equivalence test works on all platforms
  if (c1 == c2) {
    return 0;
  }
  // At this point, we know pointers are not equivalent.
  #ifdef UINTPTR_MAX
    uintptr_t u1 = (uintptr_t)c1;
    uintptr_t u2 = (uintptr_t)c2;
    // Below code "works" in that the computation is legal,
    //   but does it function as desired?
    // Likely, but strange systems lurk out in the wild. 
    // Check implementation before using
    #if tbd
      return (u1 > u2) - (u1 < u2);
    #else
      #error TBD code
    #endif
  #else
    #error TBD code
  #endif 
}

Answer 3

在具有平面内存模型（基本上所有内容）的实现中，强制转换为 uintptr_t 即可。

（但请参阅讨论是否应将指针视为带符号的，包括在对象外部形成指针的问题，即 C 中的 UB。）

但是具有非平坦内存模型的系统确实存在，并且考虑它们可以帮助解释当前情况，例如 C++ < 与 std::less 具有不同的规范.

< 关于指向单独对象的指针在 C 中是 UB（或至少在某些 C++ 修订版中未指定）的部分要点是允许怪异的机器，包括非平面内存模型。

一个著名的例子是 x86-16 实模式，其中指针是 segment:offset，通过 (segment << 4) + offset 形成一个 20 位的线性地址。同一个线性地址可以用多个不同的seg:off组合来表示。

C++ std::less 奇怪的 ISA 上的指针可能需要很昂贵 ，例如"normalize" x86-16 上的 segment:offset 偏移量 <= 15。但是，没有 或 table 方法来实现它。 规范化 uintptr_t（或指针对象的对象表示）所需的操作是特定于实现的。

但即使在 C++ std::less 必须非常昂贵的系统上，< 也不一定如此。例如，假设一个 "large" 内存模型，其中一个对象适合一个段， < 可以只比较偏移部分，甚至不关心段部分。（同一对象内的指针将具有相同的段，否则它是 C 中的 UB。C++17 仅更改为 "unspecified"，这可能仍然允许跳过规范化并仅比较偏移量。）这是假设所有指针都指向对象的任何部分始终使用相同的 seg 值，从不规范化。这是您期望 ABI 对 "large" 而非 "huge" 内存模型的要求。（参见）。

（例如，这样的内存模型可能具有 64kiB 的最大对象大小，但更大的最大总地址 space 可为许多此类最大对象提供空间。ISO C 允许实现具有低于最大值（无符号）size_t 的对象大小限制可以表示 SIZE_MAX。例如，即使在平面内存模型系统上，GNU C 也将最大对象大小限制为 PTRDIFF_MAX，因此大小计算可以忽略有符号溢出。）参见 this answer 和评论中的讨论。

如果你想允许对象大于一个段，你需要一个 "huge" 内存模型，它必须担心在 p++ 循环数组时溢出指针的偏移部分，或者在进行索引/指针运算时。这导致到处都是较慢的代码，但可能意味着 p < q 会碰巧适用于指向不同对象的指针，因为针对 "huge" 内存模型的实现通常会选择始终保持所有指针标准化.请参阅 What are near, far and huge pointers? - 一些用于 x86 实模式的真实 C 编译器确实有一个选项可以为 "huge" 模型编译，其中所有指针默认为 "huge" 除非另有声明。

x86 实模式分段不是唯一可能的非平面内存模型，它只是一个有用的具体示例来说明 C/C 如何处理它++实施。在现实生活中，实现使用 far 与 near 指针的概念扩展了 ISO C，允许程序员选择何时可以只存储/传递 16 位偏移部分，相对于一些常见的数据段。

但是纯 ISO C 实现必须在小内存模型（除具有 16 位指针的相同 64kiB 中的代码之外的所有内容）或所有指针均为 32 位的大内存模型之间进行选择。一些循环可以通过仅增加偏移部分来优化，但指针对象无法优化为更小。

如果您知道任何给定实现的魔术操作是什么，您可以用纯 C 实现它。问题是不同的系统使用不同的寻址并且细节没有被任何 portable 宏参数化。

也可能不是：它可能涉及从特殊段 table 或其他内容中查找某些内容，例如像 x86 保护模式而不是实模式，其中地址的段部分是索引，而不是要左移的值。您可以在保护模式下设置部分重叠的段，地址的段选择器部分甚至不一定按照与相应段基地址相同的顺序排序。如果 GDT and/or LDT 未映射到进程中的可读页面，则在 x86 保护模式下从 seg:off 指针获取线性地址可能涉及系统调用。

（当然，x86 的主流操作系统使用平面内存模型，因此段基数始终为 0（使用 fs 或 gs 段的线程本地存储除外），并且只有 32 -bit 或 64 位 "offset" 部分用作指针。）

您可以为各种特定平台手动添加代码，例如默认情况下假设平坦，或者 #ifdef 一些东西来检测 x86 实模式并将 uintptr_t 分成 16 位的两半用于 seg -= off>>4; off &= 0xf; 然后将这些部分组合回一个 32 位数字。

Answer 4

C 标准明确允许实现在操作调用“未定义行为”时“以环境的文档化方式”运行。在编写标准时，每个人都清楚，在处理任意指针之间的关系运算符时，在具有平面内存模型的平台上进行低级编程的实现应该准确地做到这一点。同样显而易见的是，针对其指针比较的自然方式永远不会有副作用的平台的实现应该以没有副作用的方式在任意指针之间执行比较。

在三种一般情况下，程序员可能会在指针之间执行关系运算符：

永远不会比较指向无关对象的指针。
代码可能会在结果重要的情况下比较对象内的指针，或者在不相关的对象之间比较指针在结果无关紧要的情况下。一个简单的例子就是可以按升序或降序对可能重叠的数组段进行操作的操作。在对象重叠的情况下，升序或降序的选择很重要，但在作用于不相关对象中的数组段时，任一顺序都同样有效。
代码依赖于产生与指针相等性一致的传递排序的比较。

第三种用法很少发生在特定于平台的代码之外，这些代码要么知道关系运算符可以简单地工作，要么知道特定于平台的替代方案。第二种用法可能出现在代码中，这些代码应该主要是可移植的，但是几乎所有的实现都可以像第一种一样廉价地支持第二种用法，并且没有理由让他们不这样做。唯一应该有理由关心是否定义了第二种用法的人是为此类比较昂贵的平台编写编译器的人，或者是那些试图确保他们的程序与此类平台兼容的人。这些人比委员会更能判断坚持“无副作用”保证的利弊，因此委员会悬而未决。

可以肯定的是，编译器没有理由不有效地处理构造这一事实并不能保证“无偿聪明的编译器”不会以标准为借口去做其他事情，但是C 标准没有定义“less”运算符的原因是委员会期望“<”适用于几乎所有平台上的几乎所有程序。

C 是否具有 C++ 中的 std::less 等价物？

Does C have an equivalent of std::less from C++?

c

pointers

undefined-behavior

memory-model

memory-segmentation