[C++ STL] std::unordered_map(연관 컨테이너)

std::unordered_map

std::unordered_map은 HashTable로 구현된 자료구조로 탐색에 걸리는 시간 복잡도는 O(1) -> 상수시간복잡도.

 -> 기존의 std::map은 이진 탐색 트리로 탐색의 시간 복잡도는 O(logN)의 시간 복잡도.

 -> std::map은 자동으로 정렬되는 컨테이너. 그렇기에 요소의 삽입/삭제가 빈번할 경우 성능이 저하된다.

이름에서 알 수 있듯이. 정렬되지 않은 맵. std::map과는 달리 자동으로 정렬되지 않기 때문.

 

std::map과 같이 중복 키를 허용하지 않으며, key와 value의 쌍(pair)으로 요소를 저장한다는 공통점이 존재.

 -> 다른 점은 내부 구현된 자료구조가 다르며, 요소는 key값을 통해 해시 함수가 생성하는 index기반의 bucket(list 배열)에 저장된다.

 -> 기존의 해시 테이블의 문제점인 해시 충돌의 문제점은 존재하며, 해시 충돌로 인한 성능 저하 및 탐색 시간이 길어질 수 있다.

 -> std::unordered_map은 해시 충돌이 일어날 때 일차, 이차 조사법의 방법이 아닌 체이닝 기법을 이용해 하나의 버킷에 둘 이상의 데이터가 들어간다. 

 -> key값을 통해 구한 해시에서 해시 충돌이 많고, 해당 버킷에 저장된 데이터가 많으면 상수 시간 복잡도를 보장할 수 없음. (최악의 경우 탐색 시간이 O(n))

 -> 해시 충돌을 피하는 방법은 해시 함수를 잘 설계하거나, 충분한 bucket사이즈 등이 있다.

 

먼저 std::unordered_map을 사용하기 위해서는 <unordered_map> 헤더 파일을 추가해야 한다.

기본적인 생성 방법.

// 기본적인 생성 방법.
std::unordered_map<int, int> uMap;
// 복사 생성자 지원.
std::unordered_map<int, int> uMap2(uMap);

unordered_map <key_type, value_type>이며, 템플릿의 첫 번째 인자가 key값의 자료형, 두 번째 인자가 저장할 객체의 자료형이다.

 

멤버 함수를 하나씩 살펴보자.

 

1. insert함수

// 기본적인 생성 방법.
std::unordered_map<std::string, int> uMap;
 
std::pair<std::unordered_map<std::string,int>::iterator,bool> iter = 
    uMap.insert(std::make_pair("Test",10));

insert함수는 std::unordered_map에 새 요소를 삽입하는 함수.

std::unordered_map은 내부적으로 데이터를 key와 value의 쌍의 형태로 데이터를 저장하기에 pair로 만들어 데이터를 전달해야 한다.

또한 insert함수 호출 시 first에는 iterator를 second에는 bool값을 가지는 std::pair를 반환하게 되는데 반복자는 삽입한 요소를 가리키게 되며, bool값은 삽입의 결과를 알려준다.

 -> std::map과 동일

first에는 삽입한 요소를 가리키는 반복자(iterator), 두 번째는 삽입의 성공 여부(중복 키를 허용치 않음)

만약 같은 key를 가지는 요소를 다시 삽입해보면

반환되는 pair의 first의 반복자는 이미 존재하는 key 요소를 가리키며, second는 false를 나타낸다.

 -> 즉 중복키를 허용하지 않는다.

 

key값을 사용자 정의 자료형을 넣으면 어떻게 될까.

class Student
{
public:
    Student(int kor, int eng, int math) : m_kor(kor), m_eng(eng), m_math(math)
    {
        m_avg = (m_kor + m_eng + m_math) / 3;
    }
    bool operator<(const Student& other) const // const꼭 붙여야한다.
    {
        return this->m_avg > other.m_avg; // 내림차순
    }
public:
    int m_kor;
    int m_eng;
    int m_math;
    int m_avg;
};
 
 
 
int main()
{
    // 기본적인 생성 방법.
    std::unordered_map<Student, int> uMap2;
 
    std::pair<std::unordered_map<Student, int>::iterator, bool> iter3 = 
        uMap2.insert(std::make_pair(Student(10, 20, 30), 10));
 
    return 0;
}

실행 시 위와 같은 에러를 내뱉는다.

std::map과 같이 operator < 연산자를 오버 로딩하였다고 생각하지만, std::unordered_map은 정렬되지 않는 컨테이너라고 했다. -> operator < 연산자를 오버 로딩할 필요가 없다.

 

문제는 사용자 정의 자료형에서 어떻게 해시 함수를 만들지를 모르는 것. 즉 우리가 직접 해시함수를 만들어줘야 한다.

 -> 해시 충돌을 대비해서 operator == 연산자도 오버 로딩해주어야 한다.

// C++표준 클래스(구조체)를 특수화 하기위해 namespace std안에서 해주어야 함.
namespace std
{
    //템플릿 특수화 사용
    //hash<사용자 정의 자료형> 규칙을 맞춰야 한다.
    template <>
    struct hash<Student>
    {
        // ()연산자 오버로딩.
        size_t operator()(const Student& student) const // const 는 꼭 붙여야 한다.
        {
            // 매우 간단한 해시 함수.
            return student.m_avg - student.m_avg - 1;
        }
    };
}

