c++ - 想要查看一个 vector 中的任何值是否与另一个 vector 中的值匹配

Question

我正在为一款名为 Bulls & Cows 的游戏编写代码。我已经解决了查看一个 vector 的值(如果它们在同一索引中)是否相同的问题。但是，我不确定如何编写一个 for 循环来遍历两个 vector 并查看一个 vector 中的任何值是否与另一个 vector 中任何其他索引的值匹配。我将不胜感激任何帮助。谢谢!

Answer 1

蛮力方法是

for( auto& x1 : vec1 )
    for( auto& x2 : vec2 )
        if( x1 == x2 )
            return true;
return false;

如果两个 vector 的长度均为 n，则在未找到的情况下平均执行 n² 次比较。

这是二次方时间，O(n² )，这是非常糟糕的。

---

为了获得更好的性能，您可以将一个 vector 的所有值放入一个集合。然后您可以根据集合检查另一个 vector 的每个值。对于 std::set，每个值的检查是 log(n)，因此检查 n 值会得到 O( n log n) 时间。对于 std::unordered_set，检查基本上是常数时间，这将整个事情减少到 O(n)。

但是 std::unordered_set 有一个问题，至少对于我使用的 g++ 版本 (MinGW 5.1)，它的标准库实现不支持散列 enum 值，因此您必须提供散列函数或一般散列支持才能使代码可移植。

所以，

using Item = decltype(v1)::value_type;
std::set<Item> v1_values{ v1.begin(), v1.end() };
for( auto& x2 : v2 )
    if( v1_values.count( x2 ) > 0 )
        return true;
return false;

免责声明:编译器甚至没有看一眼代码，我不确定 count 是否是最优雅的检查方式，因为我通常只是包装标准库的东西。

---

在性能方面最好的做法是使用增量方法，例如每次向 v1 或 v2 添加值时更新此类集合。这增加了代码的复杂性，并且与您使用这些 vector 的目的无关。 IE。这是一种更具侵入性的解决方案:您通常会通过增加复杂性来支付性能费用。