알고리즘(C++) / STL : set, multiset

STL : set, multiset

2021.09.06 - [알고리즘] - 알고리즘(C++) / 프로그래머스 level 3 : 이중우선순위큐 문제를 풀면서 multiset에 대해 알 수 있었다.

set과 multiset에 대해서 공부해본다.

이미지 출처 : http://www.ccplusplus.com/2014/01/std-set-example-c.html

 

set

• 유일한 원소만을 가질 수 있는 구조로서 수학적으로 집합을 의미한다.
• key값을 저장할 수 있다. 하지만, key 값이 중복될 수 없다.(multiset은 중복 가능)
• 자동으로 정렬된다. (defalt는 오름차순)
• 노드 기반이다. 
• 균형 이진 트리로 구현되어있다. (binary search tree) 빠른 탐색이 가능하다. 
• 임의 접근이 불가능하다. (배열처럼 접근x, iter 반복자로 접근)
• 생성, 삽입(insert), 삭제(erase), 탐색(find) 등이 가능하다.
• set의 멤버 함수는 https://blockdmask.tistory.com/79 에서 자세히 확인할 수 있다. 
• 헤더 #include <set>

set<int> s1; //오름차순
set<int, greater<int>> s2; //내림차순

다음과 같이 선언하여 set을 생성할 수 있다.

 

예제 코드

//set STL
#include <iostream>
#include <set>

using namespace std;

int main() {
	set<int> s1; //오름차순 defalt
	set<int, greater<int>> s2; //내림차순
	//삽입
	s1.insert(2); s2.insert(2);
	s1.insert(3); s2.insert(3);
	s1.insert(4); s2.insert(4);
	s1.insert(3); s2.insert(3);
	s1.insert(3); s2.insert(3);
	s1.insert(1); s2.insert(1);
	
	//s1출력
	for (auto it = s1.begin(); it != s1.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

	//s2 출력
	for (auto it = s2.begin(); it != s2.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

	return 0;
}

 

결과

3을 3번 삽입하였지만 중복된 key값은 저장되지 않는다.

s1은 오름차순으로 s2는 내림차순으로 자동으로 정렬된 것이 확인가능하다. 

 

multiset

• set과 동일하지만 multiset은 key값 중복이 가능하다. (set과의 차이점)
• 자동으로 정렬된다. (defalt는 오름차순)
• 이진탐색인 upper_bound(), lower_bound()함수를 사용하여 수의 처음 위치와 마지막 위치를 찾을 수 있다. 
• 헤더 #include <set>

multiset<int> s1; //오름차순
multiset<int, greater<int>> s2; //내림차순

다음과 같이 선언하여 multiset을 생성할 수 있다.

 

예제 코드

//set STL
#include <iostream>
#include <set>

using namespace std;

int main() {
	multiset<int> s1; //오름차순 defalt
	multiset<int, greater<int>> s2; //내림차순
	//삽입
	s1.insert(2); s2.insert(2);
	s1.insert(3); s2.insert(3);
	s1.insert(4); s2.insert(4);
	s1.insert(3); s2.insert(3);
	s1.insert(3); s2.insert(3);
	s1.insert(1); s2.insert(1);

	//s1출력
	for (auto it = s1.begin(); it != s1.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

	//s2 출력
	for (auto it = s2.begin(); it != s2.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

	return 0;
}

 

결과

set과 달리 multiset은 중복된 값도 저장되어있는 것을 확인할 수 있다.