[c++][STL][map][unordered_map]C++에서 map(딕셔너리:dictionary, 연관배열:associate array,해시맵:hash map)사용하기(map과 unordered_map, 그리고 차이점)

맵은 다른용어로 연관배열(php, javascript), 딕셔너리(python), 해시맵(java), js object(javascript)등으로 다양하게 불리운다.

사실 해시맵은 맵의 일종이다. 이는 아래에서 설명하도록 하겠다.

맵에 대해서 약간 설명하도록하자.

맵은 인덱스를 문자열로 받는 배열이라고 생각하면 편하다.

일반배열이 숫자만을 인덱스 번호로 받는다면 맵은 문자열을 인덱스 번호로 받을 수 있다.

c++에서는 여러종류의 맵이 존재한다. 그 중에서 가장 유명한 맵은 map과 unordered_map이다.

이 둘은 각각 구현방법이 다르다. 그래서 사용하는 곳도 다르다.

map은 balanced tree로 구현된다. 한국말로 하면 균형트리인데 균형트리중에서 red-black트리로 구현되있다.

unordered_map은 hash table로 구현된다. 즉 해시맵인것이다.

균형트리와 해시테이블에 대해서 논하지는 않겠다. 그것만 말해도 시간이 엄청 걸릴 테니까.

둘 다의 장단점이 있는데 포스팅 마지막 쯤에 짧막하게 논하도록 하겠다.

map

#include <map>
#include <iostream>

using namespace std;

int main() {
    map<string, int> m;

    /*insert*/cout<<"**********insert**********"<<endl;
    /*1*/m.insert(pair<string, int>("marin", 40));
    /*2*/m.insert(make_pair("scv", 60));
    /*3*/m["firebat"] = 50;

    /*iterate*/cout<<"**********iterate**********"<<endl;
    /*1*/map<string, int>::iterator it; // auto it = m.begin()도 가능
    for (it = m.begin(); it != m.end(); it++) {
        cout << it->first << " " << it->second << endl;
    }

    /*2*/for (pair<string, int> atom : m) {
        cout << atom.first << " " << atom.second << endl;
    }

    /*find*/cout<<"**********find**********"<<endl;
    /*1*/cout<<m.find("scv")->first<<" "<<m.find("scv")->second<<endl;
    /*2*/cout<<"scv"<<" "<<m["scv"]<<endl;


    /*erase*/cout<<"**********erase**********"<<endl;
    /*1*/m.erase("scv");
    /*2*/m.erase(m.find("marin"));
    for (pair<string, int> atom : m) {
        cout << atom.first << " " << atom.second << endl;
    }

    /*size*/cout<<"**********size**********"<<endl;
    cout<<m.size()<<endl;

    /*empty*/cout<<"**********empty**********"<<endl;
    cout<<m.empty()<<endl;

    return 0;
}

예제가 길다. 게다가 C++의 경우 하도 오래됬다보니 사용하는 방식이 시대에 따라 조금은 차이가 있다.

그래서 경우를 나눠서 설명하도록 하겠다.

map<string, int> m;

선언은 위처럼 해준다. 왼쪽이 key값이고 오른쪽이 value이다.

내부적으로는 pair클래스를 적재하는 방식으로 사용한다.

/*insert*/cout<<"**********insert**********"<<endl;
/*1*/m.insert(pair<string, int>("marin", 40));
/*2*/m.insert(make_pair("scv", 60));
/*3*/m["firebat"] = 50;

insert 방법은 3가지가 있다.

먼저 1번째 방법은 pair를 각각 넣어주는 방식이다. 고대의 방식이며 현재는 이렇게 거의 사용하지 않는다.

뭐 사용할려면 사용하라.

2번과 3번은 iostream을 include해야만 사용할 수 있다. 이유는 모르겠다.

2번은 1번에서 업그레이드 된 방식이다. make_pair라는 함수를 사용하면 pair클래스가 리턴된다. 따라서 위처럼 사용하는 경우도 많다.

하지만.... 이제는 이 방법도 사용하지 않는다. 더 좋은 방식이 있기 때문이다.

3번은 이제 대부분 언어에서 쓰는 방식이다. 이 방식이 갓갓이니까 무조건 이 방식을 사용하라.

그낭 배열처럼 넣어주면된다.

insert할 때 기존의 키에 값이 있으면 어떻게 되느냐? 값을 덮어쓴다. 애당초 그게 map의 존재이유 이니까.

/*iterate*/cout<<"**********iterate**********"<<endl;
/*1*/map<string, int>::iterator it; // auto it = m.begin()도 가능
for (it = m.begin(); it != m.end(); it++) {
    cout << it->first << " " << it->second << endl;
}

/*2*/for (pair<string, int> atom : m) {
    cout << atom.first << " " << atom.second << endl;
}

