c++ - 从自定义类型的 std::list 中删除重复项的最快方法

Question

如果之前有人问过请原谅我，我找不到了。我有一个自定义类型，我可以为其实现(模糊)相等但没有 <具有传递性的运算符。比较是昂贵的，但我没有太多的元素。我需要整理出几乎完全相同的多边形(它们大部分重叠)。自从使用 < 订购以来由于缺少可传递的实现是不可能的我正在使用如下所示的 std::list:

typedef std::list<Polygon> PolyList;
PolyList purged(rawList);
for (PolyList::iterator iter= purged.begin(); iter!=  purged.end(); ++iter) {
  for(PolyList::iterator toRemove = find(boost::next(iter),purged.end(),*iter); toRemove != purged.end(); ){
      PolyList::iterator next = purged.erase(toRemove);
      toRemove = find(next,purged.end(),*iter);
    }
  }

复杂度是 n*n/2 这在我看来是不可避免的并且虽然该算法工作正常，但读写起来仍然非常麻烦，我几乎可以肯定有一个我不知道的标准算法，或者至少有一些速度快但打字更整洁的算法。正如我所说，由于数据的模糊性，排序不是一种选择，因此没有唯一的集合或排序。非常感谢您帮助我

Answer 1

您可能不会在标准中找到答案，因为您的“重复项”听起来也不是可传递的。也就是说 a==b && b==c 并不意味着 a==c。

仅出于这个原因，任何算法都必须比较所有对，这会为您提供 (N*N-1)/2 比较(假设您的相等性是对称的，即 a== b 确实暗示b==a)。