Map

• 각 노드가 Key와 Value 쌍으로 이루어진 트리
• 중복을 허용하지 않음
• Pair 객체 형태로 저장
• 검색, 삽입, 삭제 시간 복잡도 : O(logN)
• 원소 삽입시 Key를 기준으로 오른차순 정렬이 Default

1. 생성

• 헤더 파일
  #include <map>

• 생성
  map<key,value>

  ex) map<string, int> m;

• 내림차 순으로 정렬되는 Map 생성

  ex) map<string, int, greater<string>> m

2. 멤버 함수

종류	상세설명
begin()	맨 시작 iterator를 반환
end()	맨 끝 iterator를 반환
insert( make_pair(key,value) )	맵에 원소를 pair 형태로 추가
erase(key)	key(키값)에 해당하는 원소 삭제
clear()	원소들 모두 삭제
find(key)	key(키값)에 해당하는 iterator를 반환
count(key)	key(키값)에 해당하는 원소들(value들)의 개수를 반환
empty()	비어있으면 true 아니면 false를 반환
size()	사이즈 반환
lower_bound(key)	비교 결과 주어진 값보다 먼저 나오지 않는 첫 원소의 iterator를 반환
upper_bound(key)	비교 결과 주어진 값보다 나중에 나오는 첫 원소 iterator를 반환

find()로 데이터를 찾지 못했을 경우, map.end() 반환

3. 예시

#include <iostream>
#include <map>
#include <string>
using namespace std;

void main() {
	map<string, int> m;

	m.insert(make_pair("a", 1));
	m.insert(make_pair("b", 2));
	m.insert(make_pair("c", 3));
	m.insert(make_pair("d", 4));
	m["e"] = 5;

	cout << m.size() << endl; // 5
	cout << m.count("a") << endl; // 1

	for (auto iter : m) {
		cout << iter.first << " " << iter.second << endl;
	}
	
	/*
		a, 1
		b, 2
		c, 3
		d, 4
		e, 5
	*/

	m.erase("a");
	m.erase("b");
	m.erase(m.find("d"));

	for (auto iter = m.begin(); iter != m.end(); iter++) {
		cout << iter->first << " " << iter->second << endl;
	}

	/*
		c, 3
		e, 5
	*/

	m.clear();
	cout << m.empty() << endl; // 1(true)
}

참고

• https://life-with-coding.tistory.com/305
• https://twpower.github.io/91-how-to-use-map-in-cpp