0

假设我有两个大小相同的向量，vector< pair<float, NodeDataID> > v1, v2;我想计算 v1 和 v2 中有多少元素具有相同的 NodeDataID。例如 if v1 = {<3.7, 22>, <2.22, 64>, <1.9, 29>, <0.8, 7>}, and 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）

4

2 回答 2

2

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

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

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

于 2012-11-09T21:52:04.023 回答
0

最简单的解决方案是将第一个向量的元素放入一个集合中，然后对于第二个向量，我们将每个元素插入该集合中 (ret = myset.insert(an_id))，如果 ret.second 为假，则该元素存在，因此我们增加了一个计数器。

set<NodeDataID> myset;
int counter = 0;

for(int i = 0; i < v1.size(); ++i)
   myset.insert(v1[i].second);

for(int i = 0; i < v2.size(); ++i)
{
   pair<set<NodeDataID>::iterator,bool> ret = myset.insert(v2[i].second);
   if(ret.second == false)
      ++counter;
}
于 2012-11-09T22:57:50.347 回答