C++ unordered_map이란?

unordered_map이란?

• 기존에 익숙한 map과 비슷하지만 정렬되지 않은 해시 기반 컨테이너(이름에서부터 정렬되지 않음을 들어냄)
• Key-Value 쌍으로 데이터를 저장
• Key를 기준으로 해시(hash)를 이용해 빠르게 탐색, 삽입, 삭제가 가능
• 내부적으로 해시 테이블(Hash Table)을 사용
• 원소의 순서를 보장하지 않음. (반복자로 순회 시 삽입 순서로 정렬되어 있지 않음)
• 평균 시간 복잡도
  • 탐색(find) : O(1)
  • 삽입(insert) : O(1)
  • 삭제(delete) : O(1)

기본 사용 예제

#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    unordered_map<int, std::string> unMap;
    unMap.emplace(1, "jane");
    unMap.emplace(2, "steve");
    unMap.emplace(3, "mark");

    for (const auto& pair : unMap)
    {
        std::cout << pair.first << ":" << pair.second << std::endl;
    }
}

주요 함수 정리

• insert()
  • 새로운 키-값 쌍 추가
  • 이미 존재하는 키면 추가되지 않음

• operator[] (인덱스 연산자)
  • myMap[key]로 접근
  • Key가 없으면 자동으로 생성 후 초기값(ValueType의 default값)으로 초기화됨
• find()
  • Key를 찾으면 해당 iterator 반환
  • 만약 못찾으면 myMap.end()를 반환
• count()
  • Key가 존재하면 1, 없으면 0을 반환
• erase()
  • 해당 Key의 원소를 삭제
• size()
  • 원소 개수를 반환
• clear()
  • 모든 원소를 삭제

주요 함수들 사용 예제

#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    unordered_map<int, std::string> unMap;
    
    // insert() 함수
    unMap.insert({11, "mike"});
    unMap.insert(std::make_pair(33, "jordan"));
    
    unMap[3] = "jane";
    unMap[5] = "ordin";
    
    unMap.emplace(4, "april");
    unMap.emplace(7, "sath");
    
    // 순회하기
    for (const auto& pair : unMap)
    {
        std::cout << pair.first << ":" << pair.second << std::endl;
    }

    // find() 함수
    auto target = unMap.find(11);
    if (target == unMap.end())
    {
        std::cout << "not exist 11 element." << std::endl;
    }

    // find() 함수
    auto target1 = unMap.find(2);
    if (target1 == unMap.end())
    {
        std::cout << "not exist 2 element." << std::endl;
    }
    else
    {
        std::cout << (*target1).first << ":" << (*target1).second << std::endl;
        std::cout << target1->first << ":" << target1->second << std::endl;
    }

    // count() 함수
    auto result = unMap.count(3);
    std::cout << "count:" << result << std::endl;

    std::cout << "before size:" << unMap.size() << std::endl;

    // erase() 함수
    unMap.erase(2);

    for (const auto& pair : unMap)
    {
        std::cout << pair.first << ":" << pair.second << std::endl;
    }

    std::cout << "after size:" << unMap.size() << std::endl;

    // clear()
    unMap.clear();

    std::cout << "after size:" << unMap.size() << std::endl;
}

operator[](인덱스 연산자) 더 알아보기

• 존재하지 않는 Key를 쓰면 자동으로 해당 Key로 생성된다.
• 이미 존재하는 Key라면 기존 원소를 덮어쓴다.
• 있으면 수정, 없으면 추가할 때 유용하게 사용이 가

#include <unordered_map>
#include <string>

std::unordered_map<std::string, int> myMap;
myMap["apple"] = 100;          // 추가
myMap["apple"] += 50;          // 값 덮어쓰기

insert() 함수 더 알아보기

• Key가 존재하지 않을때만 추가됨
• Key가 이미 존재하면 아무 변화 없음
• 반환값으로 pair<iterator, bool>를 반환 (insert 성공유무를 확인 가능)

#include <iostream>
#include <unordered_map>
#include <string>

std::unordered_map<std::string, int> myMap;
auto result = myMap.insert({"apple", 100});
if (result.second) {
    std::cout << "삽입 성공!" << std::endl;
} else {
    std::cout << "이미 존재하는 key입니다." << std::endl;
}

emplace() 함수 더 알아보기

• insert와 동일하게 존재하지 않을 때만 추가
• 생성 비용을 절약할 수 있음
• 객체를 pair로 만든 뒤 삽입하지 않고, 컨테이너 내부에서 직접 생성

myMap.emplace("apple", 10);

인덱스 연산자 vs insert vs emplace 비교표

정리하자면

• C++에서 제공하는 unordered_map은 정렬이 필요하지 않은 데이터를 저장할 수 있는 컨테이너
• 기존 map과 비교해서 검색, 삽입, 삭제가 더 빠르다.
• 추가 시 어떤 함수를 써야 하나?
  • 없으면 넣고 있으면 덮어쓰고 싶다 : operator[] (인덱스 연산자)
  • 없을 때만 넣고 싶다 : insert()
  • 없을 때만 넣고, 생성 비용 최적화를 하고 싶다 : emplace()