[C++] STL 연관 컨테이너 Map

# 맵 Map

map을 사용하기 위해서는 <map> 헤더파일을 추가해야합니다.

#include <map>

 

맵은 특정 순서에 따라 키 값과 매핑된 값의 조합으로 형성된 요소를 저장하는 연관 컨테이너입니다.

키 값, 매핑된 값 모두 다양한 데이터 타입을 가질 수 있습니다.

 

예를 들어, 주민등록번호를 키 값으로 이름을 매핑된 값으로 할 수도 있고,

이름을 키 값으로 주민등록번호를 매핑된 값으로 할 수도 있습니다.

 

하지만 주민등록번호를 키 값으로 할 경우 키 값이 고유한 값을 가지지만,

이름을 키 값으로 할 경우 동명이인이 있을 수 있어 고유한 값을 가지지 못하므로

이런 경우에는 map보다는 multimap을 사용하는 것이 좋겠습니다.

 

 

 

# map 클래스 템플릿의 정의

template < class Key,			// map::key_type
	class T, 			// map::mapped_type
	class Compare = less<Key>, 	// map::key_compare
	class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
	> class map;

map의 첫 번째 인수는 키 값의 클래스 유형,

두 번째 인수는 매핑된 값의 클래스 유형,

세 번째는 키 값의 비교 정렬을 위한 인수,

네 번째는 할당기 인수입니다.

 

정렬 관련 인수와, 할당기 관련 인수는 디폴트값이 있기 때문에 생략이 가능합니다.

따라서 map < 키 값 클래스, 매핑된 값 클래스> 변수명; 으로 선언 가능합니다.

 

# 생성자

#include <iostream>
#include <map>
using namespace std;
int main(){
	map<string, int> m;		// 빈 맵 생성자
	m["a"]=1;
	m["b"]=2;
	m["c"]=3;
	m["d"]=4;
	
	map<string, int> m2(m);	// 복사 생성자
	
	map<string, int>::iterator it;
	
	for(it=m2.begin(); it!=m2.end();it++)
		cout << it->first << "=" << it->second << endl;
	cout << "" << endl;
	
	map<string, int> m3(m2.begin(),m2.end());	// 구간 복사 생성자
	
	for(it=m3.begin(); it!=m3.end();it++)
		cout << it->first << "=" << it->second << endl;
	
	return 0;
}

a=1    // m2.begin()
b=2
c=3
d=4

a=1    // m3.begin()
b=2
c=3
d=4

 

 # map 멤버 함수 :: 삽입과 삭제

함 수	설 명
insert ( pair<char, int>('a', 10))	키 값인 문자 a 에 정수 10을 매핑하여 맵에 추가한다.
myMap['b']=20;	키 값인 문자 b 에 정수 20을 매핑하여 맵에 추가한다.
erase('a')	키 값 a인 맵 요소를 삭제한다.
erase(iterator::it)	반복자 it이 가리키는 맵 요소를 삭제한다.
swap(map2)	같은 맵 유형인 map2와 요소를 전부 교환한다.
clear()	map의 요소를 전부 삭제한다.
emplace('c', 30)	키 값인 문자 c 에 정수 30을 매핑하여 맵에 추가한다. insert() 처럼 새로운 맵 요소를 추가하지만, key와 value 생성자에 전송한 값을 구축하는 방식이다. pair를 만들지 않고 추가할 수 있어 간편하다.
emplace_hint(iterator::it, 'd', 40)	반복자 it의 위치에서 키 값인 문자 d와 정수 40을 매핑하여 맵에 추가한다. insert나 [ ] 로 삽입하게되면 O(log n)의 시간복잡도로 수행합니다. 반복자 it으로 hint를 주면 O(1)의 시간복잡도로 수행합니다.

* emplace(), emplace_hint()는 오래된 버전의 STL에서 작동하지 않을 수 있습니다. 최신 버전의 visual studio에서 테스트해보시길 권장합니다.

# 예제

