[C++/STL] Map 분석

가끔 꼭 필요한 Map 컨테이너에 대해서 알아보겠습니다.

Map에 대한 정보는 C++ Reference를 참고했습니다.

www.cplusplus.com/reference/map/map/?kw=map

map - C++ Reference

---

1. Map의 특성

Map은 Key와 Value의 쌍을 특별한 순서로 저장하고 있는 연관 컨테이너(associative container)입니다.

이진 트리로 구현되어있고, Key를 통해 Value에 접근하고자 할 때, [] 연산자를 사용해서 접근할 수 있습니다.

 

2. Map의 구성

 

2.1) 생성자

생성자는 크게 기본 생성자, 복사 생성자가 있습니다.

그리고 비교자 클래스를 사용해서 하고 싶은 정렬 방법을 결정할 수 있습니다.

 

map은 대부분 기본 생성자를 많이 씁니다.

삽입 부분은 뒤에서 자세히 다루겠습니다.

 

우선순위 큐처럼 비교자 클래스를 정의하여 정렬순서를 조정할 수 있습니다. 정렬 대상은 key입니다.

#include <iostream>
#include <map>
#include <string>
using namespace std;

struct mycomp {
	bool operator()(const string& left, const string& right)const {
		return  left > right;
	}
};

void PrintAll(const string &name, const map<string, int> &m)
{
	cout << "------" << name << "------\n";
	for (pair<string,int> item : m)
		cout << item.first << " -> " << item.second << '\n';

	cout << "\n\n";
	return;
}
void PrintAll(const string &name, const map<string, int, mycomp> &m)
{
	cout << "------" << name << "------\n";
	for (auto item : m)
		cout << item.first << " -> " << item.second << '\n';

	cout << "\n\n";
	return;
}
int main()
{
	map<string, int> m1;	//기본 생성자

	m1["First"] = 5;
	m1["Second"] = 6;
	m1.insert({ "Third",5 });
	m1.insert(make_pair("Forth", 40));

	PrintAll("m1", m1);

	map<string, int> m2(m1.begin(), m1.end());	//복사 생성자, 입력을 [iterator,iterator)로 받음.
	PrintAll("m2", m2);

	map<string, int> m3(m2); //복사 생성자. 입력을 다른 map으로 받음.
	PrintAll("m3", m3);

	map < string, int, mycomp> m4;	//기본 생성자. 비교자 클래스를 정의 후 연결

	m4["First"] = 5;
	m4["Second"] = 6;
	m4.insert({ "Third",5 });
	m4.insert(make_pair("Forth", 40));

	PrintAll("m4", m4);
	cout << "\n\n";

	return 0;
}

실행 결과

정렬 순서, 원리 등은 뒤에서 자세히 다루겠습니다. 지금은 삽입이 잘 이루어졌다는 것과, 복사생성자가 잘 동작한다는 것, 그리고 정렬이 잘 된다는 것만 확인하시면 됩니다.

 

2.2) 반복자

Map의 iterator도 역시 Bidirectional iterator입니다.

++, --연산까지 가능합니다.

 

또, 원소에 접근할 때 iterator와 더불어, []연산자를 사용해서도 접근 가능합니다.

#include <iostream>
#include <map>
#include <string>
using namespace std;

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

	m.insert({ "first",100 });
	m.insert({ "second",200 });
	m["third"] = 300;


	for (map<string, int> ::iterator iter = m.begin(); iter != m.end(); ++iter)
		cout << (*iter).first << " -> " << (*iter).second << '\n';

	cout << '\n';

	cout << "m[\"third\"] -> " << m["third"]<<"\n\n";

	return 0;
}

위 코드와 같이 iterator로 접근 가능하며, 대부분 auto로 받아서 씁니다. (원래는 위처럼 써야 합니다.)

밑의 [] 연산자로도 접근이 가능한 것을 밑의 실행 결과에서 볼 수 있습니다.

 

실행결과

 

 

 

2.3) 매서드

map은 데이터를 삽입하고 지우고, 찾고 하는 것이 대부분입니다. 그래서 이런 간단한 매서드를 위주로 한 번 살펴보겠습니다.

 

우선, 가장 필수적이면서 간단한 삽입, 삭제부터 보겠습니다.

삽입은 위의 코드에서도 나왔던 것처럼, []연산자를 이용해서 삽입할 수 있고, insert 매서드를 사용해서 삽입할 수 있습니다.

 

2.3.1) Insert

