📌 Set
- associative container
- 중복되지 않는 key를 원소로하는 컨테이너
- 특정 기준에 따라 원소들을 자동으로 정렬
- 위치가 계속 변경되므로 원소에 직접 접근이 불가능
- 균형 이진트리 (balanced binary tree) 형태
- 원소 추가, 제거, 탐색 등의 연산 시간복잡도: O(log n)
✔ set 사용
#include <set>
using namespace std;- <set> header
- std::set
✔ set 생성
set<[type], [compare]> [name]
[compare] default : less<[type]>
- set에 저장될 타입을 명시
- 우선순위 기준이 없는 경우, 오름차순으로 정렬
// 비어있는 정수형 타입 set s1을 생성
set<int> s1;
// 기존에 있는 vector 컨테이너를 s2에 복사
vector<int> v = { 10, 30, 30, 30, 20, 20, 50 };
set<int> s2(v.begin(), v.end()); // 중복 제거
- 비어 있는 set을 생성하거나 다른 container에서 복사하여 생성 가능
- 다른 container에서 복사되는 과정에서 오름차순 정렬 및 중복 원소 제거
✔ set 멤버 함수
1) capacity
| function | description |
|---|---|
| s.size() | set s의 크기 반환 |
| s.empty() | 비어있으면 true, 그렇지 않으면 false 반환 |
2) iterators
| function | description |
|---|---|
| s.begin() | 첫번째 원소를 가리키는 iterator |
| s.end() | 마지막 원소의 다음을 가리키는 iterator |
| s.rbegin() | 마지막 원소를 가리키는 iterator |
| s.rend() | 첫번째 원소의 이전을 가리키는 iterator |
vector<int> v = { 10, 30, 30, 30, 20, 20, 50 };
set<int> s(v.begin(), v.end());
set<int>::iterator iter;
for (iter = s.begin(); iter != s.end(); iter++)
{
cout << *iter << " "; // output : 10 20 30 50
}3) modifiers (수정)
| function | description |
|---|---|
| s.insert(x) | 원소 x를 set s에 삽입 |
| s.erase(x) | 원소 x를 set s에서 제거 |
| s.clear() | 모든 원소 제거 |
4) operations (연산)
| function | description |
|---|---|
| s.find(x) | 원소 x가 위치한 iterator를 반환. 없는 경우 s.end() 반환 |
| s.count(x) | 원소 x의 개수 반환 |
set<int> s;
s.insert(10); // 10
s.insert(50); // 10 50
s.insert(30); // 10 30 50
s.insert(30); // 10 30 50 (변화없음)
s.insert(80); // 10 30 50 80
s.erase(80); // 10 30 50
s.erase(20); // 10 30 50 (변화없음)
for (int i = 10; i <= 80; i += 10)
{
if (s.find(i) != s.end())
cout << i << " is in set ";
else
cout << i << " is not in set ";
cout << "(" << s.count(i) << " element)\n";
}- output :
10 is in set (1 element)
20 is not in set (0 element)
30 is in set (1 element)
40 is not in set (0 element)
50 is in set (1 element)
60 is not in set (0 element)
70 is not in set (0 element)
80 is not in set (0 element)✔ set 예제
두 배열이 동일한 동류의 값들로 구성되었는지 판단
#include <iostream>
#include <set>
using namespace std;
int main()
{
int arr1[8] = { 20, 50, 70, 50, 30, 20, 20, 20 };
int arr2[8] = { 70, 70, 50, 50, 30, 20, 70, 20 };
set<int> s1(arr1, arr1 + 8); // 20 30 50 70
set<int> s2(arr2, arr2 + 8); // 20 30 50 70
if (s1 == s2) cout << "두 배열은 동일한 종류로 구성";
return 0;
}- 각 배열들이 set으로 복사되면서 중복이 제거되고 오름차순으로 정렬
- 비교 연산자를 통해 두 set이 동일한지 비교 가능
📌 Multiset
- 원소가되는 key들의 중복을 허용
- 이외에는 set의 특성과 동일
✔ multiset 사용
#include <set>
using namespace std;- <set> header
- std::multiset
✔ multiset 생성
multiset<[type], [compare]> [name]
[compare] default : less<[type]>
- multiset에 저장될 타입을 명시
- 우선순위 기준이 없는 경우, 오름차순으로 정렬
// 비어있는 정수형 타입 multiset ms1을 생성
multiset<int> ms1;
// 기존에 있는 vector 컨테이너를 ms2에 복사
vector<int> v = { 10, 30, 30, 30, 20, 20, 50 };
multiset<int> ms2(v.begin(), v.end());
- 비어 있는 multiset을 생성하거나 다른 container에서 복사하여 생성 가능
- 다른 container에서 복사되는 과정에서 오름차순으로 정렬되며, 중복은 제거되지 않음
✔ multiset 멤버 함수
1) capacity
| function | description |
|---|---|
| ms.size() | multiset ms의 크기 반환 |
| ms.empty() | 비어있으면 true, 그렇지 않으면 false 반환 |
2) iterators
| function | description |
|---|---|
| ms.begin() | 첫번째 원소를 가리키는 iterator |
| ms.end() | 마지막 원소의 다음을 가리키는 iterator |
| ms.rbegin() | 마지막 원소를 가리키는 iterator |
| ms.rend() | 첫번째 원소의 이전을 가리키는 iterator |
vector<int> v = { 10, 30, 30, 30, 20, 20, 50 };
multiset<int> ms(v.begin(), v.end());
multiset<int>::iterator iter;
for (iter = ms.begin(); iter != ms.end(); iter++)
{
cout << *iter << " "; // output : 10 20 20 30 30 30 50
}3) modifiers (수정)
| function | description |
|---|---|
| ms.insert(x) | 원소 x를 multiset ms에 삽입 |
| ms.erase(x) | 원소 x를 multiset ms에서 모두 제거 |
| ms.clear() | 모든 원소 제거 |
4) operations (연산)
| function | description |
|---|---|
| ms.find(x) | 원소 x가 위치한 iterator를 반환. 없는 경우 ms.end() 반환 |
| ms.count(x) | 원소 x의 개수 반환 |
vector<int> v = { 70, 60, 70, 30, 30, 50 };
multiset<int> ms(v.begin(), v.end()); // 30 30 50 60 70 70
ms.insert(10); // 10 30 30 50 60 70 70
ms.insert(20); // 10 20 30 30 50 60 70 70
ms.insert(50); // 10 20 30 30 50 50 60 70 70
ms.insert(50); // 10 20 30 30 50 50 50 60 70 70
ms.erase(20); // 10 30 30 50 50 50 60 70 70
ms.erase(30); // 10 50 50 50 60 70 70
for (int i = 10; i <= 80; i += 10)
{
if (ms.find(i) != ms.end())
cout << i << " is in set ";
else
cout << i << " is not in set ";
cout << "(" << ms.count(i) << " element)\n";
}
- output :
10 is in set (1 element)
20 is not in set (0 element)
30 is not in set (0 element)
40 is not in set (0 element)
50 is in set (3 element)
60 is in set (1 element)
70 is in set (2 element)
80 is not in set (0 element)