1. map
- map은 내부적으로 균형이진트리 구조로 구성됨
- 각 노드에 <key, value> 쌍을 저장
- 중복 key를 허용하지 않음
- key가 자동으로 정렬됨 (key가 비교 연산 가능해야 함)
- 탐색, 삽입, 삭제에 O(log n) 소요
2. unordered_map (hash map)
- unordered_map은 해시 테이블 기반의 구조
- map과 마찬가지로 <key, value> 쌍을 저장함
- 하지만 key를 정렬하는 것이 아닌 해시 함수를 통한 해시값을 기반으로 저장
- 동일한 해시값을 가지는 경우(충돌)을 처리할 방법이 필요함
(ex. 2차해시함수, 체이닝)
- 탐색, 삽입, 삭제는 평균 O(1), 최악의 경우 O(n)소요
3. 활용
헤더 & 선언
#include <map>
#include <unordered_map>
map<string, int> m;
unordered_map<string, int> um;
데이터 삽입
m.insert({"Tom", 100});
um.insert({"Alice", 300});
m["Tom"] = 100;
um["Alice"] = 300;
데이터 찾기
auto it = m.find(key);
// key가 존재하면 해당 iterator 반환. 없으면 m.end() 반환
데이터 접근 (범위 기반 for문)
for (auto& it : m) {
cout << "key: " << it.first << " value: " << it.second << endl;
}
데이터 삭제
- 특정 위치 삭제 (iterator)
m.erase(m.begin()+1);
- key값으로 삭제
m.erase(key);
- 모든 요소 삭제
m.erase(m.begin(), m.end()); // 범위 삭제
m.clear(); // 전체 삭제
비어있는지 확인
m.empty(); // 비어있으면 true 반환. 아니면 false