#include <iostream>
#include <map>
using namespace std;
int main() {
	map<string, int>::iterator it;	// map의 유형과 같아야 합니다.

	map<string, int> m;		// iterator의 유형과 같아야 합니다.
	m.insert(pair<string, int>("a", 10));
	m["b"] = 20;
	m.emplace("c", 30);

	m.erase("b");

	m.emplace("d", 40);
	
	it = m.upper_bound("c");	// upper_bound는 c가 아닌 d를 가리킵니다.
	m.emplace_hint(it, "e", 50);	// d부터 시작해서 삽입하기 때문에 빠릅니다.

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

	m.clear();	// map의 모든 요소를 삭제합니다.
	if (m.empty())	// map의 요소가 비어있으면 true을 리턴합니다.
    	puts("비어있습니다.");	

	return 0;
}

 

# map 멤버 함수 :: 검색

함수	설명
empty()	map의 모든 요소를 삭제합니다.
size()	map이 가진 요소의 갯수를 리턴합니다.
max_size()	map이 가질 수 있는 최대 크기를 리턴합니다.
myMap["a"]	키 값 a와 매핑된 값에 접근합니다.
at("b")	키 값 a와 매핑된 값에 접근합니다.
find("c")	키 값 a인 요소를 가리키는 iterator를 리턴합니다.
count("d")	키 값이 c인 요소의 갯수를 리턴합니다.
lower_bound("b")	키 값이 b인 요소를 포함한 요소중에 첫 번째 요소를 가리키는 iterator를 리턴합니다. 이 경우에는 키 값이 b인 요소를 가리킵니다. multimap이었다면 여러개의 b 요소 중 가장 첫번째를 가리킵니다.
upper_bound("b")	키 값이 b인 요소를 포함한 요소들의 다음 요소들 중에 첫 번째 요소를 가리키는 iterator를 리턴합니다. 이 경우에는 키 값이 c인 요소를 가리킵니다. multimap이었다면 여러개의 b 요소 중 가장 마지막 것의 다음 요소를 가리킵니다.
equal_range("b")	키 값이 b인 요소들의 범위를 가리키는 iterator pair를 리턴합니다. iterator pair의 키 값으로 b 요소 중 시작하는 요소를 가리키는 iterator를 받고, 매핑된 값으로 마지막 b 요소의 다음 요소를 가리키는 iterator를 받습니다.

# 예제

#include <iostream>
#include <map>
using namespace std;
int main(){
	map<string, int>::iterator it;
	
	map<string, int> m;
	m["a"]=1;
	m["b"]=2;
	m["c"]=3;
	
	printf("size: %d\n", m.size());	// map이 가진 요소의 갯수
	printf("max_size: %d\n", m.max_size());	// map이 가질 수 있는 최대 크기
	
	printf("a=%d\n", m["a"]);	// a와 매핑된 값
	printf("b=%d\n", m.at("b"));	// b와 매핑된 값
	
	it = m.find("c");	// 키 값인 c인 요소를 가리키는 반복자 리턴
	printf("find %d\n", it->second);
	
	int x=m.count("a");	// 키 값이 a인 요소의 갯수
	printf("count %d\n", x);
	
	it = m.lower_bound("b");	// b요소 중 첫 번째 요소를 가리키는 반복자 리턴
	printf("lower_bound(\"b\") : %d\n", it->second);
	it = m.upper_bound("b");	// b요소 중 마지막 요소의 다음 요소를 가리키는 반복자 리턴
	printf("upper_bound(\"b\") : %d\n", it->second);
	
	// 맵을 가리킬 수 있는 반복자를 키값, 매핑된값으로 갖는 pair 변수를 선언
	pair<map<string, int>::iterator,map<string, int>::iterator> itPair;
	
	// 키 값이 b인 요소들의 범위
	itPair = m.equal_range("b");
	
	// pair의 키 값에는 키 값이 b인 요소중 첫번째 요소
	cout << itPair.first->first << " : " << itPair.first->second << endl;
	
	// pair의 매핑된 값에는 키 값이 b인 요소중 마지막 요소의 다음 요소
	cout << itPair.second->first << " : " << itPair.second->second << endl;
	
	return 0;
}

size: 3
max_size: 1431655765
a=1
b=2
find 3
count 1
lower_bound("b") : 2
upper_bound("b") : 3
b : 2
c : 3