[C++] STL <map> 라이브러리

map은 데이터를 key-value 형태로 저장하는 자료구조이다.

http://www.cplusplus.com/reference/map/map/

map - C++ Reference

 

map을 선언하는 방법은 다음과 같다.

map<int, int> m;

map은 템플릿 클래스이기 때문에 선언할 때 <> 사이에 key 값의 타입, value 값의 타입을 순서대로 적어줘야 한다.

key 타입과 value 타입이 같지 않아도 된다.

map<int, string> m;

이렇게 타입이 달라도 상관없다.

 

이렇게 선언된 map에 데이터를 저장하고 싶다면

m[1] = "one";

이렇게 하면 된다.

크기가 확보된 것도 아닌데 빈 map 객체인데도 이렇게 인덱스로 저장이 가능하다.

벡터의 경우에 데이터를 추가하고 싶다면 push_back() 함수를 써야 하고 set의 경우에는 insert() 함수를 써서 데이터를 추가할 수 있었는데 map은 원래 1이라는 인덱스가 있는 것처럼 저렇게 key 값을 [ ] 사이에 적고 그 키 값에 해당하는 value 값을 대입해주면 된다.

다만 주의할 것은 map이라는 자료구조는 key를 통해서 원하는 값을 꺼내오는 것이기 때문에 key 값은 유일한 값이어야 한다. 즉 key 값들 끼리는 중복이 없어야 한다. 다음 코드를 보자.

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


int main() {
	map<string, int> m;
	m["김철수"] = 15;
	m["김영희"] = 23;
	cout << "철수의 나이: " << m["김철수"] << endl;
	cout << "영희의 나이: " << m["김영희"] << endl;
	return 0;
}

이런 코드가 있을 때 이 코드를 실행하면

이렇게 철수와 영희의 나이가 제대로 출력된 것을 볼 수 있다.

 

하지만 10살짜리 김철수라는 동명이인이 있어서 map에 이 김철수의 데이터를 추가하면 어떻게 될까?

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


int main() {
	map<string, int> m;
	m["김철수"] = 15;
	m["김영희"] = 23;
	m["김철수"] = 10; //새로 추가된 10살짜리 김철수
	cout << "철수의 나이: " << m["김철수"] << endl;
	cout << "영희의 나이: " << m["김영희"] << endl;
	cout << "철수의 나이: " << m["김철수"] << endl;
	return 0;
}

 

새로운 김철수가 추가된 것이 아니라 원래 있던 15짜리 철수의 나이가 10살로 바뀐 것을 볼 수 있다.

따라서 map을 사용할 때 key는 중복될 수도 있는 데이터가 아니라 unique한 데이터를 key 값으로 하는 것이 좋다. 만약 이 예제처럼 했다면 나도 모르게 이런 실수를 하고는 이상한 결과가 나온다고 코드를 붙잡고 끙끙댈 수가 있다.

 

이제 map 객체 선언 방법과 map에 데이터를 추가하는 방법을 알았으니 유용한 함수들을 알아보자.

+size(): size_type	map에 저장된 쌍의 개수를 반환한다.
+empty(): bool	map이 비어있는지 아닌지 반환한다.
+find(k: key_type): iterator	키값인 key가 있으면 그 iterator 반환, 없으면 end() 반환
+count(k: key_type): size_type	k라는 키값을 가진 key의 개수를 반환한다. (0또는 1 반환)
+insert(pair<key_type, value_type>)	pair의 first 값을 key로, second 값을 value로 가지는 쌍을 map 객체에 추가
+erase(k: key_type): size_type	해당 키 값을 가진 데이터를 삭제한다.
+erase(position: iterator): iterator	해당 iterator 위치에 있는 원소를 삭제한다.
+begin(): iterator	map 객체의 시작 주소를 반환한다.
+end(): iterator	map 객체의 가장 끝 원소의 다음 주소를 반환한다.

count() 함수는 사실 find() 함수로 대체할 수 있다. count() 함수는 해당 키 값을 가진 key의 개수를 반환한다고는 하지만 key 값들은 서로 중복이 없는 유일한 값이기 때문에 많아봤자 최대 1을 반환한다.

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


