[C++] 데이터 구조(2) - Set structures

본 게시글은 "Competitive Programmer's Handbook"을 보며 임의로 해석하며 공부한 내용입니다.

 

Set 구조

set은 삽입하는 특정 순서에 따라 고유한 원소를 저장하는 데이터 구조이다. ▶ "중복이 없다"

set의 기본 작업은 원소 삽입, 검색, 제거이다.

 

C++ 표준 라이브러리는 2가지 set 구현을 포함한다.

1. set 구조는 밸런스 이진 트리 기반으로, 이는 O(logn) 연산 시간을 가진다.
2. unordered_set 구조는 해싱을 사용하며, 이는 평균 O(1) 연산 시간을 가진다.

 

1. set 함수 선언

set<int> s;

 

2. insert함수 : set으로 원소 삽입  

set<int> s;
s.insert(3);
s.insert(2);
s.insert(5);

 

3. count함수 : set 내부 원소의 갯수를 반환한다.

set<int> s;
s.insert(3);
s.insert(2);
s.insert(5);

cout << s.count(3) << endl; // 1
cout << s.count(4) << endl; // 0

 

4. erase 함수 : set에서 원소 제거

set<int> s;
s.insert(3);
s.insert(2);
s.insert(5);

cout << s.count(3) << endl; // 1
cout << s.count(4) << endl; // 0

s.erase(3);
s.insert(5);

cout << s.count(3) << endl; // 0
cout << s.count(4) << endl; // 1

 

set은 대부분 vector처럼 사용할 수 있지만, [ ] 표기법을 통해 원소에 접근하지 못하게 할 수 있다.

 

5. set 생성, 원소의 갯수 출력, 모든 요소 반복

set<int> s = {2,5,6,8};

cout << s.size() << endl; // 4

for(auto x : s) {
	cout << x << endl;
}

 

set의 중요한 특성은 모든 원소가 구별된다는 점이다. → 중복이 없다!

 

따라서 count 함수는 0과 1 중에 하나를 반환한다.

• 0 : 집합에 해당 원소가 없음
• 1 : 집합에 해당 원소가 있음

 

insert 함수는 이미 원소가 있을 경우 해당 집합에 원소에 추가하지 않는다.

set<int> s;
s.insert(5);
s.insert(5);
s.insert(5);
cout << s.count(5) << endl; // 1

 

 

---

 

 

C++는 multiset 구조와 unordered_multiset 구조를 포함한다.

 

이 구조들은 여러개의 원소를 포함할 수 있다. → 중복을 허용!

multiset<int> s;
s.insert(5);
s.insert(5);
s.insert(5);
cout << s.count(5) << endl; // 3

 

erase 함수 : multiset의 모든 원소를 지운다.

multiset<int> s;
s.insert(5);
s.insert(5);
s.insert(5);

s.erase(5);
cout << s.count(5) << endl; // 0

 

단 하나의 원소를 제거하고 싶다면, 아래 코드와 같이 사용 가능하다.

multiset<int> s;
s.insert(5);
s.insert(5);
s.insert(5);

s.erase(s.find(5));
cout << s.count(5) << endl; // 2