insert(삽입)은 예를 들어 <string, int> map일 때를 기준으로, 

std::pair< std:: map<string,int>::iterator , bool>를 반환합니다. std는 생략해도 되고(네임 스페이스를 std로 쓸 때만..)

 

첫 번째 반환 값인 iterator는 삽입한 곳을 가리키는 iterator입니다. 두 번째 bool은 해당 Key가 이미 map에 존재한다면 false, 그렇지 않고 성공적으로 삽입을 마쳤다면 true를 반환합니다.

 

이제 insert의 반환 값을 살펴봤으니 매개변수를 살펴봅시다.

 

매개변수에는

(1) 단순히 Key-Value쌍 하나만 들어가는 것과

(2) iterator, key-value쌍 이렇게 두 개의 매개변수가 들어가는 것,

(3) 다른 map의 iterator쌍이 들어갑니다. (map.begin(), map.end())하면 다른 map의 처음부터 끝까지 삽입.

 

보통 (1) 번을 많이 사용합니다. 필요에 따라 (3) 번도 사용하고...

(2) 번 같은 경우는 첫 번째 매개변수로 넣은 iterator이 hint가 되어서 조금 더 빨리 삽입을 할 수 있도록 한다..라고 Cplusplus reference에 나와있습니다. (정말 필요하신 분들만.. )

 

시간복잡도는 (1)이 log(n)입니다. 여기서 n은 map의 size입니다.

그래서 (3) 같은 경우는 범위의 길이 x log(n)만큼 시간을 소모하고,

(2)의 Hint를 사용하는 경우는 대부분 상수 시간에 삽입이 가능합니다.

 

#include <iostream>
#include <map>
#include <string>
using namespace std;

void PrintAll(const string &name, const map<string, int> &m)
{
	cout << "------" << name << "------\n";
	for (pair<string,int> item : m)
		cout << item.first << " -> " << item.second << '\n';

	cout << "\n\n";
	return;
}

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

	//(1) Key-Value쌍을 받는 insert
	m1.insert(pair<string,int> ("First", 100));
	m1.insert(make_pair("Second", 200));
	m1.insert({ "Third",300 });
	m1.insert({ "Forth",400 });

	PrintAll("map : m1", m1);

	//(2) Iterator의 범위를 받는 insert
	map<string, int> m2(m1.begin(), m1.find("Third"));
	PrintAll("map : m2", m2);
	
	return 0;
}

실행결과

(2)의 Insert를 봅시다.

범위가 [m1.begin(), m1.find("Third")) 가 됩니다. find는 해당 key를 가진 노드의 iterator를 반환해 줍니다.

그래서 Third까지는 포함이 되지 않은 것을 볼 수 있습니다.

 

2.3.1) Erase

 

삭제도 세 가지 버전이 있습니다.

(1) Iterator를 사용한 삭제

(2) Key값을 사용한 삭제

(3) Iterator 범위를 사용한 삭제입니다.

 

시간복잡도는

(1) amortized constant, 즉 거의 상수(O(1))라고 생각해도 되고,

(2) map의 size의 log형태로 비례. log(n)이라고 생각해도 됩니다.

(3) 범위 삭제는 범위의 길이 x log(n)이라고 생각하시면 됩니다.

 

#include <iostream>
#include <map>
#include <string>
using namespace std;

void PrintAll(const string &name, const map<string, int> &m)
{
	cout << "------" << name << "------\n";
	for (pair<string,int> item : m)
		cout << item.first << " -> " << item.second << '\n';

	cout << "\n\n";
	return;
}

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

	m1.insert({ "One", 1 });
	m1.insert({ "Two", 2 });
	m1.insert({ "Three", 3 });
	m1.insert({ "Four", 4 });
	m1.insert({ "Five", 5 });
	m1.insert({ "Six", 6 });
	m1.insert({ "Seven", 7});
	m1.insert({ "Eight", 8 });
	m1.insert({ "Nine", 9 });
		
	PrintAll("map : m1", m1);

	// (1) Iterator로 삭제
	cout << "(1) Iterator로 삭제" << '\n';
	auto iter = m1.find("Nine");
	m1.erase(iter);
	m1.erase(m1.find("Three"));
	PrintAll("map : m1", m1);

	// (2) Key로 삭제
	cout << "(2) Key로 삭제" << '\n';
	m1.erase("One");
	m1.erase("Four");
	PrintAll("map : m1", m1);

	// (3) Iterator 범위로 삭제
	cout << "(3) iterator 범위로 삭제" << '\n';
	m1.erase(m1.find("Seven"), m1.end());
	PrintAll("map : m1", m1);
	return 0;
}

 

