9. STL Equality and Equivalence

예전부터 많이 사용하는 그런 기능이라 이틀 연속으로 올리네 허헣... 졸리다...

 

일단 간단한 코드 먼저 보자

#include <stdio.h>
#include <set>

void main()
{
	std::set<int> s1;
	s1.insert(1);
	s1.insert(5);
	s1.insert(2);

	for (int v : s1)
	{
		printf("%i\r\n", v);
	}
}

여기서 사용하는 set은 RB트리로 값이 있는지 없는지 유무만 판단하기 위해 담아두는 자료구조이다. 대신 탐색 시간을 단축하기 위해 정렬해서 값이 들어간다. 기본값은 오름차순이다. 따라서 위에 코드를 실행시키면

1
2
5

이런식으로 나오게 된다.

 

만약, int형이 아니고 직접 정의한 클래스나 구조체를 넣어보자

 

#include <stdio.h>
#include <set>

class KPoint
{
public: 
	int _x;
	int _y;
public:
	KPoint(int x, int y) : _x(x), _y(y)
	{
	}
};

void main()
{
	std::set<KPoint> s1;
	s1.insert(KPoint(1,1));
	s1.insert(KPoint(1,5));
	s1.insert(KPoint(1,2));

	for (const KPoint v : s1)
	{
		printf("(%i, %i)\r\n", v._x, v._y);
	}
}

이렇게 하고 실행을 하면!!!!!!!!
에러가 난다.... ㅠㅠ

 

왜 에러가 나냐 하면... 위에 말했듯이 set은 대소 비교를 하여 정렬을 하게 된다. 하지만 위에 정의한 클래스 KPoint에는 대소 비교가 없다.
그러면 operator를 사용해서 정의 해주면 된다. (개인적으로 우선순위 큐로 문제 풀때는 많이 사용했고 개발하다가 필요하면 가끔 사용하고 있다.)

 

class KPoint
{
public: 
	int _x;
	int _y;
public:
	KPoint(int x, int y) : _x(x), _y(y)
	{
	}
	bool operator<(const KPoint& rhs) const
	{
		return _y < rhs._y;
	}
};

이런식으로 하면

(1, 1)
(1, 2)
(1, 5)

잘 들어가게 된다.
그런데 여기서 같은 값은 어떻게 판단할까?
내부적으로 같은 값은 저거 하나만 사용해도

!(a < b) && !(b < a);

이런식으로 ==을 구현한다.

여기서 조그마한 문제(생각해보니까 조금 크다)가 생긴다.
(2, 5)를 insert하면 어떤 문제가 생길까?

정답은!?!?!??

위에 출력한 값과 같은 값이 출력이 된다. 왜그럴까?
앞서 말했듯이 set은 값의 유무를 판단하기 위해 만들어진 자료구조이다. 그런데 operator < 에서 비교값은 y값만 했기 때문에 코드 상으로는 (1, 5)와 (2, 5)가 같은 값이라 판단하여 값을 넣어주지 않는다.
그러면 (2, 5)를 넣고싶다면 x의 값도 같이 비교해주면 된다.(간단~)

 

	bool operator<(const KPoint& rhs) const
	{
		//return _y < rhs._y;
		if(_y != rhs._y)
		{
			return _y < rhs._y;
		}
		return _x < rhs._x;
	}

이런식으로 수정해두자. 그러면

(1, 1)
(1, 2)
(1, 5)
(2, 5)

쨖쨔꺆쨔ㅑ꺄쨔꺄쨔꺄쨔쨖쨖
잘 들어갔다.

 

위에서 ==은 자동으로 판단 한다고 했지만, find를 사용하면 조금 문제가 달라진다.
find는 operator<를 사용하지 않고 operator==을 사용한다. 그래서 따로 정의해주어야 한다.

	bool operator==(const KPoint& rhs) const
	{
		return _x == rhs._x && _y == rhs._y;
	}

이런식으로 정의 해주자.

 

그렇게 하면

void main()
{
	std::set<KPoint> s1;
	s1.insert(KPoint(1,1));
	s1.insert(KPoint(1,5));
	s1.insert(KPoint(1,2));
	s1.insert(KPoint(2,5));

	for (const KPoint v : s1)
	{
		printf("(%i, %i)\r\n", v._x, v._y);
	}

	std::find(s1.begin(), s1.end(), KPoint(1, 2));
}

(#include <algorythm> 추가 해주어야 한다.)
문제없이 실행 된다.