그럼 for문 반복 역시 두가지 방법이 있다. 배열과는 달리 무조건 iterator를 사용...했었어야 했지만 foreach가 나오면서 iterator를 호출해줄 필요는 없다.

1번 방식은 과거의 방식으로 iterator를 사용하는 방식이다. 사실 이 방식은 지금도 사용할 가능성은 있다.

그건 배열이 foreach문으로 출력할 수 있어도 순회를 동적이게 해야할때 사용하듯이 map역시 마찬가지이다.

라곤 하지만 거의 그렇게 쓸일은 없다.

2번은 foreach구문으로 사용해 주는 것이다. 현재 대부분은 이 방식을 사용한다.

/*find*/cout<<"**********find**********"<<endl;
/*1*/cout<<m.find("scv")->first<<" "<<m.find("scv")->second<<endl;
/*2*/cout<<"scv"<<" "<<m["scv"]<<endl;

원소를 참조하는 것역시 두가지 방법이 있다.

1번 방식인 find를 사용하면 iterator가 나온다. 따라서 화살표연산으로 값을 지정해줘야한다. iterator가 포인터 이니까.

2번방식은 새로나온 방식이다.

1번방식 사용할 이유가.... 정말 단 한개도 없다. 엄청 제한적인 상황에서 사용할수도 있지만 그 상황을 언급할 필요도 없을정도로 사용할 필요가 없다.

/*erase*/cout<<"**********erase**********"<<endl;
/*1*/m.erase("scv");
/*2*/m.erase(m.find("marin"));

원소를 지우는 방법 역시 두가지가 있다.

1번과 2번이 있는데 2번 같이 저렇게 사용하는 경우는 많지 않지만 iterator를 넣어서 사용하는 경우는 아직도 있다.

/*size*/cout<<"**********size**********"<<endl;
cout<<m.size()<<endl;

/*empty*/cout<<"**********empty**********"<<endl;
cout<<m.empty()<<endl;

크기와 비어있는지 여부를 확인하는 함수 이다.

예제를 실행한 결과는 위와 같다.

unordered_map

#include <unordered_map>
#include <iostream>

using namespace std;

int main() {
    unordered_map<string, int> m;

    /*insert*/cout<<"**********insert**********"<<endl;
    /*1*/m.insert(pair<string, int>("marin", 40));
    /*2*/m.insert(make_pair("scv", 60));
    /*3*/m["firebat"] = 50;
    /*2번과 3번은 iostream을 추가해줘야한다.*/

    /*iterate*/cout<<"**********iterate**********"<<endl;
    /*1*/unordered_map<string, int>::iterator it; // auto it = m.begin()도 가능
    for (it = m.begin(); it != m.end(); it++) {
        cout << it->first << " " << it->second << endl;
    }

    /*2*/for (pair<string, int> atom : m) {
        cout << atom.first << " " << atom.second << endl;
    }

    /*find*/cout<<"**********find**********"<<endl;
    /*1*/cout<<m.find("scv")->first<<" "<<m.find("scv")->second<<endl;
    /*2*/cout<<"scv"<<" "<<m["scv"]<<endl;


    /*erase*/cout<<"**********erase**********"<<endl;
    /*1*/m.erase("scv");
    /*2*/m.erase(m.find("marin"));
    for (pair<string, int> atom : m) {
        cout << atom.first << " " << atom.second << endl;
    }

    /*size*/cout<<"**********size**********"<<endl;
    cout<<m.size()<<endl;

    /*empty*/cout<<"**********empty**********"<<endl;
    cout<<m.empty()<<endl;

    return 0;
}

사용하는 방법은 map과 완전하게 같다.

상황에 맞는걸 사용하라.

map과 unordered_map의 차이점

map과 unordered_map은 사용하는 방법은 완전 동일하므로 뭘 쓰든 상관없다.

게다가 적은 데이터라면 큰 차이도 안나므로 뭘 쓰건 상관없다.

다시 말하지만 map은 균형트리인 red black tree로 구현되있고 unordered_map은  해시 테이블로 구현되있다.

어?? 그럼 일반적으로 unordered_map이 성능이 좋은거 아냐? 라고 묻는다면 당연히 yes이다.

하지만 데이터가 많으면 많을수록 hash table의 성능은 리드미컬 하게 떨어진다.

그 이유야 뭐 간단한데 균형트리는 이론상 무조건 균형을 맞추게 되어 있다.

그러나 hash table은 값이 많아지면 비둘기집의 원리에 의해서 필연적으로 해쉬충돌이 일어나고 그러면 한 해시버킷에 충돌적재가 일어나서

결국에 성능은 떨어지게 된다는 것이다. 그래서 실제 벤치마크 테스트를 해보면 자료가 늘어나면 늘어날수록 성능은 unordered_map이 딸린다.

여러분도 잘 생각해서 고르면된다. 데이터가 작다면(작다고 해도 여러분이 일반적인 일에서는 큰 문제없다.) unordered_map이,

크다면 map이 유리하다.