[C++] map과 unorderd_map

이번에 알아볼 것은
map 과
unorderd_map 이다.

map

C++의 set은
노드 기반 컨테이너로써 균형 이진 트리(레드블렉트리)로 구현 되어있으며,
Key라 불리는 원소들의 집합과 key에 대응하는 value도 같이 저장하는 컨테이너이다. (원소 = key)

c#에서의 Dictionary나 해시테이블을 생각하면 된다.
다른점은 map은 set과 마찬가지로 정렬되어 저장된다는 것.

map은 균형 이진 트리를 이용해 중복 요소가 허용되지 않는 컨테이너이다. 즉, 같은 값을 여러 번 저장할 수 없다.

사용방법

#include <iostream>
#include <map> // map을 사용하기 위해 추가해주어야 한다.
using namespace std;

int main()
{
    map<int, string> myMap; // map<key 자료형, value 자료형> 이름으로 선언한다.
    myMap[0] = "First"; // key 1에 대한 value를 추가한다.
    myMap[1] = "Second"; // key 2에 대한 value를 추가한다.
    myMap[2] = "Third"; // key 3에 대한 value를 추가한다.

    // 중복된 key로 값을 추가하려고 하면 덮어쓴다.
    myMap[3] = "Third2";

    // Map 내부 요소는 key를 기준으로 자동으로 정렬된다.
    for (auto element : myMap)
    {
        cout << "Key: " << element.first << ", Value: " << element.second << " ";
    }

    cout << endl;

    // Map에서 key를 검색
    int key = 2;
    if (myMap.find(key) != myMap.end())
    {
        cout << "Key " << key << "을(를) 찾았습니다. Value: " << myMap[key] << endl;
    }
    else
    {
        cout << "Key " << key << "을(를) 찾지 못했습니다." << endl;
    }

    // key를 이용하여 요소를 제거
    int remove = 3;
    myMap.erase(remove);

    // Map 내용을 출력
    cout << "제거 후: ";
    for (auto element : myMap)
    {
        cout << "Key: " << element.first << ", Value: " << element.second << " ";
    }

    cout << endl;
}

unorderd_map

unorderd_map은 이름에서도 알 수 있듯이 원소들이 정렬되어 있지 않다.

map의 경우 원소들이 순서대로 정렬되어서 내부에 저장되지만, unordered_map의 경우 반복문으로 원소들을 하나씩 출력해보면 거의 랜덤한 순서로 나오는 것을 볼 수 있다.

또한 unordered_map은 map과는 달리 해시테이블로 구현 되어있다.

그럼 왜 쓰는데

정렬도 되지 않는 unordered_map을 쓰는 이유는
실행 시간 차이 때문이다.

unordered_map은 insert, erase, find 모두가
O(1).
으로 수행된다!

map의 경우 O(logn). 이었지만
unordered_map의 경우 상수 시간에 원소를 삽입하고, 검색할 수 있다.

수행시간이 다른 이유는
map은 레드블랙트리.,
unordered_map은 해시테이블.로 구현되었기 때문이다.

따라서 딱히 정렬을 하지 않아도 될 상황에서는 unordered_map을 사용하는 것이 더 좋다고 할 수 있다.

unordered_map도 중복된 값은 허용하지 않는다.

사용방법

#include <iostream>
#include <unordered_map> // unordered_map을 사용하기 위해 추가해주어야 한다.
using namespace std;

int main()
{
    unordered_map<int, string> myUnorderedMap; // unordered_map<key 자료형, value 자료형> 이름으로 선언한다.
    myUnorderedMap[1] = "First"; // key 1에 대한 value를 추가한다.
    myUnorderedMap[2] = "Second"; // key 2에 대한 value를 추가한다.
    myUnorderedMap[3] = "Third"; // key 3에 대한 value를 추가한다.

    // 중복된 key로 값을 추가하려고 하면 덮어쓴다.
    myUnorderedMap[3] = "Third2";

    // Unordered_map 내부 요소는 key의 순서를 유지하지 않는다.
    cout << "Unordered_map의 내용: ";
    for (auto element : myUnorderedMap)
    {
        cout << "Key: " << element.first << ", Value: " << element.second << " ";
    }

    cout << endl;

    // Unordered_map에서 key를 검색
    int key = 2;
    if (myUnorderedMap.find(key) != myUnorderedMap.end())
    {
        cout << "Key " << key << "을(를) 찾았습니다. Value: " << myUnorderedMap[key] << endl;
    }
    else
    {
        cout << "Key " << key << "을(를) 찾지 못했습니다." << endl;
    }

    // key를 이용하여 요소를 제거
    int remove = 3;
    myUnorderedMap.erase(remove);

    // Unordered_map 내용을 출력
    cout << "제거 후: ";
    for (auto element : myUnorderedMap)
    {
        cout << "Key: " << element.first << ", Value: " << element.second << " ";
    }

    cout << endl;
}

사용하는 방법또한 map과 다르지 않다.
unordered_map은 map과 같지만
정렬이 되지않는다.
라는 것만 알고 있으면 쉽게 사용 할 수 있을 것이다.

map과 unordered_map을 사용하는 백준문제 풀어보기
map과 unordered_map을 사용하는 백준문제 풀어보기

map과 unordered_map을 사용하는 프로그래머스 문제 풀어보기

이 문제들을 해결하였다면 기초적인 map과 unordered_map의 사용법은 모두 터득하였다고 할 수 있다.

set과 unordered_set