[C++][Data Structure] std::set 컨테이너 (2)

안녕하세요! 두두코딩 입니다 ✋
오늘은 Set의 자료구조에 대해 알아보겠습니다.

이전 포스팅을 참고하시면 더 이해가 편합니다!

🖇 소스코드에 마우스를 올리고 copy 버튼을 누를 경우 더 쉽게 복사할 수 있습니다!

궁금한 점, 보안점 남겨주시면 성실히 답변하겠습니다. 😁
+ 감상평 댓글로 남겨주시면 힘이됩니다. 🙇

중복된 값을 삽입할 경우

Set 같은 경우 고유한 값을 특정한 순서에 따라 저장하는 컨테이너이다. 고유한 값이 들어온다는 전제가 있지만, 만약 개발자가 동일한 값을 입력했을 때 어떻게 될까?

결론적으로는 아무일도 일어나지 않는다😵

set 내부에선 어떻게 처리할지 알아보자.

set_dup

위의 그림과 같이, set 에서는 데이터를 삽입할 때, 하나의 pair 형태로 반환한다. pair의 첫번째 값은 해당 위치를 가리키는 반복자이고, 두 번째 인자 값은 삽입 성공유무를 판단하는 bool 변수이다.

#include <iostream>
#include <set>

using namespace std;

int main()
{
	set<int> s;
	s.insert(30);
	s.insert(40);
	s.insert(20);
	s.insert(10);
	s.insert(45);
	s.insert(25);

	// 동일한 값을 넣었을 때
	auto ret = s.insert(20);

	// 두번째 인자로 성공유무 판단.
	// 실패라는 것은 중복된 값이라는 것.
	if (ret.second == false)
			cout << "duplicated value" << endl;

}

위의 예시처럼, 값이 동일하게 들어올 경우, 반환 값을 받아 두번째 값으로 확인해보면, 중복 유무를 판단할 수 있다.

auto ret = s.insert(20);

// 원래 형태
pair<set<int>::iterator, bool> ret = s.insert(20);

위의 코드에서 보이는 것과 같이, 원래 형태는 복잡하다. 따라서, 간단하게 auto로 쓰고, 원형을 한번 눈에 익히도록 하자.

중복된 값을 허용하는 set

그렇다면 set에서는 중복된 값을 넣을 수 없을까?

set자료구조가아닌 multiset 자료구조를 사용하면 중복을 사용할 수 있다. 위의 코드를 multiset으로 변경해보자.

#include <iostream>
#include <set>

using namespace std;

int main()
{
	// set -> multiset으로 변경
	// set<int> s;
	multiset<int> s;
	s.insert(30);
	s.insert(40);
	s.insert(20);
	s.insert(10);
	s.insert(45);
	s.insert(25);

	// 동일한 값을 넣었을 때
	auto ret = s.insert(20);

	// multiset 일경우 중복된 값이 무조건 들어가기때문에
	// 성공유무를 판단할 필요가 없다.
	// if (ret.second == false)
	//		cout << "duplicated value" << endl;

	auto p = begin(s);

	while( p != end(s) )
	{
		cout << *p << endl;
		++p;
	}
}

위의 코드와 같이, set을 multiset으로 변경해서 사용해보자. 중요한 특징은 multiset같은 경우 중복된 값을 무조건 허용하기 때문에, set과 달리 pair형식으로 반환값을 전달받는 것이 아닌 iterator만 전달받는다.

따라서, second로 중복 유무를 검사하는 부분을 주석으로 막고 테스틀해야한다.

사용자 정의 타입을 set에 넣기

우리는 프로그램을 개발하면서 기본 데이터 타입만 사용하는것이 아니라, 때론 사용자 정의 타입 (class)를 만들어 사용한다. 하지만 set은 사용자 정의 타입이 있는지도 알지 못한다.

아래의 예시를 통해 알아보자.

#include <iostream>
#include <set>

using namespace std;

struct Point
{
	int x,y;
	Point(int a = 0, int b = 0) : x(a), y(b) {}
};

