c++ - 如果 vector a 包含与 vector b 相同的元素，我如何有效地检查

Question

我寻找一种有效的方法来查看 vector A 是否包含与 vector B 相同的元素。两个 vector 具有不同的大小，并且每个元素是另一个具有两个元素(x 和 y 坐标)的 vector 。我需要 vector A 中相等元素的位置。目前我正在用 for 循环来做，但是 vector b 最多可以有 8000 个元素，而且我的程序现在真的很慢。我阅读了算法库，但找不到对我有帮助的东西或者我不理解它。

std::vector<std::vector<int>> VecA; 
std::vector<std::vector<int>> VecB; //size of VecB >> VecA

for( int i = 0; i < VecA; i++)
{
   for( int z = 0; z < VecB; z++)
   {
     if (VecA.at(i) == VecB.at(z))
     {
       Do Something with VecA.at(i)
     }
   }

}

感谢您的帮助。

Answer 1

一些建议:

• 不要使用 std::vector<int>对于一对值，使用 std::pair<int,int>或自定义结构
• 不要使用std::vector如果你想要一种快速的方法来检查一个集合是否包含另一个元素，但数据结构不同，例如 std::unordered_set<Coordinate>

用std::unordered_set<Coordinate>一切都会更有效率。假设:

struct Coordinate {
  int x;
  int y;
}

现在提供自定义 std::hash<Coordinate>创建一个size_t的特化来自你的 Coordinate对象和使用 std::set_intersection或比较元素的自定义循环。

如果你对坐标有一些范围限制，那么x和 y适合 16 位(例如 [0,65536) )然后散列是微不足道的( x << 16 | y )，更好的是它是明确的(具有相同键的两个元素将是相同的元素)，这为优化提供了更多空间。