'Insert'에 해당되는 글 1건

  1. 2012.11.26 STL std::set에서 find, insert시 동등성 비교

보통 < operator를 이용한다. x라는 데이터가 set에 있는지 없는지 검사를 다음과 같이 한다.

!(x<y) && !(y<x)


그런데 x가 edge를 나타내는 등, 구조체인 경우, less operator를 지정할 수 있다.


typedef struct Edge

{

int v1, v2, w;

bool operator <(const Edge &rhs) const{

bool b = (v1 < rhs.v1 || v2 < rhs.v2);

return (b);

}

} edge;


이렇게 하면 (3, 7) 과 (7, 3)을 비교하는 과정에서 문제가 생긴다.


http://stackoverflow.com/questions/13548472/using-stdset-find-with-struct-data


typedef struct Edge

{

int v1, v2, w;

bool operator <(const Edge &rhs) const{

bool b = v1 < rhs.v1 || (v1 == rhs.v1 && v2 < rhs.v2);

return (b);

}

} edge;


위와 같이 검사해야 제대로 작동한다.


추가로 less와 greater는 다음과 같이 직접 구현할 수 있다. visual studio 2012부터는 less만 기본으로 제공하고 greater등은 제공하지 않는것 같다.


template <class T>

struct _less

{

bool operator()(const T& _Left, const T& _Right) const

{

return (_Left < _Right);

}

};


template <class T>

struct _greater

{

bool operator()(const T& _Left, const T& _Right) const

{

return (_Left > _Right);

}

};



각 컨테이너에서 다음과 같이 선언하여, comparator를 지정할 수 있다.


priority_queue<edge, vector<edge>, _greater<edge> > pq;

set<edge, _less<edge> > s;



별도로 comparator를 지정하지 않으면, less가 default로 지정된다.


priority_queue<edge, vector<edge> > pq;

set<edge > s;






Posted by Нуеоп
이전버튼 1 이전버튼