[무기] Container <SET> 이란? - CPP

SET

Container <set>은 내부적으로 이진 검색 트리로 구현되어 있어 효율적인 삽입, 삭제, 탐색이 가능하다.

SET은 키와 값이 동일한 <MAP>이라고 생각하면 편하다. 따라서 중복되는 키 값이 없다.

SET은 주로 키가 string이고 string의 사용 유무를 판단하는 문제에서 사용하면 좋을 것 같다.

따라서 알고리즘 문제에서 key가 이름, string으로 사용되야 하는 문제에서 주로 사용하면 좋다.

 

중요 기능

1. s.begin();

- 맨 첫번째 원소를 가리키는 반복자를 리턴한다.

- ex) iter = s.begin();

 

2. s.end();

-맨 마지막 원소를 가리키는 반복자를 리턴한다.

- ex) iter = s.end();

 

3. s.empty();

- set이 비어있는 상태인지 확인한다. (bool)

 

4. s.insert(x);

- 원소 x를 삽입한다.

- O(log n)

 

5. s.erase(iter);

- iter가 가리키는 원소를 제거한다.

- 제거 한 다음 제거 한 원소 다음 원소를 가리키는 반복자를 리턴한다.

- 값이 아닌 iter를 파라미터로 사용하기 때문에, s.find()와 함께 사용한다.

- O(log n)

 

6. s.find(x);

- 원소 x를 가리키는 반복자를 반환한다.

- 원소 x가 없다면 s.end()와 같은 반복자를 반환한다.

- 이를 이용하여 if(s.find(x) == s.end())를 통해 s에 x가 없는 경우로 나타낼 수 있다.

- O(log n)

 

7. s.size();

- set의 크기를 반환한다.

- 이를 통해 set안에 있는 원소의 갯수를 알 수 있다.