C++ - 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;
}

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의 존재이유 이니까 0_<.

/*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;

원소를 참조하는 것역시 두가지 방법이 있습니다.(find)

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은 균형트리인 red black tree로 구현되있고 unordered_map은  해시 테이블로 구현되어 있다는 것입니다.

 

어?? 그럼 일반적으로 unordered_map이 성능이 좋은거 아냐? 라고 묻는다면 당연히 yes입니다. 하지만 데이터가 많으면 많을수록 hash table의 성능은 리드미컬 하게 떨어진다.

 

그 이유야 뭐 간단한데 균형트리는 이론상 무조건 균형을 맞추게 되어 있다. 그러나 hash table은 값이 많아지면 비둘기집의 원리에 의해서 필연적으로 해쉬충돌이 일어나고 그러면 한 해시버킷에 충돌적재가 일어나서 결국에 성능은 떨어지게 된다는 것이다. 그래서 실제 벤치마크 테스트를 해보면 자료가 늘어나면 늘어날수록 성능은 unordered_map이 딸린다. 여러분도 잘 생각해서 고르면된다. 데이터가 작다면unordered_map이,크다면 map이 유리합니다.

 

- 멤버함수 종류

 

- m.begin();

- m.end();

- m.rbegin();

- m.rend();

- m.clear();

- m.count(k);

- m.empty();

- m.insert(k);     //k는 pair 객체입니다.

- m.insert(iter, k);

- m.erase(start, end);

- m.find(k);

- m2.swap(m1);

- m.upper_bound(k);

- m.lower_bound(k);

- m.equal_range(k);    

- m.value_comp();

- m.key_comp();

- m.size();

- m.max_size();

 

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