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

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 或 [= 的两个成员的指针17=]，前提是成员本身属于同一类型。但是不相关的对象不属于此列表中的任何一个。它以句子结束："In all other cases, the behavior is undefined."

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

Answer 2

如果要删除重复项，则可以使用嵌套的 for 循环遍历每个指针，如下所示：

int duplicates=0;
for (int i=0;i<count;++i;)
    for (int j=i+1;j<count;++j)
        if (data [i]==data [j])
            ++duplicates;

然后为count-duplicates指针分配足够的内存，然后循环遍历原始数据集，只复制你还没有复制的数据。它效率低下，但它会起作用。

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

Can I sort an array of pointers in order to remove duplicates?

c

pointers

undefined-behavior