Set / Map
- Set : 값을 저장할 수 있는 컨테이너
- Map : 키, 값을 저장할 수 있는 컨테이너
Red-Black Tree를 사용해 키의 순서를 유지
탐색속도 : O(logN)
언제 사용하는 가?(Set기준이지만 Map도 비슷하다고 생각)
- 정렬된 데이터가 필요할 때
- (정렬된 순서로) 데이터를 출력/접근을 해야할 때
- element의 앞/뒤(pre/next or prodecessor/successor)가 필요할 때
- 정렬된 셋으로부터 element에 binary_search(), lower_bound() and upper_bound()같은 함수들을 사용해야할 때
- 이 함수들은 unordered_set()을 지원하지 않음
- BST가 Hash table보다 더 좋을 때
- hashing보다 BST가 커스터마이징이 쉽다.
- hashing을 일반적으로 프로그래밍 언어에서 제공하는 라이브러리에 의존한다.
- BST는 모든 operation이 O(log(n))시간내에 작동하도록 보장된다. 그러나 Hashing의 경우, O(1)은 평균 시간이며, 특히 테이블 크기가 조정될 때 일부 특정 작업을 비용이 많이 들 수 있다.
- hashing보다 BST가 커스터마이징이 쉽다.
unordered Set / Map
hash table을 사용해 키의 순서를 유지하지 않는다.
키의 순서를 유지할 필요가 없기 때문에 탐색 속도등에 유리한 점을 가진다.
삽입된 순서가 아닌 랜덤순으로 데이터가 저장된다.
탐색속도 : O(1)
언제 사용하는 가?(Set기준이지만 Map도 비슷하다고 생각)
- 정렬되지않고 구분된 요소들을 유지할 때
- 순회 없이 하나의 요소에 대한 접근이 필요할 때
Key의 종류에 따른 탐색속도 비교(Map 기준)
환경 : Intel i7-3550 3.3GHz, Windows 7 SP1, VC++ 10 SP1
x 축 : 데이터 크기 N
y 축 : 탐색 1회에 걸린 시간(µs)
| int형 key | const char*형 key - hash함수로 sdbm hash 함수 사용 |
 |
    |
| map : O(logN) unordered_map : O(1), N이 32부터 유리 unordered_map(bypass) : unordered_map에 비해 2배 빠름, N이 6부터 유리
|
M(문자열 길이)의 크기가 커질수록 map과 unordered_map의 성능이 교차하는 점이 같이 커진다. -> M이 커질수록 map이 유리한 N의 범위가 커진다.
|
차이 정리
| set | unordered_set
---------------------------------------------------------
Ordering | increasing order | no ordering
| (by default) |
Implementation | Self balancing BST | Hash Table
| like Red-Black Tree |
search time | log(n) | O(1) -> Average
| | O(n) -> Worst Case
Insertion time | log(n) + Rebalance | Same as search
Deletion time | log(n) + Rebalance | Same as search
참조 사이트