[C++11] unordered_map

최근에 스크립트형 언어 컴파일러를 만들고 있습니다.

(실시간 스크립트 변형 후 동작을 위한)

 

이 과정 중에서 어휘 분석기(Lexical Analyzer)를 구현하는 과정에서 이전에 한 번 써보았던 unordered_map를 사용하게되어 unordered_map을 다시 공부한 내용을 써보려고 합니다.

 

들어가기에 앞서

제가 공부한 내용들은 전부 아래의 링크들에서 학습 및 참고하였습니다.

A Proposal to Add Hash Tables to the Standard Library

 

std::unordered_map - cppreference.com

 

unordered_map 클래스

 

unordered_map이란

• unordered_map은 C++ 위원회에서 만든 해시 테이블(Hash Table)을 이용하여 해시맵(Hash Map) 기능을 하는 컨테이너(Container)입니다.
  (정식 도입은 C++11에서 이루어졌습니다.)
  hash라는 구조체와 함께 unordered_map, unordered_set, unordered_multimap, unordered_multiset 네 가지가 도입이 되었습니다.
• unordered_map은 말 그대로 "정렬되지 않은 map"입니다.
• map과 동일하게 키(Key)와 요소(Element)로 이루어져 있으며 키(Key)는 중복될 수 없습니다.
• 평균 시간 복잡도는 O(1) 입니다.
  (단, O(1)의 속도를 유지하려면 요소의 수가 증가할 수록 버킷의 수도 같이 증가해야 함(메모리의 증가))
  최악의 상황인 경우에는 O(N) (N은 키의 개수)
• unordered_map은 버킷(Bucket) 단위로 관리됩니다.
• 버킷은 단일 링크드리스트(Singly linked list)로 이루어져 있습니다.
• insert(특정 위치 삽입)할 때 최대 O(N * size()) 만큼 걸리는 것으로 보아 특정 위치에 많은 삽입이 일어나는 경우에는 성능 저하 가능성이 높습니다.
• #include <unordered_map> 필요합니다.
• std namespace를 사용해야합니다.
  (std::unordered_map)

 

unordered_map 생성자

// C++11
// Key       : 키 형식
// T         : 매핑 형식
// Hash      : 해시에 사용할 함수 개체 형식
// KeyEqual  : 비교에 사용할 함수 개체 형식
// Allocator : 할당자
template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;

// C++17
// Key       : 키 형식
// T         : 매핑 형식
// Hash      : 해시에 사용할 함수 개체 형식
// KeyEqual  : 비교에 사용할 함수 개체 형식
namespace pmr 
{
template <
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>
> using unordered_map = std::unordered_map<Key, T, Hash, KeyEqual,
                            std::pmr::polymorphic_allocator<std::pair<const Key,T>>>;
}

C++11과 C++17의 차이점은 Allocator의 차이가 있습니다.

 

보통 Hash, KeyEqual, Allocator는 기본값을 사용하며 Key와 T만 선언하여 사용합니다.

#include <unordered_map>

int main()
{
    // 키 타입은 string, 데이터는 int
    std::unordered_map<std::string, int> umap;
    
    return 0;
}

 

데이터 추가 (insert)

#include <unordered_map>
#include <iostream>

int main()
{
    std::unordered_map<std::string, int> umap;
    // 방법 1
    umap.insert(std::make_pair("Hi", 11));
    // 방법 2
    umap.insert(std::unordered_map<std::string, int>::value_type("My", 22));
    // 방법 3
    umap.insert({ "Hello", 33 });
    
    return 0;
}

기본적으로 위와 같은 방법이 있습니다.

 

반복자 (iterator)

vector, deque 등의 컨테이너(Container)들과 마찬가지로 정방향, 역방향 반복자를 지원합니다.

#include <unordered_map>
#include <iostream>

