如何在C++中从向量中删除几乎重复的元素

Question

我有一个std :: vector的浮点数，我希望它不包含重复项，但是用于填充向量的数学并不完全精确。该向量具有相差几百分之几的值，但应视为同一点。例如，在其中一个中有一些值：

...
X: -43.094505
X: -43.094501
X: -43.094498
...

如何最好/最有效地从此类向量中删除重复项。

- Max Rahm

---

你想保留它们的顺序吗？ - Deduplicator

@RedAlert：这允许对它们进行聚类，但是非常相似的数字可能会分别出现在不同的集合中。 - Deduplicator

@RedAlert：你不能使用set。没有适用的偏序关系。特别地，如果a<b && b<c，则a<c，但是如果a<c，则a<=b || b<=c。在这种情况下，可以选择b=a+epsilon，c=a+2*epsilon。 - MSalters

@MSalters 集合可以使用任何比较函数进行初始化。 - Red Alert

考虑改进向量的填充，而不是事后“修复”它。 - Walter

Answer 1

首先使用std::sort对向量进行排序。然后使用自定义谓词的std::unique函数来去除重复项。

std::unique(v.begin(), v.end(), 
            [](double l, double r) { return std::abs(l - r) < 0.01; });
// treats any numbers that differ by less than 0.01 as equal

Live demo

- Praetorian

---

在调用unique之后，您还可以调整元素的大小。myvector.resize(std::distance(myvector.begin(), it)); - evpo

@evpo：实际上，你应该说得更加强烈。必须清除尾部的引用。 - Deduplicator

@Deduplicator 或者调用 vector::erase，或者使用 unique_copy 写入到另一个容器中。多余的元素可以通过多种方式处理，包括我示例中展示的方法。这并不意味着这是解决此问题的唯一明确方法。 - Praetorian

@Praetorian 在 C++03 中（在 lambda 函数出现之前）应该如何实现这个？ - Tyler Shellberg

Answer 2

1. 排序总是一个很好的第一步。使用 std::sort()。

2. 删除不足够唯一的元素：std::unique()。

3. 最后一步，调用 resize()，也许还要调用 shrink_to_fit()。

如果你想保留顺序，在副本上执行前面的三个步骤（省略缩小）。
然后使用带有lambda表达式的std::remove_if，检查副本中元素的存在性（二进制搜索）（找到后别忘了删除），只保留在副本中找到的元素。

- Deduplicator

---

关于您的第三点，“reserve(0)”完全没有任何作用。 - Blastfurnace

@Blastfurnace：我以为它和 std::string 一样。我讨厌这种小小的不一致性。 - Deduplicator

没有任何矛盾，对string调用reserve(0)也不会有任何作用。另外请注意，shrink_to_fit是非绑定的，这意味着实现可能选择忽略它。 - Praetorian

@Praetorian 在字符串上调用reserve(0)等同于调用shrink_to_fit()，两者都是非绑定的收缩请求。对于vector来说，reserve(...)永远不是一个收缩请求。 - Deduplicator

是的，你说得对。感谢指出不一致性。 - Praetorian

Answer 3

大多数答案的问题在于您有一个不寻常的“相等性”。如果A和B相似但不完全相同，则希望将它们视为相等。基本上，A和A + epsilon仍然被视为相等，但是A + 2 * epsilon不是（对于某些未指定的epsilon）。或者，根据您的算法，A *（1 + epsilon）和A *（1 + 2 * epsilon）不同。

这意味着A + epsilon与A + 2 * epsilon相等。因此，A = B且B = C并不意味着A = C。这打破了中的常见假设。

您仍然可以对值进行排序，这是一个明智的做法。但是，您必须考虑在结果中处理一系列相似值的方法。如果范围足够长，则第一个和最后一个之间的差异仍然可能很大。没有简单的答案。

- MSalters

Answer 4

我会做以下事情：

1. 创建一个 set<double>
2. 通过循环或使用函数对象遍历向量
3. 对每个元素进行四舍五入并插入到集合中
4. 然后，您可以将您的向量与一个空向量交换
5. 将所有元素从集合复制到空向量中

这种方法的复杂度为 n * log(n)，但它更简单，可以用几行代码完成。内存消耗将从仅存储向量的两倍。此外，每个元素的 set 消耗的内存略多于向量。但是，在使用后，您将销毁它。

std::vector<double> v;
v.push_back(-43.094505);
v.push_back(-43.094501);
v.push_back(-43.094498);
v.push_back(-45.093435);

std::set<double> s;

std::vector<double>::const_iterator it = v.begin();
for(;it != v.end(); ++it)
    s.insert(floor(*it));

v.swap(std::vector<double>());
v.resize(s.size());
std::copy(s.begin(), s.end(), v.begin());

- evpo

Answer 5

嗨，你可以像这样比较

bool isAlmostEquals(const double &f1, const double &f2)
{
  double allowedDif = xxxx;
  return (abs(f1 - f2) <= allowedDif);
}

但这取决于您的比较范围，双精度不在您这一方面

如果您的向量已排序，则可以使用带有函数谓词的std::unique

- Boo

Answer 6

我建议使用std::sort()函数，然后逐一检查并删除在特定范围内的值。

你可以为同一个向量创建一个单独的写迭代器，并在最后进行一次resize操作，而不是为每个被删除的元素调用erase()函数或者创建另一个目标副本以提高性能和减少内存使用。

- Yirkha

Answer 7

如果您的向量不能包含重复项，则使用std::set可能更为合适。然后，您可以使用自定义比较对象将小更改视为无关紧要。

- Velox