[ 코테 꿀팁 ] set, unordered_set (C++)

set과 unordered_set은 코테 보면서 사용할 일이 그닥 많지 않다. 근데 모르면 못 써먹기 때문에 간단한 특징과 함수들을 정리해봤다. 

 

1. 특징

1) Set
- 균형 이진탐색트리 구조
- 탐색, 삽입, 삭제 모두 O(logN) 보장
- 정렬된 상태
- 값 중복 X

2) Unordered_set
- 해시테이블 구조
- 탐색, 삽입, 삭제 모두 O(1)
- 원소가 너무 많아지면 리헤싱 과정을 거치는데 이는 O(N) 시간 소요
- 정렬되지 않음
- 값 중복 X

 

균형 이진탐색트리가 뭔지, 해시테이블이 뭔지에 대한 설명은 생략하도록 한다. 이 둘의 공통점은 키(key) 값으로 접근한다는 점이다. 따라서 Key의 존재여부만을 판단할때 사용하면 좋다. 

 

2. 함수(둘 다 똑같다)

• 기본 선언 : set<type> s;    unordered_set<type> s;
• s.begin() : 맨 첫번째 원소를 가리키는 반복자 반환
• s.end() : 맨 마지막 원소를 가리키는 반복자 반환
• s.clear() : 모든 원소 제거
• s.count(k) : 원소 k의 개수 (무조건 0 또는 1)
• s.empty() : 비었는지?
• s.insert(k) : k 삽입
• s.find(k) : k를 가리키는 반복자 반환. 존재하지 않으면 s.end() 반환
• s.size() : s의 크기 반환

 

 

글이 너무 짧네.. 나중에 map, unordered_map도 같이 정리해야겠다..