int main()
{
    std::unordered_map<std::string, int> umap = 
    {
        std::make_pair("Hi", 1),
        std::make_pair("Hello", 3),
        std::make_pair("World", 4),
        std::make_pair("!!!", 6)
    };
    
    // 정방향
    // auto it = umap.begin(); 도 가능
    std::unordered_map<std::string, int>::iterator it = umap.begin();
    while (it != umap.end())
    {
        // Do something ...
        ++it;
    }
    
    // 역방향
    // auto cit = umap.cbegin(); 도 가능
    std::unordered_map<std::string, int>::const_iterator cit = umap.cbegin();
    while (cit != umap.cend())
    {
        // Do something ...
        ++cit;
    }
    
    // 정방향 (버킷의 크기 만큼 이동)
    // auto itb = umap.begin(umap.bucket("Hi")); 도 가능
    std::unordered_map<std::string, int>::iterator it = umap.begin(umap.bucket("Hi"));
    
    // 역방향 (버킷의 크기 만큼 이동)
    // auto citb = umap.cbegin(umap.bucket("Hi")); 도 가능
    std::unordered_map<std::string, int>::const_iterator citb = umap.cbegin(umap.bucket("Hi"));
    
    return 0;
}

버킷단위로 관리하는 만큼 버킷의 크기만큼 이동하는 반복자도 지원합니다.

 

데이터 삭제 (erase)

unordered_map의 erase는 map의 erase와 동일한 동작을 수행합니다.

#include <unordered_map>
#include <iostream>

int main()
{
    std::unordered_map<std::string, int> umap = 
    {
        std::make_pair("Hi", 1),
        std::make_pair("Hello", 3),
        std::make_pair("World", 4),
        std::make_pair("!!!", 6)
    };
    
    std::unordered_map<std::string, int>::iterator it = umap.begin();
    umap.erase(it);	    // { "Hi",1 }   제거
    umap.erase("!!!");  // { "!!!", 6 } 제거
    
    return 0;
}

 

요소 값(Element) (at, [ ])

특정 키(Key)의 요소 값(Element)을 받아오는 기능입니다.

#include <unordered_map>
#include <iostream>

int main()
{
    std::unordered_map<std::string, int> umap = 
    {
        std::make_pair("Hi", 1),
        std::make_pair("Hello", 3),
        std::make_pair("World", 4),
        std::make_pair("!!!", 6)
    };
    
    printf("Hi: %d\n", umap.at("Hi"));     // Hi: 1
    printf("Hello: %d\n", umap["Hello"]);  // Hello: 3
    umap["Hello"] = 5;
    printf("Hello: %d\n", umap["Hello"]);  // Hello: 5
    
    return 0;
}

[ ] operator의 경우에는 값을 대입할 수도 있습니다.

 

키(Key)의 요소 값(Element) 찾기 (find)

키(Key)의 요소 값(Element)을 찾는 기능입니다.

#include <unordered_map>
#include <iostream>

int main()
{
    std::unordered_map<std::string, int> umap = 
    {
        std::make_pair("Hi", 1),
        std::make_pair("Hello", 3),
        std::make_pair("World", 4),
        std::make_pair("!!!", 6)
    };
    
    std::unordered_map<std::string, int>::iterator it = umap.find("World");
    
    // 키값을 찾지 못했다면 iterator는 end()와 같음
    if (it != umap.end())
        printf("Find: [%s, %d]\n", it->first, it->second);  // Find: [World, 4]
    
    return 0;
}

 

키(Key)의 요소 개수 찾기 (count)

find()와 비슷하지만 find()는 키(Key)와 요소(Element)를 반환하는 대신에 count()는 단순히 개수만 반환합니다.

#include <unordered_map>
#include <iostream>

int main()
{
    std::unordered_map<std::string, int> umap = 
    {
        std::make_pair("Hi", 1),
        std::make_pair("Hello", 3),
        std::make_pair("World", 4),
        std::make_pair("!!!", 6)
    };
    
    // 키값을 찾으면 반환되는 개수는 1 (키값이 중복되지 않으므로 요소의 개수도 1개)
    if (umap.count("Hi") == 1)
        printf("Find: Hi");
    
    return 0;
}

실제로 libcxx에서 count()를 구현할 때 find()를 사용했다고 합니다.

unordered_map: which one is faster find() or count()?

 

요소가 비어있는지 확인 (empty), 전체 요소의 개수 (size)

다른 컨테이너(Container)에서도 제공하는 empty()와 size()입니다.

#include <unordered_map>
#include <iostream>

int main()
{
    std::unordered_map<std::string, int> umap;
    
    if (umap.empty())
        printf("umap is empty.\n");
        
    umap.insert(std::make_pair("Hi", 1));
    umap.insert(std::make_pair("Hello", 3));
    umap.insert(std::make_pair("World", 4));
    umap.insert(std::make_pair("!!!", 6));
    
    if (umap.empty() == false)
        printf("umap count: %d\n", umap.size());
    
    return 0;
}