[STL] Map 맵

Map 맵

각 노드가 key와 value의 쌍으로 이루어진 red-black tree이다.

key를 기준으로 정렬된 상태이기 때문에 검색, 삽입, 삭제 등의 속도가 빠르다.

주의할 점은 key가 중복이면 새로 추가하는 value값으로 덮어쓰기가 된다.

만약, key값 중복을 원하면 map말고 multimap을 사용한다.

#include <map>

map<key,value>처럼 key, value의 pair로 선언

map<int,int> m : key와 value 자료형이 int인 map m 선언

m.size() : 노드 개수 리턴

m.begin() : 첫 번째 원소 iterator

m.end() : 마지막 원소 iterator

m.find(a) : key가 a인 노드 찾아 해당 iterator 리턴, 만약 존재하지 않으면 마지막 iterator 리턴

m.insert(make_pair(a,b)) : a key의 b value 삽입

m.erase(a) : key가 a인 원소 삭제

m.clear() : 모든 원소 삭제

m.count(a) : key가 a인 원소들 개수 리턴

ex) unsorted 배열과 sorted 배열을 비교하여 sorting count 계산 코드

   vector <int> unsorted_arr = { 4,3,1,2 };

vector <int> sorted_arr(unsorted_arr);

sort(sorted_arr.begin(), sorted_arr.end());

map<int, int> m;

for (int i = 0; i < arr.size(); i++) m[arr[i]] = i;

int ans = 0;

for (int i = 0; i<unsorted_arr.size(); i++) {

if (unsorted_arr[i] != sorted_arr[i]) {

int tmp = m[sorted_arr[i]]; swap(unsorted_arr[tmp], unsorted_arr[i]);

m[unsorted_arr[tmp]] = tmp; ans++;

}

}

cout << ans;

작성자 : 히더