[C++] unordered_map

unordered_map

 

특징

• map보다 더 빠른 탐색을 하기 위한 컨테이너
• 해시 테이블(Hash Table)을 기반으로 구현되었다.
• 삽입, 삭제, 탐색에 대해서 $O(1)$ 정도의 시간 복잡도를 가진다. 
  • 가장 최악의 경우 $O(N)$ 정도의 시간 복잡도를 가진다.
  • map의 삽입, 삭제 탐색 시간 복잡도는 $O(\log n)$ 이다.
• 중복된 데이터를 허용하지 않는다.
• map에 비해 데이터가 많을 경우 월등히 좋은 성능을 보인다.
• 하지만, 키(Key)가 유사한 데이터가 많을 경우, 해시 충돌로 인해 성능이 떨어질 수도 있다.

 

unordered_map의 구조

 

헤더 파일

• unordered_map을 사용하려면 다음의 헤더 파일을 불러와야 한다.

#include <unordered_map>

 

멤버 함수

 

사용 방법

• 요소가 삽입될 때 키(Key)가 정렬되지 않는다는 것을 빼고는 map과 사용 방법이 비슷하다.
• 바로가기 : https://dev-astra.tistory.com/244

[C++] 맵(Map)

 

객체 생성

• 다음과 같이 객체를 생성한다.
• 생성된 객체의 요소는 map과 다르게 정렬되어 있지 않다.

unordered_map<[data_type_1], [data_type_2]> [name]

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

unordered_map<int, string> um {
    { 1, "Kim" },
    { 2, "Park" },
    { 3, "Choi" },
    { 4, "Yun" },
    { 7, "Yang" },
    { 6, "Bang" }
};

int main() {
    for (const auto& [key, value] : um) {
        cout << key << " : " << value << endl;
    }
    
    return 0;
}

6 : Bang
7 : Yang
4 : Yun
3 : Choi
2 : Park
1 : Kim

 

사용 시 주의사항

• 얼핏 보면 정렬이 필요하지 않은 문제에는 unordered_map을 써야 할 것 같지만, 제출해보면 시간 초과가 나기도 한다. 가장 최악의 경우의 시간 복잡도가$O(N)$이기 때문이다.
• 따라서 코딩 테스트에서 되도록 map을 사용하는 것이 권장된다.

 

사용 예

#include <iostream>
#include <unordered_map>

using namespace std;

// [1] 객체 생성 및 초기화
//// 객체만 생성
unordered_map<int, string> m1;

//// 객체 생성과 동시에 초기화
unordered_map<int, string> m2 {
    { 1, "Lim" },                   // 방법 1
    pair<int, string>(2, "Kuk"),    // 방법 2
    make_pair(3, "Yun")             // 방법 3
};

int main() {
    // [2] 요소 삽입
    m1.insert(pair<int, string>(40, "Me"));   // 방법 1
    m1.insert({ 20, "Lee" });                 // 방법 2
    m1.insert(make_pair(10, "Choi"));         // 방법 3
    m1.emplace(35, "Park");                   // 방법 4
    m1[65] = "Kim";                           // 방법 5
    
    // [3] 요소 접근
    //// 방법 1
    for (auto i = m1.begin(); i != m1.end(); i++) {
        cout << "(" << i->first << ", " << (*i).second << ")" << '\n';    // 2가지 방법으로 요소에 접근 가능
    }
    
    cout << endl;
    
    //// 방법 2
    for (auto i : m2) {
        cout << "(" << i.first << ", " << i.second << ")" << '\n';
    }
    
    cout << endl;
    
    // [4] 요소 찾기
    auto search1 = m1.find(70);    // 찾기 실패
    auto search2 = m1.find(20);    // 찾기 성공
    
    if (search1 != m1.end()) {
        cout << "Key : " << search1->first << ", Value : " << (*search1).second << '\n';
    }
    else {
        cout << "Not Found." << '\n';
    }
    
    if (search2 != m1.end()) {
        cout << "Key : " << search2->first << ", Value : " << (*search2).second << '\n';
    }
    else {
        cout << "Not Found." << '\n';
    }
    
    //// 해당 키가 맵에 있는지 확인하기
    cout << m1.count(22) << " " << m2.count(20) << '\n';
    
    // [5] 요소 수정
    unordered_map<string, int> m3 {
        { "Queen", 2 },
        { "Prince", 3 },
        { "Princess", 4 }
    };
    
    m3["Pince"] = 0;   // 방법 1-1
    m3["Queen"]++;     // 방법 1-2 : 값(Value)을 1 증가 시킴.
    
    // 방법 2
    for (auto i = m3.begin(); i != m3.end(); i++) {
        i->second = 7;       // m3 맵의 요소들의 값(Value)을 모두 7로 변경함.
        (*i).second = 8;     // m3 맵의 요소들의 값(Value)을 모두 8로 변경함.
    }
    
    // 방법 3
    for (auto i : m3) {
        i.second = 9;    // m3 맵의 요소들의 값(Value)을 모두 9로 변경함.
    }
    
    // 방법 4 
    for (auto [key, value] : m3) {
        value = 10;    // m3 맵의 요소들의 값(Value)을 모두 10으로 변경함.
    }
    
    // 방법 5 
    for (auto i = m3.cbegin(); i != m3.cend(); i++) {
        auto [key, value] = *i;   
        value = 11;    // m3 맵의 요소들의 값(Value)을 모두 11로 변경함.
    }
    
    cout << endl;
    
    // [6] 맵 객체의 크기 출력하기
    cout << m1.size() << '\n';
    cout << m2.size() << '\n';
    cout << m3.size() << '\n';
    
    cout << endl;
    
    // [7] 맵 객체의 요소 지우기
    //// 방법 1
    m1.erase(10);
    
    //// 방법 2
    auto search = m1.find(10);
    if (search != m1.end()) {
        m1.erase(search);
    }
    
    cout << endl;
    
    // [8] 맵에 있는 모든 요소 지우기
    m1.clear();
    m2.clear();
    m3.clear();
    
    cout << endl;
    
    // [*] 맵에 요소가 있는지 없는지를 확인하고 맵에 데이터를 할당하기
    //// 방법 1
    if (m1[90] == "") {
        m1[90] = "Koo";
    }
    
    //// 방법 2
    if (m1.find(50) == m1.end()) {
        m1[50] = "Jung";
    }
    
    // 결과 출력
    for (auto i : m1) {
        cout << "(" << i.first << ", " << i.second << ")" << '\n';
    }
    
    for (auto i : m2) {
        cout << "(" << i.first << ", " << i.second << ")" << '\n';
    }
    
    for (auto i : m3) {
        cout << "(" << i.first << ", " << i.second << ")" << '\n';
    }
    
    return 0;
}

(65, Kim)
(35, Park)
(10, Choi)
(20, Lee)
(40, Me)

(3, Yun)
(2, Kuk)
(1, Lim)

Not Found.
Key : 20, Value : Lee
0 0

5
3
4



(50, Jung)
(90, Koo)