map 과 unordered_map 의 차이점.

[1. 개요]

std::map 은 이진 탐색 트리를 기반으로 한다.

• search 연산을 대상으로 로그의 시간복잡도를 갖는다.

std::unorderd_map 은 해시 테이블을 기반으로 한다.

• key 에 대한 hash 함수가 잘 정의 된다면, 
• search 연산을 대상으로 일반적으로 상수 시간의 시간 복잡도를 갖는다. 

그러나 key 를 대상으로 iterate 시 차이점이 있는데,

• map 은 key 가 정렬 조건 상 앞서는 것 순서대로 조회 할 수 있지만,
• unordered_map 은 그렇지 않다. (그래서 unordered_map 인 듯.)

또, 경우에 따라서, unordered_map 이 map 보다 더 많은 메모리를 사용 할 수 있다.

 

---

[2. 예제]

#include <iostream>
#include <map>
#include <unordered_map>
#include <chrono>

constexpr const int VMAX = 10'000'000;

int main()
{

    std::map<int, int> m;
    std::unordered_map<int, int> um;


    for (int i=1; i<=VMAX; i++) {
        m.insert({i, i});
        um.insert({i, i});
    }

    const auto t0 = std::chrono::steady_clock::now();

    for (int i=VMAX; i>0; i--) {
        m.find(i);
    }

    const auto t1 = std::chrono::steady_clock::now();
    for (int i=VMAX; i>0; i--) {
        um.find(i);
    }

    const auto t2 = std::chrono::steady_clock::now();

    const auto du1 = std::chrono::duration_cast<std::chrono::milliseconds>(t1-t0);
    const auto du2 = std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1);
    const auto du3 = std::chrono::duration_cast<std::chrono::milliseconds>(t2-t0);

    std::cout << "map duration " << du1.count() << " ms\n";
    std::cout << "unordered_map duration " << du2.count() << " ms\n";
    std::cout << "total duration " << du3.count() << " ms\n";
    std::cout << double(du1.count()) / du3.count() * 100 << "%\n";
    std::cout << double(du2.count()) / du3.count() * 100 << "%\n";    

    return 0;
}

 

출력

map duration 2635 ms unordered_map duration 396 ms total duration 3032 ms 86.9063% 13.0607%

 

확실히, unordered_map 이 더 빠른 것을 확인 할 수 있다.

 

set           /  unordered_set 

multimap /  unordered_multimap

multiset   /  unordered_multiset 

 

도 비슷할 듯.

 

=========

여기서, std::vector 를 대상으로 std::lower_bound 사용 시,

unordered_map 보단 느리지만 map 보다는 빠르게 탐색 할 수 있음.

=> 벡터는 배열 형태로, 메모리 구조 상, map 보다 더 효율적으로 접근 할 수 있음

=> 연속적인 구조이므로 캐시 hit 을 더 많이 노릴 수 있다. 

=> 단, 배열의 길이가 너무 길면 또 의미 없을 수 있음.