[C++] Container - Map

List에 이어 이번에 알아볼 Container는 Map이다.

 

Map의 자료구조는 Red Black Tree이다.

 

이는 자가 균형 이진트리로써, 삽입과 삭제가 일어나는 경우 자동으로 그 높이를 작게 유지해주는 이진트리이다.

 

꽤나 어려운 내용이므로, 코드를 직접 구현하기 보다는 STL Library를 살펴보는 것이 나을 것 같다.

 

먼저 map의 기본 형태는 다음과 같다.

map<Key, Value> : Key-Value Type > Key와 Value가 쌍으로 저장되는 형태를 띄며, Key값을 이용하여 Value값을 찾을 수 있다.

이런 형태를 사실 파이썬에서는 Dictionary라는 자료형으로 사용하고 있다. 

 

Map 사용 예

Map은 다음과 같이 사용한다. key의 자료형을 string, value의 자료형을 int로 놓고 사용한 예이다. insert(make_pair())이런식으로 원소를 삽입할 수도 있고, p[Key] = Value 이런식으로 원소를 삽입할 수도 있다. 그리고 Key를 이용하여 접근, 삭제가 가능하다는 것을 알 수 있다. Insert함수를 사용 할 때, 동일한 키로 Value를 여러번 삽입할 경우, 뒤에 삽입한 값의 경우 존재하지 않는다. 처음 삽입한 Key의 Value가 계속해서 남게 된다. 바꾸고 싶을 경우, p[Key] = Value와 같은 방식을 사용하면 된다.

중복 삽입

대입

 

Map의 경우 구현이 상당히 복잡하고 어렵기 때문에 개념 원리에 대해서는 레드블랙트리를 따로 공부하면 좋을 것 같다.

그러한 이유로 다음 시간에는 레드 블랙 트리를 한번 보고 가도록 하려고 한다.

 

-- 중요!

Map에 데이터를 삽입하면 정렬이 되어 들어가게 된다. 그러므로, 만약 본인이 사용하고 싶은 자료구조가 Key - Value 자료구조이면서, 정렬을 안했으면 좋겠다 싶으면, unordered_map을 사용하여야 한다. 또한, 중복을 허용하지 않는다. 이 점에 유의하여 코드를 작성해야 한다.