C++에서 Set 사용시 주의할 점
struct Node{
int x,y;
};
set<struct Node> Nset;
을 사용하다가 Nset.insert({x,y})를 하려던 도중, 컴파일 에러가 발생하여 조사를 시작하였다.
Set 자료구조는 내부적으로 Balanced Binary Tree(C++의 set은 레드블랙 트리)로 이루어져 있으며 삽입할때 정렬이 이루어 진다.
한 데이터의 최대 탐색속도는 Tree의 높이가 결정짓고, 높이는 데이터 수가 N개 일 때 logN이 된다.(정확히는 로그 2의 N) 따라서 삽입 연산은 적지만, 탐색 연산이 많은 경우 set을 사용하면 logN의 시간복잡도로 탐색을 마칠 수 있다는 장점이 있다.
그런데 Binary Tree에서 insert를 할 때 한 노드의 왼쪽 자식으로 넣을지, 오른쪽에 넣을지 결정은 어떻게 할까?
int 나 char 타입이라면 값의 크기나 아스키코드값 등을 비교하여 결정할 수 있을 것이다.
그런데 구조체 타입이라면..?? 애매해진다. set은 중복을 허용하지 않기 때문에 잘못 비교하면 다른 데이터인데 중복된 데이터라고 인식하여 insert가 안될 수 있기때문에 사용자가 정의해야한다. 즉, 크기 비교의 operator 재정의가 필요하다.(operator overloading)
이를 위해 구조체보다는 Class 를 만들자.
위의 예시에서는 아래와 같이 수정할 수 있다. *1000이 들어간 이유는 문제의 조건에 의해서 x와 y의 최댓값이 1000을 넘지 않는다고 하였기 때문이다.( 따라서 x,y가 다를 경우 중복을 반드시 피할 수 있다. )
class Node {
private:
int x, y;
public:
Node(int x, int y) {
this->x = x;
this->y = y;
}
bool operator<(const Node& node) const {
return x*1000 + y < node.x*1000 + node.y;
}
};
그런데 이렇게 할거면 차라리 x*1000+y값을 저장하는 set<int> 변수를 만드는 것이 나을 수도 있다.(단기간에 문제를 많이 맞추는 알고리즘 특성상 코드가 짧은게 유리하므로)
결론적으로,,,난 앞으로 set안에 struct와 같은 타입을 넣는 것을 지양할 생각이다.(map에서 key를 저장하는 것도 마찬가지다. 소스코드를 보니 c++은 별개같은데 java의 hashset이 내부적으로 hashmap으로 구성되어있었다. 즉 map도 같은 매커니즘이라고 보아도 무방하다. )
지금까지
지양한다면 '왜' 지양하는지, 그리고 어쩔 수 없이 써야하는 상황이라면 주의해야할 점은 무엇인지 정리하는 글이었다.
참고 자료