c++ STL Map/Unordered_Map에 관한 정보!

오늘은 c++ stl 중 하나인 map에 대해서 다뤄보려고 한다. unordered_map도 같이 다룰 예정이다! 사실 아직 이에 관한 지식이나 정보가 많이 부족해서 내가 이해하는 내용들만 적고 나머지는 차차 문제 풀고 이해해나가면서 추가할 예정이다.

먼저 stl map은 사용하기 위해서

#include <map>

을 통해 헤더를 include 해줘야 한다.

이제 map을 설명해보도록 하겠다. map은 자료구조 중 하나로써, 데이터 관리에 사용된다. 자료 구조 중에 트리(tree)라는 것이 있는데(모르면 한번 보고 오는 것을 추천한다), map은 트리인데, 각 노드가 key와 value의 pair로 이루어져있다. 여기서 pair는 그 내가 전에 글을 썼던 그 pair가 맞다(pair를 모르면 먼저 pair부터 공부하자). pair는 알다시피 first, second가 존재한다. first가 key고, second가 value다. 나름 중요한 정보인데, map은 중복을 허용하지 않는다. 정확히 말하면, key가 unique해서 key가 중복되지 않는다. 이후에 설명할 unordered_map과는 다르다.

사용 이유는....여러 가지가 있을 것이고 딱 특정하긴 애매하다. 우리가 특정 자료 구조를 가지고 이건 이거 때문에 쓴다 이렇게 말을 못하니까...근데 지금까지 문제 풀면서 맵이 사용되는 경우는 대부분 값을 저장한 뒤에 검색, 혹은 순회를 통해서 key를 이용해서 값을 얻는 그런 과정에서 사용됐다.

map은 검색(find), 삽입(insert), 삭제(erase) 등 다양한 기능이 존재하는데, 이 기능들의 시간복잡도는 모두 O(logn)이다. 이걸 레드블랙트리라고 하던데, 아직 트리에 대해 그리 잘 알진 않아서 레드블랙트리에 대해서는 별로 정보가 없다. 궁금하면 따로 찾아보는 것이 나을 것 같다. 그냥 시간복잡도 정도만 알아놔도 충분할 것 같다.

이제 map의 사용법에 대해서 알아보자! 먼저 map은 다음과 같이 선언해준다.

map<type, type> m;

당연히 여기서 저 type은 각각 key의 자료형, value의 자료형을 의미한다(pair랑 비슷하다). 그리고 이 map은 신기하게도, 자동으로 오름차순 정렬이 된다! 만약에, 자동으로 내림차순 정렬이 되는 map을 만들고 싶으면

map<type, type, greater> m;

다음과 같이 greater를 추가해주면 된다.

기본적으로 map은 벡터랑 비슷하다고 생각할 수 있다. 선언 방식도 비슷하고, 멤버 함수도 begin(), end(), clear(), empty(), erase(), find(), upper_bound(), lower_bound() 등 비슷하다(기능도 사실상 똑같다고 보면 된다). 그래도 기본적인 삽입, 삭제, 검색, 순회는 알아두도록 하자.

먼저 insert다. 두 가지 방식이 있다. 하나는 insert 함수를 이용해서 삽입하는 것이다. 위에서 말했듯이 key와 value, 이렇게 pair 형태로 이루어져있기 때문에, 삽입도 pair로 삽입해줘야 된다. 가령 이런 식이다.

map <int, string> m;
m.insert({3, "hi"});

pair 설명 글에서도 저렇게 중괄호로 묶어서 삽입하는 것에 대해 얘기했다(아까도 말했지만 pair를 모르면 먼저 pair부터 공부를 하고 와서 이 글을 보는 것이 맞다). 혹은 pair를 만들어서 삽입해도 된다. 가령 이런식으로 말이다.

map <int, string> m;
m.insert(pair<int, string>(3, "hi"));

요건 pair 형태로 바로 insert 하는게 아니라 pair를 만들어서 insert 하는 것이다. 어차피 둘이 같은 방식이니까, 좀 더 간단한 전자의 방식을 추천한다.

근데 재밌게도 insert 함수를 이용해서 값을 넣을 때 key 값이 겹치면(중복되면) 애초에 삽입이 안된다. 그니까 그냥 뱉어버리는 것이다. 퉤. 근데 그러면, 물론 의도치 않게 실수로 중복값을 넣으면 안될때 넣어버리면 좋을 것이다. 알아서 뱉어버리니까. 근데 만약에 해당 key의 value를 업데이트 해주고 싶다면...?

