[C++] STL - deque, map, set, multimap, multiset

지금까지 포스팅한 vector와 list는 시퀀스 컨테이너, 데이터가 삽입하는 순서대로 나열되는 형태를 가졌다.

그 중 나머지 하나인 deque에 대해 알아보자.

deque

double-ended queue를 말한다. 실제로 많이 사용하는 경우는 크게 없다. 간단한 원리만 알아보도록 하자.

vector와 list를 합쳐놓은 STL이라고 생각할 수 있다. 동적 배열로 배열이 생성되고 그 영역을 넘어가게되면 새로운 영역을 만들어서 데이터를 추가한다. 그리고 이전 영역에서 새로운 영역을 가리켜서 동작한다.

#include <iostream> 
#include <deque>
#include <vector>

using namespace std;

int main()
{
	deque<int> dq;
	dq.push_back(1);
	dq.push_front(2);
	cout << dq[1];
	// vector와 마찬가지로 배열 기반으로 동작
	// 다만 메모리 할당 정책이 다르다.

	// vector [1 1 1]
	vector<int> v(3, 1);
	// deque [1 1 1]
	deque<int> dq2(3, 1);

	v.push_back(3);
	v.push_back(2);

	// [1 1 1 2]
	dq2.push_back(2);
	// [1 1 1 2] [2    ]
	dq2.push_back(2);

	// [3    ] [1 1 1 1] [2    ]
	dq2.push_front(3);
	// [3 3  ] [1 1 1 1] [2    ]
	dq2.push_front(3);

    return 0;
}

처음/끝 삽입 삭제도 빠르게 동작한다. 상자가 가득 차면 새로 만들고 넣으면 되기 때문이다.

중간 삽입 삭제는 데이터가 연속되어있기 때문에 vector와 동일하게 느리다는 사실이다.

map

map도 vector와 비슷하게 정말 많이 쓰이는 컨테이너중 하나이다. 연관 컨테이너 중 하나인 map은 왜 필요할까?

만약 vector를 이용해서 10만명의 플레이어를 관리한다고 생각해보자. 그리고 플레이어는 고유 번호를 가지고 있을 것이다. 그런데 랜덤한 플레이어가 5만명 정도 접속을 종료한다고 해보면 되게 삭제가 느린 vector는 되게 오래 걸릴 것이다. 그 후 만약 우리가 플레이어 고유번호가 2만인 플레이어를 찾고 싶다. 라고 한다면 vector를 하나하나 순회해서 데이터를 찾아야한다. 그렇게되면 매우 불리하고 느리게 서칭을할 것이기 때문에 손해를 보는 것이다.

 

map은 균형 이진 트리(AVL)로 이루어져있다. 자세한 내용은 알고리즘 포스팅때 다루겠다.

map 역시 list와 마치 node 형태로 이루어져있다. map은 data로 실제 value와 key로 설정되어 있다.

 

위의 플레이어를 vector로 관리하는걸 map으로 관리하려면 이렇게 할 수 있다.

map<int, Player*> m;

#include <iostream> 
#include <deque>
#include <vector>
#include <map>

class Player
{
public:
	Player(int id) : _id(id){}

	int _id;
};


using namespace std;

int main()
{
	srand((unsigned int)time(nullptr));
	map<int, Player*> m;
	// 10만명 입장
	for (int i = 0; i < 100000; i++)
	{
		m.insert(pair<int, Player*>(i, new Player(i)));
	}
	// 5만명 퇴장
	for (int i = 0; i < 50000; i++)
	{
		int randomValue = rand() % 50000;
		// erase by key
		// 만약 운이 나빠서 똑같은 번호가 나온다면 그냥 무시될것
		m.erase(randomValue);
	}

	// Q) ID = 2만인 Player를 찾고 싶다.
	// A) 매우 빠르게 찾을 수 있다.
	map<int,Player*>::iterator findIt = m.find(20000);
	if (findIt != m.end())
	{
		cout << "찾음" << endl;
	}
	else
	{
		cout << "못 찾음" << endl;
	}
    return 0;
}

데이터 찾는것을 엄청 빠르게 할 수 있다는 점이 장점이다.

	m.insert(make_pair(0, new Player(1)));
	m.insert(make_pair(0, new Player(0)));

