2つのベクトルの変数の一致と効率的な比較のマップの作成

Question

両方のベクトル内に同じオブジェクトのインスタンスのいくつかを持つオブジェクトの2つのベクトルと一致するコードを少し書いています。

「main」ベクトルでオブジェクトのインデックスを見つけ、それを他のベクトルのオブジェクトに一致させることです。

メインベクトルのインデックスは、そのオブジェクトを持つマップで使用されます。

私はコードを見ることは私の説明が少し明確にかもしれないと思う：

ifndef OBJECTMAPMATCH_H 
#define OBJECTMAPMATCH_H 

#include <map> 
#include <utility> 
#include <vector> 
#include <typeinfo> 
#include <iostream> 
#include <stdlib.h> 

namespace ObjectMapMatch { 

    ... 
    ... 
    template< class A, class B > 
    std::map<int, B*>* getIndexMap(std::vector<A*>* x , std::vector<B*>* y, std::map<int, B*>* output) 
    { 
     typename std::vector<A*>::iterator Aitr = x->begin(); 
     typename std::vector<A*>::iterator AitrE = x->end(); 
     typename std::vector<B*>::iterator Bitr = y->begin(); 
     typename std::vector<B*>::iterator BitrE = y->end(); 

     for(int index=0; Aitr!=AitrE; ++Aitr, ++index){ 
     //Keep track of original index 
     int AntupIndex = (*Aitr)->Index(); 
     int match = false; 

     for(; Bitr!=BitrE; ++Bitr){ 
      int BntupIndex = (*Bitr)->Index(); 

      if(AntupIndex == BntupIndex){ 
       match = true; 
       output[index] = (*Bitr); 
      } 
      } //End of loop B 

      if(!match){ 
      std::cout << "ERROR:ObjectMapMatch::getIndexMap: Can not Find Match" << typeid(y).name() << " FOR " << typeid(x).name() << std::endl; 
      exit(1); 
      } 

      }//End of Loop A 

      } 

    ... 
    ... 
} 
#endif 

あなたは、私は基本的にそこにユニークインデックスを持つ2つのオブジェクトを比較していますし、これが一致する場合、オブジェクトが一致します見ることができるように。

マイquesitons：

私は、オブジェクトクラスの比較演算子をオーバーロードしている可能性が知っているが、このようなものが正しいだろう場合、私は確認されませんでした？

bool operator==(object1& lhs, object2& rhs){ 
    &lhs == &rhs ? return true : return false; 
} 

また、

は、いくつかのSTLアルゴリズム（ブーストLIBSを使用することはできません）、またはよりスマートなものを使用して上記のコードの短い/より効率的な方法はあります？

マイク

Answer 1

より効率的にはO（n^2）よりもこれを行うにはいくつかの方法があります。例えば

：最初のベクトルの

• 並べ替え要素。
• 第2ベクトルの要素をソートします。
• ソートベクターにset_intersectionを使用してください。

または：multiset（またはunordered_multiset）に両方ベクトルの

• 入れ要素。
• が複数の要素を持つmultisetのキーが一致することを示します。

これらの方法の両方について、実際の要素の代わりに元のベクトルにポインタまたはインデックスを使用できます。ポインター/インデックスを扱うことができるコンペラー（sort、set_intersection、multiset）を提供するように注意してください。