강의 보고 공부한 것을 정리하는 목적으로 작성된 글이므로 틀린 점이 있을 수 있음에 양해 부탁드립니다. (피드백 환영입니다)
map은 Red Black Tree로 구현된 자료구조!! 드디어 사용해본다!!
map
map과 set은 짝꿍이긴하다!
하지만 보통 key랑 value를 묶어서 내기 때문에 map부터 시작하면 된다.
게임이라고 예시를 든다면
어떤 player가 있고 vector로 player를 관리한다면
#include <iostream>
using namespace std;
#include <vector>
#include <list>
#include <queue>
#include <map>
class Player
{
public:
Player() : _id(0) {}
Player(int id) : _id(id) {}
int _id = 0;
};
int main()
{
vector<Player> v;
v.push_back(Player(100));
v.push_back(Player(200));
v.push_back(Player(300));
v.push_back(Player(400));
v.push_back(Player(500));
}이런식으로 말이다.
✨잠깐!
우리가 이제 컨텐츠로 넘어간다면
int를 그대로 vector에 때려박는 것이 아니라!
객체자체를 vector에 넣어줄 것이다.
하지만 이때 고민해야하는 부분이 player에 id만 있는 것이아니라 다른 것들도 있다면 vector안에 player를 가지고 있는게 괜찮은 건가? 생각을 해봐야 한다.
void Test(vector<Player>& v)
{
}이런 함수를 사용할 때도 참조값을 넘기는 것이 성능이 더 좋아지기 때문에
우리가 나중에 실제로 작업을 하게 된다면
vector에 Player자체를 때려넣기 보다는 동적할당을 하여서 포인터로 들고 있게하여 사용한다.
vector<Player*> v;
v.push_back(new Player(100));
v.push_back(new Player(200));
v.push_back(new Player(300));
v.push_back(new Player(400));
v.push_back(new Player(500));이렇게 하지 않는다면 이사를 하는 과정에서 빈번하게 복사가 일어날 것이기 때문에 성능에 영향이 갈 수 있다.
포인터로 가지고 있으면 포인터는 하나의 정수에 불가하기 때문에 문제가 없다.
그래서 대부분은 정수(포인터)또는 스마트 포인터로 가지고 있는 것이 일반적이다.
물론 위처럼 관리를 하게 된다면 소멸시키는 것도 책임을 져야 한다.
자 그래서 본론으로 넘어가 본다면
id가 적절하게 섞여있고 특정 id를 찾아야 하는 상황이 온다면 이진 탐색을 이용하려면 정렬또한 되어 있어야하고 vector는 중간 추가/삭제가 어렵기에 한계가 있다.
그래서 Red Black Tree형태로 데이터를 관리하게 된다면 규형도 잘맞고 왼쪽은 작고 오른쪽은 크다라는 것이 보장되어 있기에 어떻게 본다면 만능형 자료구조가 생긴것이다.
그래서 (key, value)형태로 저장할 때 map를 사용할 수 있다.
사물함의 열쇠(key)와 사물함안에 넣은 물품(value)을 생각하면 편한다.
map<int, Player*> m;그래서 이런식으로 사용할 수 있다.
map을 이용하게 된다면 vector와 달리 연관형 컨테이너이기 때문에 데이터를 넣은데로 나오는 것이 아니라 정렬이 된 상태로 나오게 된다.
전에 배운 레드 블랙 트리를 생각하면 된다.
그래서 우리는 여기서
추가
찾기
삭제
순회
를 알아보면 된다.
추가
insert로 값을 넣을 수 있다.
값을 넣기 위해서는 key값과 value값을 하나하나 넣어주는 것이 아니라 짝을 맞춰서 넣어줘야 하는데
짝을 맞추는 방법은
std::pair<int, Player*> p;
m.insert(p);이런식으로 넣어줄 수 있다.
여기서 pair는 무엇이냐?
직접 만들어 본다면 이러한 느낌이다.
template<typename T, typename U>
struct Pair
{
T first;
U second;
};하지만 매번 이런식으로 pair를 만들어서 사용하면 힘들 수 있다.
뭐 한 번에
vector<Player*> v;
v.push_back(new Player(500));
v.push_back(new Player(100));
v.push_back(new Player(400));
v.push_back(new Player(200));
v.push_back(new Player(300));
map<int, Player*> m;
for (Player* p : v)
{
int key = p->_id;
Player* data = p;
m.insert(pair<int, Player*>(key, data));
}이런식으로 해줄 수도 있지만 매번 치는 것이 힘들 수 있다..
여기서 template에 쩌는 기능이 있다.
template<typename T, typename U>
auto MakePair(T frist, U second)
{
return std::pair<T, U>(first, second);
}이런식의 함수를 만들어서 <>이 부분을 생략하고 만들 수 있게 해주는 함수를 cpp에서 지원해준다.
m.insert(make_pair(key, data));이런식으로 사용할 수 있다.
for (Player* p : v)
{
m.insert(make_pair(p->_id, p));
}그래서 나중에 익숙해 진다면 이런식으로 사용할 수 있다.
찾기
vector는 하나하나 순회를 하면서 찾는것 뿐이였다.
하지만 map은 레드 블랙 트리로 정렬이 되어 있기때문에 순회를 하면서 찾을 필요가 없다.
그래서 find라는 함수가 존재한다.
만약 id가 300인 player를 찾고 싶다면
m.find(300);으로 해줄 수 있다.
반환값은
map<int, Player*>::iterator it = m.find(300);이런형식으로 된다.
하지만 우리는 auto를 배웠기 때문에
auto it = m.find(300);캬! 이런식으로 사용할 수 있다.
그래서 가져와서 데이터를 추출하기 위해서
auto whoami = *it;이런식으로 가져온다면 key와 value의 짝이라는것을 알 수 있다.
그래서
whoami.first; // key값
whoami.second; // value값이렇게 두 값을 가져올 수 있다는 것을 알 수 있다.
만약 한 번에 꺼내고 싶다면
int key = (*it).first;
Player* value = (*it).second;이런식으로 꺼내줄 수 있다.
그리고 여기서 우리가 예전에 배운 포인터를 사용할 때
(*it).first는 (순간이동 + 덧셈)이기 때문에
it->first로 축약하여 사용할 수 있다.
int key = it->first;
Player* value = it->second;이런식으로 말이다.
하지만 찾는 데이터가 없다면 vector와 동일하게
auto it = m.find(300);
if(it != m.end())
{
int key = it->first;
Player* value = it->second;
cout << "데이터 찾음" << endl;
}
else
{
cout << "데이터 없음" << endl;
}이런식으로 판별해줄 수 있다.
그럼 m.find의 시간 복잡도는 얼마일까?
우리가 이러한 짓을 하였던 이유는 우리가 조금이라도 성능적으로 이득을 보기 위해서 하였던 것이다.
레드 블랙 트리이기 때문에 O(logN)이라고 볼 수 있다.
(항상 중간 정도에 위치하기 때문이다)
그래서 우리가 데이터를 관리할 때 더 빠른 수단을 얻었다고 볼 수 있다.
삭제
vector같은 경우는 쭉 스캔하면서 iterator를 찾아가지고 삭제를 했어야 했지만
map은 erase를 사용하여서 key값으로 삭제를 할 수 있다.
m.erase(200);만약 찾은 것을 지우고 싶다면
m.erase(it)l이렇게 iterator형식으로도 지워줄 수 있다.
순회
순회는 vector와 같이
for(auto it = m.begin(); it != m.end(); it++)
{
int key = it->first;
Player* p = it->second;
}이런식으로 순회를 돌 수 있다
그럼 map으로 순회를 하면 효율적일까?
순회에서는 장점이 딱히 없다.
조심할 점?
우리가 데이터를 찾을 때 find를 이용해서 찾을 수도 있지만,
조금 더 빠르고 많이 사용하는 임의접근을 이용해서 찾을 수도 있다.
Player* p = m[100]; // key값하지만 이 방식은 조심해야 할 점이 있다.
C++ STL과 UE Tmap이 조금 다르다.
만약에 없는 key값을 넣게 된다면
C++에서는 갖고 오되, 없으면 기본값으로 추가를 시켜버린다. (의도적으로 사용하지 않았다면 안좋다)
UE에서는 바로 크래시를 낸다.
마무리
결국에 우리는 이 세부적인 상항을 하나하나 외울 것이 아니라(어차피 작업할 때 구글링을 하면서 사용하다보면 자연스럽게 사용가능하게 된다) 우리가 컨테이너를 고를 때 장점을 바탕으로 선택할 수만 있으면 된다.
정리를 해보자면 map은 데이터를 빠르게 서칭할 수 있게 도와주는 컨테이너라는 것을 알 수 있다.
그리고 C++ vector = C# list이고 C++ hash_map = C# Dictionary이다.
우리가 다음에 배울게 hashmap인데 c#에서는 거의 Dictionary를 사용한다.
그래서 다음시간에 공부를 하면서 map과 hashmap의 차이를 이해해야지 컨테이너를 고르기 수월하다.
그래도 hashmap은 어려운 개념은 아니다.
