[C++] STL에서의 unordered_map사용법과 map과의 차이점, unordered_set 사용법

해시테이블이란?

C++에서 표준 라이브러리로 해시테이블을 지원한다. 해시 테이블은 key-value 형태의 데이터를 빠른 시간복잡도를 보장하는 삽입, 삭제 및 검색 작업을 위한 자료 구조이다. 해시 함수를 사용하여 배열의 인덱스에 키를 매핑하여 작동한다. 배열의 각 인덱스는 동일한 키가 한 인덱스에 매핑되는 충돌을 해결하기 위한 메커니즘을 보유한다.

해시테이블의 자세한 개념이 궁금하다면?

해시테이블을 C++로 직접 구현해보고 싶다면?

---

unordered_map 선언과 주요 메서드

C++에서는 unordered_map으로 이를 지원하는데, 평균적으로 상수 시간에 원소를 삽입/삭제/검색이 가능하다. 보통 키를 기반으로 원소에 대한 빠른 탐색이 필요한 경우 사용한다. 

 

key(string) : value(int) 형태의 데이터를 사용하는 해시테이블을 만들어보자!

unordered_map<string, int> table;

간단하게 주요 메서드들을 보고, 예제로 다시 보자.

table[key] = value : key를 해싱하여 table에 삽입한다.

table.erase(key) : table에서 key값을 삭제한다.

 

table.find(key) : table에서 key값을 찾으면 해당 원소의 이터레이터를 반환하고, 찾지 못하면 table.end()를 반환한다.

table.end() : table의 끝을 나타내는 이터레이터를 반환한다. 이 이터레이터는 유효하지 않은 위치를 나타낸다.

---

key, value 모두 pair 형태로 여러 쌍을 저장할 수 있다.

원소의 삽입과 삭제도 간단하다.

table["one"] = 1;
table["two"] = 2;

table.erase("two");

table["one"]을 실행하면서 자동으로 one에 해싱이 이루어지면서 삽입된다. 

 

원소의 탐색과 테이블 순회를 보자.

int main(){
	
    cout << "Value of key 'two' : "<< table["two"];

    if(table.find("four") != table.end()) cout << "'four' does not exist.";
    else cout << "'four' exists.";

    for(auto pair : table)
        cout << pair.first << " : " << pair.second << "\n";

    unordered_map<string, int>::iterator it;
    for(it = table.begin(); it != table.end(); it++)
        cout << it->first << " : " << it->second << "\n";
    }

---

unordered_map과 map의 차이점

1. unordered_map

• 해시 테이블로 구현되어 평균적으로 빠른 삽입, 삭제 및 검색을 제공한다.
• 원소의 순서가 삽입 순서와는 무관하다.
• 원소에 빠른 접근이 많이 일어나고 원소에 대한 정렬이 필요하지 않을 때 사용한다.
• 중복 키를 허용하지 않는다.

2. map

• 레드-블랙 트리같은 균형 이진 검색 트리로 구현되어 원소가 키에 따라 정렬된다.
• 원소에 대한 빠른 접근과 정렬된 원소가 필요할 때 사용한다.
• 중복 키를 허용하지 않는다.

만약 중복 키가 필요하다면 multimap이나 unordered_multimap을 사용하면 된다.

---

unordered_set

unordered_set은 해시테이블 기반의 자료구조이다. unordered_map과 거의 똑같은 역할을 하지만 key-value 형태의 데이터가 아닌, key만 가지고 데이터를 관리할 때 사용한다.