[자료구조][C++] Map

Map이란 ?

Key와 Value로 이루어진 자료구조로 Key와 Value가 하나의 쌍으로 연결되어 Key를 통해 Value에 접근할 수 있도록 만들어졌습니다.

Map의 특징

Key의 중복을 허용하지 않아야 한다.
순서가 유지되지 않는다.
Value의 중복은 허용된다.

Map의 종류

HashMap
- 중복을 허용하지 않는다.
- 순서를 보장하지 않는다.
TreeMap
- 이진검색트리의 형태로 Key와 Value의 쌍으로 이루어진 데이터를 저장한다.
- 순서를 보장하며 저장하므로 빠른 검색이 가능하다.
- 저장할 때 정렬을 하기 때문에 시간이 오래 걸린다.
LinkedHashMap
- 데이터 입력한 순서대로 쌓아 저장한다.
- 배열, 리스트처럼 인덱스 접근에 용이하다.

Map 기본 형태

map <key, value> m;

Map 사용방법

1. Map 선언

map<string, int> m;

2. Map 데이터 삽입

m.insert({"0inn", 1});

map<int, int> m; 인 경우, 아래 형태의 선언도 가능

m[1] = 1;

3. Map 탐색 (search)

Map 탐색에서는 iterator를 사용하기 때문에 데이터를 끝까지 찾지 못했을 경우에는 m.end()를 반환합니다.

if(m.find("0inn") != m.end()) {
	cout << "찾았다" << endl; 
} else {
	cout << "못찾았다" << endl;
}

4. Map 삭제

1) erase : key값 기준으로 요소 삭제

m.erase("0inn");

2) clear : 모든 요소 삭제

m.clear();

5. 데이터 접근

for(auto iter:m) {
	cout << iter -> first << " " << iter -> second << endl;
}

+ value 기준으로 정렬

typedef pair<int, int> ii;

vector<ii> v(m.begin(), m.end());
sort(v.begin(), v.end(), [](ii a, ii b) {
	// 원하는 정렬 기준 작성
	if (a.second == b.second) {
		return a.first < b.first;
	} else {
		return a.second < b.second;
	}
});