高效地比较std::vector中的所有元素与同一向量中的每个其他元素

Question

我是C++的新手。

我正在尝试找到如何迭代遍历向量，以将每个元素与其他每个元素进行比较，其中比较顺序是不相关的，即;

(a 'compared to' b) = (b 'compared to' a)

因此，检查一个元素意味着您不需要将每个值与EVERY其他值进行比较，而只需比较其余值。

我有一个类似于这个TOY算法的东西;

#include <vector>

typedef std::vector<double> vector_t;

int countTheFoo(const vector_t &v)
{
  int fooFound {0};
  for (auto it1 = v.begin(); (it1 != v.end()); it1++)
  {
    for (auto it2 = it1.next(); (it2 != v.end()); it2++)
    {
      if testForFoo(*it1, *it2)
      {
        // Woot! Found some...
        fooFound++;
      }
    }
  }
  return fooFound;
}

vector_t foo { 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0 };

int numFoo {countTheFoo(foo)};

我实际上是在比较线条，找到相交的线条而不是简单的重复线条，但技术方法是一样的。

这就是;

for (auto it2 = it1.next(); (it2 != v.end()); it2++)

我认为可以使用lambda表达式更高效地完成以下部分。

这种方法是可行的，但是：

• 在进行此类迭代时，它是否是最有效的方式？

• 是否可以使用std::for_all()将其作为lambda实现？

谢谢。

- David H Parry

---

是否定义了大于/小于关系？如果是，您可以对列表进行排序，并且可以避免比较所有内容。 - James Wierzba

不知道那是否可行...我实际上是在比较相交的线而不是简单的数字，所以我正在寻找解决方案的通用形式，而不是简单的双精度数。 - David H Parry

如果向量包含三个（或更多）相等的元素，则会得到错误的结果。 - user2249683

如果最高效意味着性能：是的（代码很高效，此外你应该习惯使用前缀自增 ++it）如果最高效意味着可维护性：可能（然而，代码仍然容易理解） - user2249683

@Dieter 是的。我已经使用了lambda表达式，发现它们更易于理解和相当整洁。顺便问一下，使用前增量和后增量有什么大的区别吗？ - David H Parry

@DavidHParry 不是在这里，但你可能会在某个时候使用更复杂的迭代器（例如：通过将代码制作为模板/通用算法）。 - user2249683

Answer 1

不需要测试 (it1 != it2)，因为根据你在 it2 上的循环定义，it2 总是大于 it1。如果从代码中删除该短语，效率将会提高。

你可能可以使用 std::for_all，但不清楚是否能增加代码的效率。

- Logicrat

Answer 2

使用一个std :: set 和单个循环来检查向量中的值是否已经存在于设置中; 如果不存在，则插入它。

这确实是std :: set 的用途。很难想出一种查找实现方法，可以胜过std :: set 。

- Sam Varshavchik

---

std::sort 可以轻松胜过 std::set。 - Slava

std::lower_bound和std::binary_search在排序向量上都是具有对数复杂度的二分查找。缺点是您必须对向量进行排序或以排序方式插入元素（再次使用例如lower_bound），这可能会触发重新分配和复制。对于相对较小的数据集，甚至线性搜索（find_if）也比搜索集更快，因为处理器缓存。 - Michał Góral

这没有任何意义。如果谓词是一个等价关系，并且 OP 可以访问兼容的弱序，那么他可以通过简单地对数据进行排序并比较相邻元素（也不需要二分搜索）来做得更好。 - filipos