map

---

map 은 C++ 에서 제공하는 컨테이너 중 하나로 <Key, Value> 형태로 저장할 때 사용한다.

Python의 dictionary 와 같은 구조이지만 C++ 의 map 은 자동으로 key 에 대한 오름차순으로 정렬을 한다. 따라서 따로 정렬을 해줄 필요가 없게 된다.

또한 key 의 중복을 허용하지 않는다.

자동 정렬을 하지 않고 <key, value> 형태로 저장하고 싶다면 unordered_map을 이용하면 된다.
map은 tree 형태이므로 find에 대한 시간 복잡도가 O(log(n)) 이지만
unordered_map은 hash table 형태로 시간 복잡도가 O(1) 이다.

중복 key 를 사용하기 위해서는 multimap를 이용한다.

vector와 queue 처럼 컨테이너이므로 #include <map> 이 필요하다.

구현 예시

---

https://www.acmicpc.net/problem/1764
백준 1764번 : 듣보잡

해당 문제는 문자열들을 입력받고 이후 다시 입력한 문자열들 중 먼저 입력받은 문자열과 같을 경우를 count 하여 해당 문자열들을 오름차순으로 정렬하여 출력하는 문제이다.

따라서 <key, value> 형태로 key 에 문자열을 저장하고 이후 입력받은 문자열을 map 의 key로 대입하여 value가 true 로 존재하면 같은 문자열이 존재한다는 것을 알 수 있다.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main()
{

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, M;
    int cnt = 0;
    map<string, int> my_m;
    vector<string> v2;

    cin >> N >> M;

    for(int i = 0; i < N; i++)
    {
        string str;
        cin >> str;
        my_m[str] = true;
    }

    for(int i = 0; i < M; i++)
    {
        string str;
        cin >> str;
        
        if (my_m[str])
        {
            cnt++;
            v2.push_back(str);
        }
    }
    cout << cnt << '\n';

    sort(v2.begin(),v2.end()); // for output format

    for(int i = 0; i < v2.size(); i++)
    {
        cout << v2[i] << '\n';
    }
    

    
    return 0;
}