Certi Pro 취득을 위해 꼭 알아야 할 STL Container : Unordered Associative

저번 포스팅에서는 STL에 정의된 자료구조 중 Associative Contatiner에 대해 알아보았다.

Associative Container : Certi Pro 취득을 위해 꼭 알아야 할 STL Container : Associative

 

이번 포스팅에서는 Unordered Associative Container에 대해 알아보자.

 

① hash table

해시 테이블은 데이터를 빠르게 검색하기 위한 자료구조로, key와 value로 이루어진 데이터를 저장하는 자료구조이다.

해시 함수는 Key를 받아 해시 테이블(bucket) 내에서 유일한 인덱스를 생성하는 함수이다. 해시 함수는 Key값의 분포를 고르게 만들어야 하는데, 특정 데이터에 대해 동일한 인덱스를 반환한다면, 해시 충돌이 발생한다.

해시 충돌을 해결하기 위한 방식으로는 Open address와 Chaining 기법이 있다.

 

Key에 따라 bucket에 잘 분배되도록 hash function을 만들면, 삽입 / 삭제 / 탐색 모두 O(1)의 시간복잡도를 가지며, Pro 시험에서 특정 데이터를 빠르게 찾을 때 자주 사용된다.

	Average	Worst Case
Space	O(n)	O(n)
Search	O(1)	O(n)
Insert	O(1)	O(n)
Delete	O(1)	O(n)

C++ STL에서 내부적으로 해시 자료구조를 사용하는 라이브러리로는 대표적으로 unordered_set과 unordered_map이 있다.

 

 

② unordered_set

unordered_set은 key만 저장하고 value는 저장하지 않는다. 즉, 중복된 값을 허용하지 않는 집합(set) 자료구조이다.

 

[unordered_set 주요 문법]

unordered_set<T> htab
unordered_set<T, Hash> htab
unordered_set<T, Hash, KeyEqual> htab

iterator htab.begin(), htab.end()
bool htab.empty()
size_type htab.size()
void htab.clear()
size_type htab.count(T x)
iterator htab.find(T x)

pair<iterator, bool> htab.insert(T x) // 등록된 iterator, 성공 여부
void htab.insert(iterator first, iterator last)

iterator htab.erase(iterator pos) // pos의 다음 iterator 반환
iterator htab.erase(iterator first, iterator last)
// 마지막으로 지운 element의 다음 iterator 반환
size_type htab.erase(T x) // 성공 여부 0, 1

 

 

③ unordered_map

unordered_map은 key-value 쌍으로 이루어진 데이터를 저장한다. map과 유사하지만, 해시 함수를 사용하기 때문에 더 빠른 검색 속도를 보인다.

 

[unordered_map 주요 문법]

unordered_map<T> htab
unordered_map<T, Hash> htab
unordered_map<T, Hash, KeyEqual> htab

iterator htab.begin(), htab.end()

U htab[T x] // x가 등록되지 않은 상황이면 default 값(0)으로 등록

bool htab.empty()
size_type htab.size()
void htab.clear()
size_type htab.count(T x)
iterator htab.find(T x)
void htab.reserve(int n)

pair<iterator, bool> htab.insert({T Key, U value})
void htab.insert(iterator first, iterator last)

iterator htab.erase(iterator pos)
iterator htab.erase(iterator first, iterator last)
size_type htab.erase(T x)

 

pro 시험에서 unordered_map은 굉장히 많이 사용된다. 사용되는 상황과, 사용하는 방식은 별도의 포스팅에서 다뤄보자.

 

 

※ set vs map vs unordered_set vs unordered_map

set	unordered_set	- key
map	unordered_map	- key-value 쌍 존재 - operator[] 제공 - [] 접근 시, default 값(0)으로 자동 삽입
- Red-Black Tree로 구현된다. - 탐색 O(logn) - Compare 함수 사용 - 우선순위 값 / 정렬된 정보 필요할 때 유용	- Hash Table로 구현된다. - 탐색 O(1 + a) - Hash, KeyEqual 함수 사용 - 일치하는 정보 검색에 특화	[공통] - 오로지 key 값 기준으로 검색 - key 값 변경 불가, 필요 시 삭제 후 삽입