unordered_set/multiset

[unordered_set]

 

1. 중복허용 X

2. 정렬 X

3. hash 사용

4. insert, erase, find 모두 O(1)

 

그냥 set은 노드기반-이진탐색트리로 구현되어있지만

unordered_set은 hash-table 기반으로 되어 있다.

 

unordered_set 의 가장 큰 장점은 탐색시간이 O(1) 이라는 것

set은 이진탐색트리로 구성되어 있어 탐색 시간복잡도가 O(logN) 이지만 

unordered_set은 O(1) 상수함수 시간복잡도를 가지고 있음

 

unordered_set<int> set;

set.insert(5);
set.erase(10);

if(set.find(7)!=set.end()) cout << 1;
else cout << 0;

 

---

[multiset]

 

원래 set은 중복된 key를 허용하지 않지만

multiset은 중복된 key를 허용한다!