예를 들어서, {3, "hi"}인데, hi 말고 hello를 넣고 싶으면? {3, "hello"}를 넣으면 뱉어서 소용이 없다. 그럴 때는 operator []를 사용해주면 된다.

[]는 굳이 따지면 업데이트라고 보면 된다. 나는 보통 insert를 통해서 삽입을 하고, 특정 key의 value를 업데이트 하고 싶을 땐 []를 쓴다. 말로 풀면 더 복잡할 것 같아서 예시 코드를 쓰겠다.

map <int, string> m;
m.insert({3, "hi"});
m.insert({4, "hii"});
cout<<m[1].first<<m[1].second<<endl; // 4hii 출력
m[1]="Hello";
cout<<m[1].first<<m[1].second<<endl; // 4Hello 출력

충분히 이해할 만한 간단한 삽입 및 업데이트 코드라고 생각한다. 참고로 접근은 위와 같이 그냥 벡터에서 특정 원소 접근하듯이 []와 인덱스를 이용해서 접근해주면 되고, 각 key, value 접근은 당연히 pair니까 first와 second를 이용해주면 된다.

추가: 반대로 m["Hello"]=1;도 된다! 이 [] operator를 이용한 삽입을 제대로 사용을 못해서 백준 문제 하나를 쓸데없이 드럽게 어렵게 풀었다. [] operator를 이용해서 업데이트 뿐만 아니라 자유롭게 삽입도 가능하다는 점도 참고하자,,

다음은 삭제 함수다. 기본적으로 erase를 사용한다. 다 지우고 싶으면 clear()를 사용한다. 이것도 간단해서 그냥 예시코드로 끝내겠다.

map <int, string> m;
m.insert({3, "hi"});
m.insert({4, "hii"});
m.insert({5, "hiii"});

m.erase(4); // 이러면 key가 4인 {4, "hii"}가 지워진다
m.clear(); // 싹 다 지워버린다

아 참고로 저기 erase에서 꼭 저렇게 key 말고, value를 넣어줘도 된다. erase("hii"); 이런식으로 말이다.

다음은 검색 함수다. 검색은 find()와 end()를 쓴다. 그리고 데이터 검색에서는 기본적으로 iterator를 사용한다. 이 iterator가 end()를 반환해서 end()를 쓴다는 것이다. 참고로 iterator는 반복자를 의미한다.

반복자는 벡터나 map 등의 컨테이너에 저장된 원소를 순회하면서 접근하는 방법을 제공하는 것을 말한다. 말이 좀 어려워진 것 같은데, 그냥 포인터랑 비슷한 느낌이다. 우리 문자열에서 각 문자들 확인할때 보통 반복문에서 포인터 맹글어놓고 그걸로 하나하나 챱챱 비교하던가 하면서 확인한다(문자열 문제 좀 풀어봤으면 뭔 소린지 알 것이다). 그런 느낌이다. 다만 컨테이너, 그러니까 라이브러리마다 다 요소들을 순회하는 방식이 다르기 때문에 반복자 자체는 다양한데, 그냥 이런 의미라고 보면 된다.

다시 검색으로 돌아와서, 검색 자체에 좀 더 집중해보자. 아까 말했듯, iterator는 데이터를 못 찾았을 때 end()를 반환한다. 뭐 이해가 잘 안되면 간단하게 반복문 끝까지 싹 돌았는데도 없으면 끝을 반환하는 그런 느낌으로 이해하면 될 것 같다. 사용 방법은 다음과 같다.

map <int, string> m;
m.insert({3, "hi"});
m.insert({4, "hii"});
m.insert({5, "hiii"});

map<int, string>::iterator it;
it=m.find(4);
if(it!=m.end())
{
	cout<<it->first<<endl;
    cout<<it->second<<endl;
}

이런 느낌이다. 코드를 보니까 무슨 느낌인지 감이 오지 않나? 근데 이거보다 조금 더 간단하게 쓸 수도 있다.

map <int, string> m;
m.insert({3, "hi"});
m.insert({4, "hii"});
m.insert({5, "hiii"});

if(m.find("hi")!=m.end())
	cout<<"found!"<<endl;

근데 이건 일단 따로 정보를 담지 않기 때문에 아까 iterator 사용 코드와 다르게 그 값을 알지 못한다. 좀 번거롭긴 하지만 전자처럼 하는게 좀 더 정확하지 않을까라고 생각한다.

그리고 보통 iterator 같은 경우는 auto로도 많이 선언한다.

auto it=m.find(4);

auto가 뭔지 모른다면 검색해서 공부해보는 것을 추천한다(설명하기엔 나도 사실 정확한 정보는 거의 없다).

