c++ - 仅使用几乎相等的标准(无排序)从容器中删除重复项的最有效方法是什么

Question

当我无法定义 operator< 时，如何从未排序的容器(主要是 vector )中删除重复项例如当我只能定义一个模糊比较函数时。

This answer using sort不起作用，因为我无法定义用于排序数据的函数。

template <typename T>
void removeDuplicatesComparable(T& cont){
 for(auto iter=cont.begin();iter!=cont.end();++iter){
    cont.erase(std::remove(boost::next(iter),cont.end(),*iter),cont.end());
 }
}

这是 O(n²) 并且在缓存命中方面应该非常本地化。是否有更快或至少更简洁的解决方案？

编辑:为什么我不能使用集合。我做几何比较。一个例子可能是这个，但我还有其他不同于多边形的实体。

bool match(SegPoly const& left,SegPoly const& right,double epsilon){
  double const cLengthCompare = 0.1; //just an example
  if(!isZero(left.getLength()- right.getLength(), cLengthCompare)) return false;
  double const interArea =areaOfPolygon(left.intersected(right)); //this is a geometric intersection
  if(!isZero(interArea-right.getArea(),epsilon)) return false;
  else return true;
}

因此对于此类比较，我不知道如何制定排序或简洁的哈希函数。

Answer 1

首先，不要一次删除一个元素。

接下来，使用哈希表(或类似结构)来检测重复项。

如果您不需要保留顺序，则将所有元素复制到哈希集中(这会破坏重复项)，然后使用哈希集中剩余的值重新创建 vector 。

如果您需要保持秩序，那么:

1. 将读写迭代器设置到 vector 的开头。
2. 开始移动读取迭代器，根据哈希集或八叉树或允许快速找到附近元素的东西检查元素。
3. 对于与哈希集/八叉树中的一个元素发生冲突的每个元素，仅推进读取迭代器。
4. 对于不冲突的元素，从读取迭代器移动到写入迭代器，复制到哈希集/八叉树，然后推进两者。
5. 当读迭代器到达末尾时，调用erase在写迭代器位置截断 vector 。

八叉树的主要优势在于，虽然它不会让您立即确定是否有足够接近的东西成为“重​​复”，但它允许您仅针对近邻进行测试，排除大部分数据集。因此，根据空间分布，您的算法可能是 O(N lg N) 甚至是 O(N lg lg N)。

同样，如果您不关心顺序，您实际上可以将幸存者移动到哈希集/八叉树中，最后将它们移回 vector 中(紧凑地)。