(1) Iterator로 삭제한 경우입니다. find를 통해 해당 Key값을 갖는 노드의 Iterator를 반환받아, Iterator변수에 담고 매개변수로 넣을 수 있고, 아니면 바로 매개변수로 넣어줄 수 있습니다.

 

(2) Key로 삭제한 경우는 특별한 게 없습니다.

 

(3) 범위로 삭제한 경우는 삭제하고 싶은 부분의 Iterator를 구해서 범위로 입력하시면 됩니다.

 

실행 결과 입니다.

 

그 외, map의 데이터를 수정하는 매서드에 swap, clear 같은 매서드가 있는데 알아두면 좋지만 자주 사용하지는 않아서 적지는 않겠습니다. (글 서두에 있는 Cplusplus reference 홈페이지에 잘 나와있습니다.)

 

 

다음은 map의 데이터에 접근하는 매서드들을 살펴보겠습니다.

map의 데이터, 즉 Key를 통해서 Value값을 얻거나 해당 key를 가진 노드의 iterator를 얻는 행동을 말합니다.

 

key를 통해서 value값을 얻는 것은 []를 사용해서 얻을 수도 있고 Iterator의 .second를 통해서 접근할 수 있습니다.

 

 

 

2.3.3) Find, Count

find는 Key값을 통해 해당 Key값을 가지는 노드를 찾습니다.

매개변수는 Key값을 받고, 시간복잡도는 log(n)입니다. 여기서 n은 map의 size입니다.

 

find는 매개변수로 들어온 Key가 존재하면, 해당 노드의 Iterator, 그렇지 않으면 map:: end를 반환합니다.

 

Count 또한 key를 매개변수로 받고 시간복잡도는 log(n)입니다.

단, 반환 값이 해당 노드를 가리키는 Iterator가 아니고 존재하면 1, 그렇지 않다면 0을 반환한다는 점이 다릅니다.

 

사용처는 똑같습니다.

#include <iostream>
#include <map>
#include <string>
using namespace std;

void PrintAll(const string &name, const map<string, int> &m)
{
	cout << "------" << name << "------\n";
	for (pair<string,int> item : m)
		cout << item.first << " -> " << item.second << '\n';

	cout << "\n\n";
	return;
}

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

	m1.insert({ "One", 1 });
	m1.insert({ "Two", 2 });
	m1.insert({ "Three", 3 });
	m1.insert({ "Four", 4 });
	m1.insert({ "Five", 5 });
	m1.insert({ "Six", 6 });
	m1.insert({ "Seven", 7});
	m1.insert({ "Eight", 8 });
	m1.insert({ "Nine", 9 });
		
	PrintAll("map : m1", m1);

	//(1) []으로 접근
	cout << "m1[\"One\"] -> " <<m1["One"] << "\n\n";

	//(2) find로 접근
	cout <<"(*m1.find(\"Two\")).second -> "<<(*m1.find("Two")).second << "\n\n";

	//(3) Count로 존재 확인
	cout << "if (m1.count(\"Six\"))" << '\n';
	if (m1.count("Six"))
		cout << "있음\n\n";
	else
		cout << "없음\n\n";

	return 0;
}

 

실행결과

위의 코드와 같이 간단하게 접근 가능합니다.

 

 

그 외, lower_bound, upper_bound가 존재합니다. set 컨테이너에도 lower, upper bound 멤버 함수가 존재하는데, 기능은 똑같습니다. 

 

 

 

---

마치며...

어떤 문제들은 꼭 map을 사용해야 풀리거나 다른 컨테이너 말고 map을 사용하면 간단하고 빠르게 풀립니다.

 

원하는 대로 정렬하는 방법(비교자 클래스 작성법)만 알아도 크게 문제는 없습니다.

삽입 삭제, 찾기 등이 상당히 직관적이어서 간단합니다.

 

대부분 map을 만들어놓고 접근하는 용도로 쓰이기 때문에 데이터를 넣었다 뺐다가 막 하는 것도 덜합니다.

위의 간단한 내용들과 map이 대부분 log(n)의 속도로 실행되는 점만 알아도 충분하다고 생각합니다.

 

틀린 부분이나 수정할 부분이 있다면 댓글 언제든지 부탁드립니다.