만약 동일한 키가 있는데 insert를 한다면 어떤 일이 일어날까? 바로 데이터를 덮어쓰는 것이 아닌 그냥 false를 반환하고(iterator와 bool pair) 무시된다.

 

데이터 전체를 순회하는 방법은 다음과 같다.

#include <iostream> 
#include <deque>
#include <vector>
#include <map>

class Player
{
public:
	Player(int id) : _id(id){}

	int _id;
};


using namespace std;

int main()
{
	srand((unsigned int)time(nullptr));
	map<int, Player*> m;
	
	// 10만명 입장
	for (int i = 0; i < 100000; i++)
	{
		m.insert(pair<int, Player*>(i, new Player(i)));
	}
	
	for (map<int,Player*>::iterator it = m.begin();  it != m.end(); ++it)
	{
		pair<const int, Player*>& p = (*it);
		int key = it->first;
		Player* value = it->second;
		// 또는
		// int key = p.first;
		// Player* value = p.second;
		cout << key << " " << value->_id << endl;
	}

    return 0;
}

없으면 추가, 있으면 수정 하는 코드를 다음과 같이 할 수 있다.

map<int,Player*>::iterator findIt = m.find(20000);
if (findIt != m.end())
{
    cout << "수정" << endl;
}
else
{
    cout << "추가" << endl;
}

그런데 이 코드를 매번 하는 것은 되게 불필요하다. 그래서 기능하나를 제공하는데 [] 연산자를 오버로딩한 것이다.

m[20000] = value;

위의 코드랑 정확히 동일하게 동작한다. 20000이라는 키가 없다면 추가하고 value를 지정해준다. 20000이라는 키가 있다면 value로 수정한다.

단 조심해야할 것이 데이터를 찾고만 싶은 경우에는 find를 사용해야하는 것이다. 데이터를 찾고 싶은데 m[i] 등을 사용해버리면 값이 계속 추가될 것이다. 매우 조심하자.

 

set, multiset, multiset

map을 정말 많이 쓸것인데 나머지는 map을 이해했다면 전부 바로 이해할 수 있다.

set는 key가 결국엔 value인 경우의 map이다. map과 동일하게 동작하는데 pair가 아닌 key 값이 value인 형태인 것이다.

#include <iostream> 
#include <set>


using namespace std;

int main()
{
	set<int> s;
	// 삽입
	s.insert(10);
	// 삭제
	s.erase(30);
	// 찾기
	set<int>::iterator findIt = s.find(10);
	if (findIt != s.end())
	{
		cout << " 찾음 " << endl;
	}
	else
	{
		cout << " 못 찾 음" << endl;
	}
	// 순회
	for (set<int>::iterator it = s.begin();it != s.end(); ++it)
	{
		cout << *it << endl;
	}
    return 0;
}

multimap과 multiset은 map과 set과 동일한데 그냥 중복키를 허용하는 것에 그치지 않는다.

#include <iostream> 
#include <deque>
#include <vector>
#include <map>
#include <set>


using namespace std;

int main()
{
	multimap<int, int> mm;
	// 삽입
	mm.insert(make_pair(1, 100));
	mm.insert(make_pair(1, 500));
	mm.insert(make_pair(1, 200));
	mm.insert(make_pair(2, 300));
	
	// 키가 1인 데이터 전부 삭제
	unsigned int count = mm.erase(1);

	// 찾고 삭제
	multimap<int, int>::iterator findIt = mm.find(1);
	if (findIt != mm.end())
	{
		mm.erase(findIt);
	}
	// 키가 1인 값만 추출
	pair<multimap<int, int>::iterator, multimap<int, int>::iterator> itPair;
	itPair = mm.equal_range(1);
	for (multimap<int,int>::iterator it = itPair.first; it != itPair.second; ++it )
	{
		cout << it->first << " " << it->second << endl;
	}

	multiset<int> ms;
	ms.insert(100);
	ms.insert(100);
	ms.insert(100);
	ms.insert(400);
	ms.insert(400);

	multiset<int>::iterator findItSet = ms.find(100);
	pair<multiset<int>::iterator, multiset<int>::iterator> itSetPair;
	itSetPair = ms.equal_range(100);

	for (multiset<int>::iterator it = itSetPair.first; it != itSetPair.second; ++it)
	{
		cout << *it << endl;
	}
    return 0;
}