iterator를 얘기하는 김에 순회에 대해서도 얘기하겠다. 저 iterator는 단순히 find에서만 사용하는 것이 아니라, 반복문을 통해 map을 훑고 싶을때도, 즉 순회시에도 사용한다. 가령 다음과 같이 말이다.

map <int, string> m;
map<int, string>::iterator it;

for(it=m.begin();it!=m.end();it++)
{
	cout<<it->first<<it->second<<endl;
}

이 정도면 map에 대한 설명은 충분한 것 같다. 사실 뭐 훨씬 많은 정보가 있긴 하지만, 이 정도면 그래도 기본적인 정보는 다 채웠다고 생각한다. 한번 간단한 백준 문제들을 통해 공부한 것들을 잘 테스트 해보자!
라고 하고 끝낼 건 아니고, unordered_map에 대해서도 간단히 다루겠다. 너무 길어지긴 하는데, 이걸 따로 다루기엔...한번에 다루는게 낫다.

unordered_map은 map처럼 stl 중 하나다. map에 대해 공부를 했으니, map과 비교하는 방식으로 글을 써보겠다.

일단 이 unordered_map은 map보다 더 빠르게 탐색을 하기 위한 자료구조라고 볼 수 있다. 그냥 더 쉽게 말해서, map보다 더 빠르다. 아까 map의 시간복잡도는 O(logn)으로 사실 굉장히 빠른편이다. 근데 얘는 O(1)로 더 빨라 버린다. 이 unordered_map은 해쉬테이블로 구현한 자료구조다.
해쉬테이블은 또 새로운 개념인데..일단 나는 개념보다는 사용방법에 좀 더 초점을 맞출 것이므로, 간단하게만 설명하겠다. 해쉬 테이블은 해쉬 함수를 이용해서 변환한 값을 인덱스로 삼아서 key, value를 저장하는 자료구조다. 아까 위에서 배운 map이 해쉬테이블이다!
그럼 또 해쉬함수가 나오는데..해쉬 함수는 어떤 임의의 길이를 갖는 input을 입력받아서 고정된 길이의 해쉬값을 출력하는 함수다. 이 이상은 설명하지 않겠다. 내가 가진 정보가 정확하지 않기도 하고, 개념적으로는 그렇게 깊게 파고들려고 하지 않는다. 궁금하다면 직접 구글링해서 공부하는 것이 나을 것이다.

이 unordered_map은 map보다 훨씬 빠르기도 하고, 데이터가 많은 경우에는 더더욱이 좋은 성능을 발휘한다. 다만, 반대로 자료가 적을수록 메모리 낭비도 심해지고, 성능이 떨어져서 오히려 벡터나 리스트가 더 빨라진다. 또한, key가 유사한 데이터값이 많으면 많을수록 해쉬 충돌이라는 현상이 발생할 확률이 올라가서 성능이 역으로 떨어질수도 있다. 결론적으로 이 unordered_map은 보통 큰 규모의 데이터를 저장할 때, 데이터의 크기에 비해 검색 속도를 빠르게 가져가고 싶을 때 쓴다고 보면 되겠다.

원래 이 unordered_map은 hash_map이라는 stl이였는데, 이게 영 엉망이라고 한다. 그래서 unordered_map로 바뀌었고, 이게 표준이다(hash_map은 비표준!). map과의 기본적인 차이점은 이름에서도 알 수 있듯이 값들이 순서대로 정렬되지 않는다. map은 오름차순 정렬이 기본적으로 된다고 위에서 설명했다. 근데 얘는 아니다! 그러니까 키가 순서대로 1 2 3 4 5 이렇게 돼있지 않는다는 것이다.

주요함수 자체는 begin, end, insert, clear, erase, find, size 등 map이랑 사실상 똑같다. 그래서 추가적으로 설명하진 않겠다.

말이 좀 뒤죽박죽인데, 결론적으로 unordered_map은 map과 비교했을 때 더 많은 양의 데이터를 저장할 때, 그리고 더 빠른 속도를 원할 때 사용하고, 해쉬테이블 기반의 stl이라는 정보 정도만 알아놔도 충분할 것 같다. 사실 이 데이터의 양이라는게 주관적이라서 선택 자체도 약간은 주관적일 것이다. 사실 map도 빠른편인지라, map을 썼다고 백준 문제에서 시간 초과가 나는 경우도 사실상 없어서...그냥 딱 보고 데이터 범위가 꽤 큰 것 같다면 unordered_map을, 아니면 좀 더 일반적인 map을 사용하면 될 것 같다!