int main()
{
	set<Point> s;

	s.insert(Point(1,1));
	s.insert(Point(2,2));
	s.insert(Point(3,3));
}

위의 코드를 수행했을 때, set에서는 사용자 정의 타입을 알지못하는 상태에서 비교한다. 사실 set에서는 어떻게 비교를 해야하는지도 몰라 아래와 같은 에러를 출력한다.

...
/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX.sdk/usr/include/c++/v1/set:675:25: note: in instantiation of member function 'std::__1::__tree<Point, std::__1::less<Point>, std::__1::allocator<Point>>::__insert_unique' requested here
        {return __tree_.__insert_unique(_VSTD::move(__v));}
                        ^
set.cc:16:4: note: in instantiation of member function 'std::__1::set<Point, std::__1::less<Point>, std::__1::allocator<Point>>::insert' requested here
        s.insert(Point(1,1));
          ^
/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX.sdk/usr/include/c++/v1/utility:592:1: note: candidate template ignored: could not match 'pair<type-parameter-0-0, type-parameter-0-1>' against 'const Point'
operator< (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
^
1 error generated.

이런 set자료구조에 사용자 정의 타입을 넣으려면 어떻게 해야할까?

해결하는 방법은 함수 객체 제공 과 < 연산자 재정의 두 가지를 활용하면 된다.

🌱 함수 객체 제공

함수 객체를 제공하는 것은 템플릿 단위전략 패턴을 활용하는 방법으로, set에서 해당 타입을 비교할 때, 내가 전달한 비교함수로 해줘~ 라고 요청하는 것이다.

// 함수 객체 만들기
struct Pointless
{
	// 편의상 x만 비교합니다.
	bool operator()(const Point& p1, const Point& p2) const
	{
		return p1.x < p2.x;
	}
};

int main()
{
	set<Point, Pointless> s;

	s.insert(10);
	...
}

위의 코드와 같이, Pointless 함수 객체를 만들어, set의 두번째 인자로 넘겨주게 되면 된다. set은 두번째 인자를 전달받아 해당 비교 객체를 통해 비교하도록 한다.

🌱 < 연산자 재정의

위의 방법보다 더 쉽게 구현할 수 있는 방법이다. 바로 < 연산자 를 재정의해두면 set이 알아서 사용하도록 한다.

struct Point
{
	int x,y;
	Point(int a = 0, int b = 0) : x(a), y(b) {}

	// < 연산자 재정의
	// 편의상 x 값만 비교
	bool operator<(const Point& p) const
	{
		return x < p.x;
	}
};

위와 같이, 사용자 정의 타입에 operator<를 넣어둘 경우 set은 자동적으로 비교할 수 있다.

사용자 정의 타입 상등연산

그렇다면 우리는 set을 잘 사용하기 위해 어떤 비교연산들을 제공해야할까?

당연히 insert()를 위해 < 연산자 와 > 연산자 두개를 함수 객체나 연산자 재정의로 제공해야한다.

만약 우리가 동일한 값을 입력하거나 find() 함수를 사용하기 위해서 == 연산을 제공해야할까? 생각해보자🤔

결론적으로는 ”==” 연산자는 제공할 필요가 없다 이다.

set 내부적으로는 상등을 조사하는 방법이 있다.

// set 내부 과정 간략화
if (newelem < oldelem) left
else if (oldelem < newelem) right
else // 모두 같다고 판단..

위의 코드는 상등을 구하는 부분을 간략화한 것이다. set 내부에서는 “<” 연산과 “>” 연산을 통해 비교를 하고, 나머지는 상등으로 취급하기 때문에 == 연산은 굳이 필요하지가 않다.

== 연산은 만들어도 사용하지 않는다는 점을 기억하자!

[C++][Data Structure] std::set 컨테이너 (2)

C++ set 자료구조 사용하는 방법을 알아보자😚

중복된 값을 삽입할 경우

중복된 값을 허용하는 set

사용자 정의 타입을 set에 넣기

사용자 정의 타입 상등연산

Table of Content