[Algorithm/c++] STL: Map, Hash_Map 알아보기

Map, Hash_Map 톺아보기

1.1 시퀀스 컨테이너와 연관 컨테이너

STL 컨테이너는 크게 시퀀스 컨테이너와 연관 컨테이너로 나눈다.

시퀀스 컨테이너는 vector, list, deque와 같이 순서 있게 자료를 보관한다.

연관 컨테이너는 어떠한 Key와 짝을 이루어 자료를 보관한다. 그래서 자료를 넣거나 빼고 찾을 때는 Key가 필요하다.

 

1.2 연관 컨테이너

연관 컨테이너로 map, set, hash_map, hash_set이 있다. 이것들은 Key로 사용하는 값이 중복되지 않은 때 사용한다.

만약 중복되는 key를 사용할 때는 컨테이너 앞에 "multi"를 붙인 multi_map, multi_set, hash_multimap, hash_multiset을 사용한다. 

 

1.2.1. map, set과 hash_map, hash_set의 차이

map과 set 컨테이너는 자료를 정렬하여 저장한다. 그래서 반복자로 저장된 데이터를 순회할 때 순서로 순회하지 않고 정렬된 순서로 순회한다. 그에 반해 hash_map, hash_set은 정렬하지 않고 자료를 저장한다. 또 hash라는 자료구조를 사용함으로 원소를 빠르게 검색한다.

 

1.3 Hash_map의 주요 멤버들

멤버	설명
begin	첫 번째 원소의 랜덤 접근 반복자를 반환
clear	저장한 모든 원소를 삭제
empty	저장한 요소가 없으면 true 반환
end	마지막 원소 다음의(미 사용 영역) 반복자를 반환
erase	특정 위치의 원소나 지정 범위의 원소들을 삭제
find	Key와 연관된 원소의 반복자 반환
insert	원소 추가
lower_bound	지정한 Key의 요소가 있다면 해당 위치의 반복자를 반환
rbegin	역방향으로 첫 번째 원소의 반복자를 반환
rend	역방향으로 마지막 원소 다음의 반복자를 반환
size	원소의 개수를 반환
upper_bound	지정한 Key 요소가 있다면 해당 위치 다음 위치의 반복자 반환

 

2.1. Map의 자료구조와 사용

map의 자료구조는 '트리(tree)'이다. 

map은 많은 자료를 정렬하여 저장하고 있고, 빠른 검색을 필요로 할 때 자주 사용한다.

앞서 말했듯이 map은 자료를 저장할 때 내부에서 자동으로 정렬하고 hash_map은 정렬하지 않는다.

 

2.2. Map 사용방법

보통 map을 사용하는 방법은 아래와 같습니다.

map< key 자료 type, value 자료 type > 변수 이름

Map의 기본 정렬방식은 오름차순이다. 만약 다른 방식으로 정렬하고 싶으면 아래와 같이 하면 된다.

map< key 자료 type, value 자료 type, 비교 함수 > 변수 이름

 

2.3. Map의 주요 멤버들

멤버	설명
begin	첫 번째 원소의 랜덤 접근 반복자를 반환
clear	저장하고 있는 모든 원소를 삭제
empty	저장 하고 있는 요소가 없으면 true 반환
End	마지막 원소 다음의(미 사용 영역) 반복자를 반환
erase	특정 위치의 원소나 지정 범위의 원소들을 삭제
Find	key와 연관된 원소의 반복자 반환
insert	원소 추가
lower_bound	지정한 key의 요소를 가지고 있다면 해당 위치의 반복자를 반환
operator[]	지정한 key 값으로 원소 추가 및 접근
rbegin	역방향으로 첫 번째 원소의 반복자를 반환
rend	역방향으로 마지막 원소 다음의 반복자를 반환
size	원소의 개수를 반환
upper_bound	지정한 key 요소를 가지고 있다면 해당 위치 다음 위치의 반복자 반환