int main() {
	map<string, int> m;
	cout << "m의 크기: " << m.size() << endl; // 0 출력
	cout << "m은 비어있습니까? " << (m.empty() ? "true" : "false") << endl; //true 출력
	m["김철수"] = 15;
	m["김영희"] = 23;
	cout << "m의 크기: " << m.size() << endl; //2 출력
	m.insert(make_pair("홍길동", 40));
	cout << "홍길동의 나이: " << m["홍길동"] << endl; //40 출력
	cout << ((m.find("김철수") != m.end()) ? "m에 김철수 있습니다." : "m에 김철수 없습니다.") << endl;
	map<string, int>::iterator iter = m.find("김철수");
	if (iter != m.end()) cout << "김철수의 나이: " << iter->second << endl; // 주소는 -> 연산자를 통해 접근. (*iter).second도 가능
	cout << ((m.find("김민지") != m.end()) ? "m에 김민지 있습니다." : "m에 김민지 없습니다.") << endl;
	cout << "삭제 전: " << ((m.find("김철수") != m.end()) ? "m에 김철수 있습니다." : "m에 김철수 없습니다.") << endl;
	m.erase(iter); //iterator를 이용해 삭제
	cout << "삭제 후: " << ((m.find("김철수") != m.end()) ? "m에 김철수 있습니다." : "m에 김철수 없습니다.") << endl;
	cout << "삭제 전: " << ((m.find("홍길동") != m.end()) ? "m에 홍길동 있습니다." : "m에 홍길동 없습니다.") << endl;
	m.erase("홍길동"); //key 값으로 삭제
	cout << "삭제 후: " << ((m.find("홍길동") != m.end()) ? "m에 홍길동 있습니다." : "m에 홍길동 없습니다.") << endl;
	return 0;
}

이 코드를 실행하면 다음과 같은 결과가 나온다.

 

함수들의 사용법은 매우 간단하기 때문에 이 예제 코드와 실행 결과만 봐도 알 수 있을 것이라 생각된다.

 

그럼 이제 map에 저장된 모든 데이터 쌍을 순회하는 법을 알아보자.

배열이나 벡터 같은 경우는 for(int i = 0; i < n; i++) 이 문장으로 모든 것이 가능했다. 이렇게 하고 for문 안에서 i를 인덱스로 해서 그 인덱스에 해당하는 원소에 접근할 수 있었다. 하지만 map은 인덱스로 접근이 불가능하고 key 값으로 접근이 가능한 자료구조이기 때문에 순회를 하려면 iterator를 사용해야 한다.

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


int main() {
	map<string, int> m;
	m["김철수"] = 15;
	m["김영희"] = 23;
	m["홍길동"] = 40;
	for (map<string, int>::iterator iter = m.begin(); iter != m.end(); iter++) {
		cout << "이름: " << iter->first << ", 나이: " << iter->second << endl;
	}
	return 0;
}

for(int i = 0; i < n; i++) 대신에 for(map<string, int>::iterator iter = m.begin(); iter != m.end(); iter++)를 쓰는데

for(map<string, int>::iterator iter = m.begin(); iter != m.end(); iter++)

이 코드 꼭 알아두자.

iterator는 주소이기 때문에 iter.first가 아니라 iter->first 또는 (*iter).first로 접근이 가능하다.

 

예를 들어 하나의 원소가 8바이트인 map 객체가 있는데 3개의 쌍이 들어있고 map의 시작 주소는 1000이라고 하자.

그러면 첫 번째 원소는 1000번지~1007번지 이렇게 8바이트에 걸쳐서 저장되어 있다.

두 번째 원소는 1008번지~1015번지에, 세 번째 원소 즉 마지막 원소는 1016번지~1023번지에 저장되어 있을 것이다.

iterator 변수인 iter를 iter++를 하면 iter가 가지고 있는 주소는 8바이트씩 증가한다.

즉 처음에 iter=m.begin() 이렇게 선언되었을 때 iter는 1000, for문을 한 번 돌고 나면 iter++에 의해 1008이 되고, 그 다음 for문을 돌면서 1016이 된다. 그리고 iter++에 의해서 1024가 된다. 이 1024가 바로 m.end()이다.

그렇게 for문을 돌면서 순회하다가 for문에서 조건 체크를 한다. iter != m.end()이어야 for문의 body 부분으로 들어갈 수 있는데 1024는 m.end()이다. 따라서 for문을 빠져나가게 되는 것이다.

포인터에 대해 익숙치 않은 분이라면 https://breakcoding.tistory.com/81

[C++] 포인터

이 글을 먼저 보고 오시는 것을 추천드린다.

 

그래서 아까 find() 함수를 사용할 때에도

if(m.find("홍길동") != m.end())

이런 식으로 사용했던 것이다. find() 함수는 iterator가 map을 순회하면서 find()의 매개변수로 들어온 그 key 값을 가진 원소가 있는지 찾는 것인데 m.end()까지 탐색해보고 없으면 멈추는 것이기 때문이다.

(선형 탐색을 하는 것처럼 말했지만 사실 map은 항상 정렬되어 있기 때문에 선형탐색이 아니라 이진탐색을 해서 find() 함수의 시간 복잡도는 로그 복잡도를 가진다.)

 

STL 라이브러리를 알아두면 굉장히 유용하므로 자주 쓰이는 함수, 순회하는 방법은 꼭 알아두자.

더 많은 함수를 알고 싶다면 http://www.cplusplus.com/reference/map/map/

map - C++ Reference

이 사이트에 직접 들어가서 보는 것을 추천한다.