다시 정리하는 C++ STL 자료구조 unordered_map/set

 

 

[ STL 자료구조 unordered_map/set ]

 

unordered 컨테이너 메모리 구조

unordered_map과 unordered_set은 이름 그대로 순서가 없다.

key값과 value값이 연관은 있지만, 순서가 없다?

이 말은 각 key 값마다 해시 번호표가 있어서 원하는 데이터를 즉각 찾을 수 있다는 말이다.

즉, STL unordered 컨테이너는 해시(hash) 자료구조이다.

프로그래밍에서 사용하는 메모리와 성능은 반비례 한다.

STL unordered 컨테이너는 빠른 성능을 위해 많은 메모리를 필요로하는 단점이 있다.

(내부적으로 vector와 list를 같이 쓰기 때문에 많은 메모리가 필요)

 

int 자료형의 해시 테이블 번호

데이터를 담을 때 hash함수를 거쳐서 번호표를 받는다.

해시값을 미리 내부에 vector로 만들어 놓는다. (버킷을 만들어 놓는다.)

버킷 번호와 해시 값을 매칭 시켜서 데이터를 찾는다.

이러한 구조는 시간상의 이득을 얻기위해 사용한다. 내가 찾는 원소를 빠르게 찾기 위해서이다.

해시 번호표를 통해 바로바로 데이터를 찾을 수 있다.

이 구조보다 빠르게 찾을 수 있는 구조는 존재하지 않는다.

STL unordered 컨테이너에서 데이터를 찾는데 걸리는 시간은 O(1)이다.

 

 

[ unordered_set의 메모리 모양 ]

unordered_set의 메모리 모양

데이터 값과 매칭 되는 해시 테이블 값에 데이터가 들어가 있는 모습을 확인할 수 있다.

 

[ unordered_multiset의 메모리 모양 ]

unordered_multiset 메모리 모양

STL unordered_multimap/set은 중복 값을 담을 수 있어서 위와 같은 메모리 모양이 나온다.

 

 

 

[ 사용자 정의 자료형을 unordered 컨테이너에 넣기 ]

 

우리가 직접 정의한 자료형(struct, class)을 unordered 컨테이너에 담기 위해서는?

해시 번호표를 만들 수 있어야 한다.

즉, hash <> 함수를 거칠 수 있어야 한다.

Test 클래스

사용자 정의 자료형을 unordered 컨테이너에 넣기 위해 임의로 만든 클래스이다.

우리가 만든 자료형이 hash<> 함수를 거치기 위해서는

==와 () 연산자가 const로 오버 로딩돼있어야 한다.

 

hash 특수화

그런 다음 hash <> 템플릿에 대해서 특수화해주면 된다.

 

데이터 출력

마지막으로 unordered_set에 클래스 데이터를 넣고 데이터가 잘 들어갔는지 확인해주면 된다.