두 벡터의 변수 매칭 및 효율적인 방법으로 비교지도 만들기

Question

두 벡터 내에서 동일한 객체 인스턴스 중 일부를 가진 두 개의 벡터 벡터와 일치하는 코드를 작성했습니다.

아이디어는 '기본'벡터에서 개체의 색인을 찾아 다른 벡터의 개체와 일치시키는 것입니다.

주 벡터의 색인은 해당 개체가있는지도에서 사용됩니다.

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 

당신은 내가 거기에 기본적으로 고유 인덱스로 두 개체를 비교하고이 일치하는 경우 개체가 일치합니다 볼 수 있듯이 :

나는 코드를 보는 것은 나의 설명이 좀 명확하게 할 수있다 생각합니다.

내 quesitons :

내가 객체 클래스의 비교 연산자를 오버로드 할 수 알지만, 이런 일이 올 것 만약 내가 확실하지 않았다? 또한

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

,

는 일부 STL 알고리즘 (부스트 libs와 사용할 수 없습니다) 또는 스마트 뭔가를 사용하여 위의 코드의 짧은/더 효율적인 방법이 있나요 ??

마이크

Answer 1

가지 방법의 커플 O (N^2)보다 더 효율적으로이 작업을 수행 할 수 있습니다. 예를 들어

: 첫 번째 벡터

• 정렬 소자.
• 두 번째 벡터의 요소를 정렬합니다.
• 정렬 된 벡터에 set_intersection을 사용하십시오.

또는 : multiset (또는 unordered_multiset)에 모두 벡터의

• 넣어 요소.
• 의 키가 이 넘고 요소가 일치하는 것을 나타냅니다.

두 가지 방법 모두 실제 요소 대신 원본 벡터에서 포인터 또는 인덱스를 사용할 수 있습니다. 포인터/인덱스를 처리 할 수있는 비교 자 (sort, set_intersection 및 multiset)를 제공하는 데주의하십시오.