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

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

728x90

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 s1; //오름차순

set> s2; //내림차순

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

예제 코드

//set STL #include #include using namespace std; int main() { set s1; //오름차순 defalt set> 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

multiset s1; //오름차순

multiset> s2; //내림차순

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

예제 코드

//set STL #include #include using namespace std; int main() { multiset s1; //오름차순 defalt multiset> 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은 중복된 값도 저장되어있는 것을 확인할 수 있다.

728x90

from http://se-jung-h.tistory.com/157 by ccl(A) rewrite - 2021-09-06 15:00:21