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

 

 

 

[ STL 자료구조 map / set ]

 

STL array, vector, list가 연속 컨테이너(Sequential Container)였다면

map과 set은 연관 컨테이너(Associative Container)이다.

연관이라는 말은 저장하려고 하는 자료와 key값이 서로 관련이 있다는 의미이다.

 

map은 pair<key, value>를 원소로 저장하는데, key를 기준으로 데이터를 정렬한다.

set은 key를 기준으로 원소를 정렬 상태로 저장하지만, value가 따로 있지 않다.

즉, set은 key와 value가 같은 데이터를 원소로 저장한다.

연관 컨테이너는 찾고자 하는 원소를 빨리 찾기 위해 사용한다.

여기서 빠르다는 것은 연속 컨테이너보다 빠르다는 의미이다.

연관 컨테이너에서 원소를 찾는 데 걸리는 시간 복잡도는 n * log2(n) 이다.

 

연속 컨테이너에서는 원소를 삽입하는데 O(1)의 시간이 소요되는 반면

연관 컨테이너는 원소를 삽입하는데 기본 로그 시간 복잡도를 갖는다.

따라서 연관 컨테이너는 원소가 항상 정렬된 상태가 되도록 하는 데 시간을 더 써서,

찾는데 드는 시간을 단축하는 것이다.

 

 

 

[ map ]

STL map

숫자가 key값이고, 문자가 value이다.

STL map은 이진 탐색 트리의 일종인 red-black 트리로 구성되어있다.

map의 key는 유일(unique) 해야 한다. 즉, 중복된 key값을 사용할 수 없다.

같은 key값을 갖는 원소를 저장하고 싶다면 multimap을 사용하면 된다.

map은 key를 이용해 다른 자료형인 value를 빠르게 검색할 수 있는 연관 컨테이너이다.

 

 

 

map의 원소는 pair<key, value>이므로

항상 pair 객체를 만들어서 원소를 추가한다는 것을 주의하면 된다.

원소를 추가하거나 삭제할 때는 key값을 기준으로 한다.

map 원소 추가

map에 원소를 삽입하는 방법은 5가지가 있다.

1. pair<key, value> 임시 객체 생성을 통한 원소 삽입 방법.

2. pair<key, value>를 만들어주는 make_pair 함수 사용 방법.

3. make_pair로 pair<key, value>를 만들어서 이를 직접 삽입하는 방법

4. emplace 내부에서 pair<key, value>를 직접 생성하여 삽입하는 방법.

5. insert_or_assign을 통한 key가 없는 경우에만 삽입하는 방법.

map의 원소를 참조할 때 first는 key값, second는 value값을 나타낸다.

 

map 원소 삭제

map의 멤버 함수 erase()를 통해 원소를 삭제할 수 있다.

key값을 통해 삭제가 가능하다.

 

 

 

[]을 통한 value 참조

map은 [] 연산자를 통해 value값을 참조할 수 있어서 연관 배열이라고도 부른다.

배열과 같이 map은 key값을 index로 사용하여 value에 액세스 할 수 있다.

다른 점은 메모리가 연속되어 있지 않다는 것이다.

그리고 map에서는 어떤 자료형이라도 key값으로 사용할 수 있다는 점이다.

 

 

 

[ set ]

set

map과 set의 기능적인 부분은 크게 다른 것이 없다.

set은 key를 정렬 기준으로 사용하며 이것을 그대로 저장한다.

key와 value가 같은 map이라고 생각하면 문제가 없다.

멤버 함수도 map과 거의 동일하다.

 

set은 원소를 항상 정렬 상태로 저장하는 컨테이너라고 이해하면 된다.

set<int>는 모든 int를 less<int>로 비교하여 저장할 것이다.