map, unordered_map

C++ STL에서의 hash table에는 map, unordered_map이 있다.

차이점

STL	key에 의한 접근 시간	라이브러리 내부 구현
map	O(logN)	(주로) binary search tree
unordered_map	O(1)	hash table

※ map에서는 key에 따른 정렬을 계속 유지해야 하기 때문에 원소의 삽입, 삭제, 검색에서 hash table이 가지고 있는 상수 시간 접근이 불가능하고 log에 비례하게 된다.

사용법

map과 unordered_map의 차이점은 위에 적어두었고, 이를 제외하고 사용하는 방법은 동일하기 때문에 사용법과 예시들은 unordered_map을 기준으로 작성하겠다!

생성

• #include <unordered_map>
• unordered_map<key, value> 이름

입력 및 삭제

• 입력
  m[key] = value
  ※ 각 key에 대한 default value는 map이 되는 객체의 타입의 기본 값을 따르게 된다. <string, int>라면 int 형의 기본 값인 0이 되며 만약 <string, string>일 경우, 비어있는 문자열이 기본이 된다.
  ※ 만약 이미 key값이 존재하는 원소의 값을 바꾸고 싶다면 그냥 덮어 써주면 된다.
  m.insert(make_pair(key, value))

• 삭제
  m.erase(key) -> 맵에서 키값에 해당하는 원소 삭제
  m.clear() -> 모든 원소들을 삭제한다.

순회

• for(auto& i : m)
  ※ i는 unordered_map에 대한 iterator의 reference이다.
  C++ STL에서 unordered_map에 대한 iterator는 pair이다.
  그래서 i.first, i.second를 활용해서 우리가 원하는 값을 순회하여 볼 수 있다.
• for(auto i = m.begin() ; i != m.end() ; i++)
  ※ 여기서는 i->first, i->second를 통해 값을 확인한다.

검색

• m.find(key) -> key에 해당하는 iterator을 반환
  ※ 만약 key가 없다면 m.end() (end iterator)을 반환한다.
• m.count(key) -> key에 해당하는 value의 개수를 반환
  ※ 보통 문제를 풀 때 개수보다는 key가 존재하는지 확인하는데 사용한다.
  key가 존재한다면 1 (true)를 return하고, 존재하지 않는다면 0 (false)를 return한다.

기타

• m.empty() -> 비어있으면 true, 그렇지 않다면 false를 반환
• m.size() -> map의 크기를 반환

예시

#include <iostream>
#include <unordered_map>
using namespace std;

int main(){
    unordered_map <string, int> m;
    m["a"] = 1;
    m["a"] = 2;
    m["b"] = 3;
    m["c"] = 4;
    m["d"] = 5;
    m["e"] = 6;
    
    for(auto& i : m) cout << i.first << " " << i.second << " | ";
    cout << endl;
    // e 6 | d 5 | b 3 | c 4 | a 2 | 
    
    m.erase("a");
    
    if(m.find("a") == m.end()) cout << "a is erased!" << endl; 
    // a is erased!
    
    cout << m.count("b") << endl; // 1(true)
    cout << m.count("a") << endl; // 0(false)
    cout << m.size() << endl; // 4
    cout << m.empty() << endl; // 0(false)
}