我可以对指针数组进行排序以删除重复项吗？

Question

假设我定义了一个结构并创建了它的几个实例。我有一个指向这些实例的指针数组，但有些指针指向我的结构的相同实例。我想删除数组中的重复项，所以我通过 qsort() 函数对其进行排序。这是我的比较函数:

int cmp(const void *a, const void *b)
{
  struct foo **s1 = (struct foo**)a;
  struct foo **s2 = (struct foo**)b;
  return *s1 - *s2;
}

问题是，我真的可以使用这样的比较来排序吗？我知道在这种情况下减去指针是未定义的，但我只关心指针的整数值，因为我只是希望指向同一 foo 实例的指针彼此相邻。

也许我应该使用这样的函数:

int cmp(const void *a, const void *b)
{
  struct foo **s1 = (struct foo**)a;
  struct foo **s2 = (struct foo**)b;
  if (*s1 > *s2)
    return 1;
  else if (*s1 == *s2)
    return 0;
  else 
    return -1;
}

使用起来有什么区别吗？

Answer 1

如果您有 intptr_t(它是一个整数类型)，那么您可以将您的 void* 指针转换为它，然后您可以比较任意值。 intptr_t 不是必需的类型，但在实践中很常见。

从另一个中减去一个 intptr_t 可能仍然会溢出，因此它不是一个严格可移植的解决方案。但是对比一下就好了。如果您使用 uintptr_t 来避免溢出，则差异永远不会为负。这是使用 a - b 实现 qsort 风格比较函数的普遍问题。

减去或比较不指向同一对象的指针是未定义的行为。因此，问题中提出的两种解决方案均无效:

§6.5.6 第 9 段(加法运算符):

When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object

§6.5.8 第 5 段提供了可能有效比较的列表，这比对减法的限制更宽松一些，因为您可以比较指向同一 struct 或 union，前提是成员本身属于同一类型。但是不相关的对象不属于此列表中的任何一个。它以一句话结束:“在所有其他情况下，行为未定义。”

如果您想要一个不依赖于 intptr_t 的真正可移植的解决方案，那么您可以 memcmp 指针。但是，实际上，我认为这只是理论上的兴趣。