0

同じサイズの 2 つのベクトルがあるとvector< pair<float, NodeDataID> > v1, v2;します。v1 と v2 の両方から、同じ NodeDataID を持つ要素の数を計算したいとします。たとえばv1 = {<3.7, 22>, <2.22, 64>, <1.9, 29>, <0.8, 7>}、 との場合、同じ NodeDataID を共有する v1 と v2 の 2 つの要素 (7 と 64) があるため、2v2 = {<1.66, 7>, <0.03, 9>, <5.65, 64>, <4.9, 11>}を返します。

C++ でそれを行う最も簡単な方法は何ですか?

参考までに、ブーストを次のように使用するため、型NodeDataIDsが定義されていることに注意してください。

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

しかし、演算子 == を使用して 2 つの NodeDataID を比較できるため (つまり、実行可能)、重要ではありませんv1[i].second == v2[j].second。

4

2 に答える 2

2

最初のベクトルの要素をハッシュ テーブルに入れます。2 番目のベクトルを繰り返し処理し、各要素がハッシュ テーブルにあるかどうかをテストします。

ハッシュ テーブルには、挿入と検索を一定時間で実行できるという利点があります。つまり、交差点を見つけることは線形時間で行うことができます。アルゴリズムに関係なく、各ベクトル要素を少なくとも 1 回は確認する必要があるため、これが最適です。

Boost にはboost::intrusive::hashtableがありますが、(名前が示すように) 侵入的です。

于 2012-11-09T21:52:04.023 に答える
0

最も簡単な解決策は、最初のベクトルの要素をセットに入れ、次に 2 番目のベクトルに対して、このセット (ret = myset.insert(an_id)) に各要素を挿入し、ret.second が false の場合、要素が存在することです。カウンターを増やします。

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 に答える