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

Question

假设我有两个大小相同的 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 )

Answer 1

将第一个 vector 的元素放入哈希表中。迭代第二个 vector ，测试每个元素是否在哈希表中。

哈希表的优点是可以在常数时间内完成插入和查找。这意味着，可以在线性时间内找到交点。这是最优的，因为无论算法如何，您都必须至少查看每个 vector 元素一次。

Boost 具有 boost::intrusive::hashtable ，但它(顾名思义)是侵入性的。