[STL] Set Container

📌 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)