먼저 hash 함수 정의.

C++ 표준 구조체이기에 조금 까다롭게 템플릿 특수화를 하여 정의된 자료형을 넣어주면 된다.

operator() 연산자를 오버 로딩하면 되고, 내부에서 해시 알고리즘을 작성하여 bucket의 index에 해당하는 값을 리턴한다.

 

여기서 끝이 아니고, 사용자 정의 자료형에서 operator == 연산자도 오버 로딩해주어야 한다.

class Student
{
public:
    Student(int kor, int eng, int math) ...
    bool operator==(const Student& other) const // const꼭 붙여야한다.
    {
        // key충돌의 기준은 m_kor
        if (other.m_kor == this->m_kor)
            return true;
        return false;
    }
public:
    int m_kor;
    int m_eng;
    int m_math;
    int m_avg;
};

위와 같이 간단하게 정의한 후, 제대로 요소가 삽입되는지 확인해보면

제대로 삽입이 되는 것을 알 수 있다.

 

위에서 해시 함수를 구하는 알고리즘이 매우 빈약한데, 해시 충돌을 피하기 위해서는 잘 설계된 해시 함수가 필요.

 

2. operator [] 연산자.

// 기본적인 생성 방법.
std::unordered_map<std::string, int> uMap;
 
uMap["Test"] = 10;
 

operator [] 연산자를 이용하여 std::unorder_map에 새 요소를 삽입할 수 있다.

기본적으로 std::map과 기능이 동일하다.

 -> std::unordered_map에 키가 이미 존재하면 넘겨준 value로 기존의 value를 덮어 씌운다.

  --> std::map과 똑같이 해당 key에 대응하는 value를 참조로 반환하기에. (find기능)

// 기본적인 생성 방법.
std::unordered_map<std::string, int> uMap;
 
uMap["Test"] = 10;
uMap["Test"] = 20; // 값이 덮어씌워짐.
 
// 해당하는 key의 value를 참조로 반환.
std::cout << uMap["Test"];

또한 std::map과 같이 key값이 존재하지 않는데 find와 같이 접근을 할 경우.

// 기본적인 생성 방법.
std::unordered_map<std::string, int> uMap;
 
uMap["Test"] = 10;
uMap["Test"] = 20; // 값이 덮어씌워짐.
 
std::cout << uMap["Test2"]; // 존재하지 않는 key (Test2)

위와 같이 새롭게 요소를 만들어 넣어버린다. (std::map과 똑같은 문제)

만약 프로그래머가 operator [] 연산자를 이용하여 해당 key값에 대응되는 값(value)의 반환의 결과만을 얻고 싶었는데

위와 같이 새 요소가 삽입이 되었다면 원치 않는 결과가 발생할 수 있다.

 -> 그렇기에 주의해서 사용해야 한다.

 

insert함수와 가장 큰 차이는 중복 key가 존재하면 insert는 삽입하지 않지만 

operator []는 중복 key가 문제가 아니라 해당 key에 해당하는 값(value)의 참조를 반환하기에 값을 덮어씌울 수 있으며

해당 key가 존재하지 않는다면 해당 key와 함께 0이라는 값을 채워 std::unordered_map에 삽입해버린다

 

3. find 함수

// 기본적인 생성 방법.
std::unordered_map<std::string, int> uMap;
 
uMap["Test"] = 10;
uMap["Test"] = 20; // 값이 덮어씌워짐.
 
auto iter = uMap.find("Test");
if (iter != uMap.end())
{
    std::cout << iter->second;
}

std::unordered_map의 find함수는 이름에서 알 수 있듯이 인자로 넘긴 키(key) 값을 넘겨 map에서 탐색 후 반복자를 반환하는 함수.

1. find함수의 인자로 넘긴 값에 해당하는 key가 unordered_map에 존재한다면 해당 key와 value의 요소를 가리키는 반복자를 반환한다.

2. 만약 해당하는 key가 없다면 nullptr을 반환하는 것이 아닌 end를 반환한다.

 

find함수. std::map에서 설명하는 것과 다른 게 없다. 단 내부적으로 탐색하는 방법이 다르다.

 -> std::map의 경우에는 루트 노드부터 key값과 비교하면서 내려간다 최대 log(N)의 시간 복잡도.

 -> std::unordred_map의 경우에는 key값에 대응되는 해시값을 통해 index에 접근. -> O(1) ~ O(N) -> 최악의 경우.

 

find함수는 이게 전부이고, 인자로 넘겨주는 값은 key값이어야 한다는 것을 잊지 말아야 한다.

 

그 외의 함수는 map과 인터페이스가 동일하다. (erase, clear, begin, end 등등)

 

 

std::unordered_map 컨테이너의 장점

 - std::map과 달리 자동으로 정렬되지 않는다.

 - 해시 테이블의 자료구조를 이용하여 요소의 탐색 시간이 O(1) -> 상수 시간 복잡도.

 

std::unordered_map 컨테이너의 단점

 - 해시 충돌이 자주 일어날 경우 성능 저하 및 해당 버킷의 탐색 시간이 최악의 경우 O(N).

 - bucket으로 인한 메모리 사용량이 증가한다.