맵(Map)

🟩 인덱스로 int가 아닌 다른 자료형을 사용할 수 있는 배열 (편의상)

map의 내부적인 구조는 각 노드가 key와 value의 쌍으로 이루어진 '트리'이다.

특히 검색, 삽입, 삭제 등의 속도를 빠르게 하기 위해 균형 이진 트리 중의 하나인 '레드-블랙 트리'로 구현되어 있다.

검색 속도가 특히 빠른데 이는 key를 기준으로 정렬된 상태이기 때문이다.

 

🟩 연관있는 두 값을 함께 묶어서 관리하되, 검색을 빠르게 하고 싶은 경우

 

🟩 #include <map>

map은 중복 불가한 key와 value 쌍으로 이루어진 노드의 트리라고 할 수 있다.

같은 key 값을 갖는 노드를 추가하면 어떻게 될까? 해당 key  값을 갖고 있던 원래 노드의 value 값에 덮어 씌워지게 된다.

map의 요소에 접근할 때, 반복자(iterator)를 이용하는 방식과 인덱스(key)를 이용한 방식, 두 가지 방식을 이용할 수 있다.

m.size()	m의 노드 개수를 리턴
m.empty()	m의 사이즈가 0인지 아닌지 리턴
m.begin()	m의 첫 번째 원소를  가리키는 iterator 리턴
m.end()	m의 마지막 원소를가리키는 iterator 리턴
m[k] = v	m에 key가 k이고, value가 v인 노드 추가
m.insert(make_pair(k,v))
m.erase(k)	m에서 key가 k인 노드 삭제
m.find(k)	m에서 key가 k인 노드를 찾아, 해당 노드를 가리키는 iterator 리턴 (key가 k인 노드가 존재하지 않는 경우, m의 마지막 원소를 가리키는 iterator 리턴)
m.count(k)	m에서 key가 k인 노드의 개수를 리턴

 

cf. insert와 erase 함수의 경우, 파라미터로 값 자체가 아닌 iterator를 넘겨주는 방식을 사용할 수 있다.

iterator를 넘겨주는 방식을 통해, 배열이나 벡터에 있는 모든 값을 추가하거나, map의 첫 번째 원소나 마지막 원소를 삭제할 수도 있다.

 

EX1) vector의 v에 있는 모든 값 추가 👉 m.insert(v.begin(), v.end())

EX2) map의 첫 번째 원소 삭제 👉 m.erase(m.begin())

 

map은 다른 컨테이너에 비해, iterator의 사용이 잦은 컨테이너이다.

map<char, int> m;
map<char, int>::iterator it;

m['B'] = 2;                   // m : (B,2)
m.insert(make_pair('A',1));   // m : (A,1) (B,2)
m['C'] = 3;                   // m : (A,1) (B,2) (C,3)

m.erase('A');                 // m : (B,2) (C,3)

// m 전체를 순회하며 key와 value 출력
for(it= m.begin(); it != m.end(); it++){
	cout << it->first << ' ' << it->second << '\n';
}

if(m.find('B') != m.end())
	cout << "key값이 B인 노드가 존재합니다." << '\n';
else
	cout << "key값이 B인 노드가 존재하지 않습니다." << '\n';