[자료구조] Map

Map

각 노드가 (key, value) 쌍으로 이루어진 트리

• 파이썬의 딕셔너리 타입과 동일한 개념
• key 중복을 허용하지 않음 ❗

📌 사용하려면

#include <map> 
using namespace std;

//key 기준으로 오름차순 정렬(디폴트)
map<string, int> mp;
map<char, int> mp;
map<int, int> mp;

//key 기준으로 내림차순 정렬
map<string, int, greater> mp;

• map<key의 자료형, value의 자료형> mymap; : 디폴트
• map<key의 자료형, value의 자료형, greater> mymap; : key 기준으로 내림차순 정렬

📌 시간복잡도

• 검색, 삽입, 삭제 : 𝑂(𝑙𝑜𝑔𝑁)

📌 장점

• 데이터 검색 속도가 빠르다
• 키에 대한 데이터가 존재하는지 확인하기 쉬움 -> 데이터 중복 검사에 유용!

📌 단점

• 저장공간이 좀더 많이 필요하다

데이터 삽입

• mp.insert({key값, value값});

  ex. mp.insert({"Joe", 3});

• mp[key값] = value값;

데이터 접근

• mp.find(key값) : iterator 반환

• mp.find(key값) -> second : key값에 해당하는 value값 반환
  

• 반복문에서 데이터 접근

for(auto i=mp.begin(); i!=m.end(); i++) {
  cout << i->first << " " << i->second << endl;
  //iterator i는 map의 각 데이터(key,value)를 가리킴
}

for(auto i : mp) {
  cout << i.first << " " << i.second << endl;
}

map에 찾고자 하는 데이터가 있는지 확인

데이터를 찾지 못하면, iterator는 map.end()를 반환

if (mp.find("Alice") != mp.end()) {
	cout << "find" << endl;
}
else {
	cout << "not find" << endl;
}

데이터 삭제

• mp.erase(key값); : key값을 기준으로 삭제

  ex. mp.erase("Joe");

• mp.erase(mp.begin()+2); : 특정 위치의 요소 삭제

• mp.clear(); : 모든 요소 삭제

---

참고
https://life-with-coding.tistory.com/305