c++ - 计算两个 vector 之间共享元素数量的最快方法

假设我有两个大小均为vector< pair<float, NodeDataID> > v1, v2;的向量，我想计算v1和v2中有多少个元素具有相同的NodeDataID。例如，如果v1 = {<3.7, 22>, <2.22, 64>, <1.9, 29>, <0.8, 7>}和v2 = {<1.66, 7>, <0.03, 9>, <5.65, 64>, <4.9, 11>}，那么我想返回2，因为v1和v2中有两个元素共享相同的NodeDataID：7和64。

用C ++最快的方法是什么？

仅供参考，请注意类型NodeDataIDs的定义是因为我使用boost为：

typedef adjacency_list<setS, setS, undirectedS, NodeData, EdgeData> myGraph;
typedef myGraph::vertex_descriptor NodeDataID;

但这并不重要，因为我们可以使用运算符==比较两个NodeDataID（也就是说，可以执行v1[i].second == v2[j].second）

最佳答案

将第一个向量的元素放入哈希表。遍历第二个向量，测试每个元素是否在哈希表中。

哈希表的优点是可以在固定时间内完成插入和查找。这意味着，找到交点可以在线性时间内完成。这是最佳选择，因为无论使用哪种算法，您都必须至少查看每个向量元素一次。

Boost具有boost::intrusive::hashtable，但是（顾名思义）具有侵入性。