STL, map

1. map 정의

한 데이터 아이템(키)에서 다른 것(값)으로 매핑을 할때 사용하는 자료 구조 입니다.

map 은 알아두면 굉장히 유용한 자료 구조입니다. 성능을 개선할때 map사용을 고려해보는게 좋습니다. n개의 원소가 있을 때 O(log n)의 시간 복잡도로 삽입, 삭제, 검색이 가능합니다.

MAP에 대한 기본적인것은 여기에서 다루지는 않고, MAP을 STL에서 사용하는 예제들로만 다룰 예정입니다. 

기본적인 상식은 MAP에서는 key가 중복되지 않습니다. key가 중복된다면 중복MAP을 이용해야합니다.

2. 사용 형태

map<key type, value type> map변수이름

예) map<int, int> map_variable;

값을 넣을때 

  map변수이름[key]=값

값을 읽을때

  map변수이름[key]

3. 메소드 종류

begin() :  첫 번째 원소의 iterator (반복자)를 반환한다. (map의 원소를 반복자를 이용해서 접근할때 사용한다.)

end() : 마지막 원소 다음의 반복자를 반환. (map의 원소를 반복자를 이용해서 접근할때 사용한다.)

clear() : 저장하고 있는 모든 원소를 삭제한다.

insert() : 원소를 추가한다. 이것 보다는 [] 형태를 사용하는것을 추천합니다.

find() : key와 관련된 원소의 반복자를 반환한다.  (단 찾지 못한 경우 end() 반복자를 반환한다)

size() : 원소의 개수를 반환한다.

erase() : 해당 원소를 삭제한다.

4. 예제

4.1 가장 기본 key, value가 모두 int,float

#include <map>
#include <iostream>

using namespace std;


int test1()
{
	// defination key type, value type
	map<int, float> mTest;
	
	// Add item
	mTest.insert(make_pair(1,1.1));
	mTest.insert(make_pair(1,2.1));
	mTest.insert(make_pair(50,3.1));
	mTest[50]=4.11; // 갱신 가능
	mTest.insert(make_pair(50,5.1)); // 갱신이 일어나지 않음
	
	cout << "mTest[50]:" << mTest[50] << endl;
	cout << "mTest.find(50)->first:" << mTest.find(50)->first << endl;
	cout << "mTest.find(50)->second:" << mTest.find(50)->second << endl;
	
	return 0;
}

int main()
{
	test1();
	return 0;
}

find의 리턴값은 iterator입니다. 키의 접근은 ->first , 값의 접근은 ->second를 사용합니다.

mTest[50]:4.11
mTest.find(50)->first:50
mTest.find(50)->second:4.11

4.2 begin(), end()예제

iterator(반복자)를 이용하여 구현합니다.

방법은 다음과 같은 형태를 사용합니다. map<int, float>::iterator iter;

#include <map>
#include <iostream>

using namespace std;

int test1()
{
	// defination key type, value type
	map<int, float> mTest;
	
	// Add item
	mTest.insert(make_pair(1,1.1));
	mTest.insert(make_pair(1,2.1));
	mTest.insert(make_pair(50,3.1));
	mTest[50]=4.11; // 갱신 가능
	mTest.insert(make_pair(50,5.1)); // 갱신이 일어나지 않음
	
	map<int, float>::iterator iter;
	for(iter = mTest.begin() ; iter!=mTest.end();iter++){
		cout << "iter->first:" << iter->first << endl;
		cout << "iter->second:" << iter->second << endl;
	}
	
	return 0;
}

int main()
{
	test1();
	return 0;
}

기존과 동일한 예제를 사용하였습니다.

iter->first:1
iter->second:1.1
iter->first:50
iter->second:4.11

4.3 key가 문자열인 경우

#include <map>
#include <iostream>

using namespace std;

int test1()
{
	{
		map<const char*, float> mTest;
		
		mTest["abc"]=1.11;
		mTest["ab"]=2.11;
		mTest["bbb"]=3.11;
		
		cout << mTest["ab"] << endl;
	}
	{
		map<char*, float> mTest;
		
		mTest[(char *)"abc"]=1.11;
		mTest[(char *)"ab"]=2.11;
		mTest[(char *)"bbb"]=3.11;
		
		cout << mTest[(char *)"ab"] << endl;
		
		char buf[20];
		buf[0]='a';
		buf[1]='b';
		buf[2]=0;
		cout << buf << endl;
		cout << mTest[buf] << endl;
	}
	
	return 0;
}

int main()
{
	test1();
	return 0;
}

문자열을 다루는것인데 이번에는 좀 더 복잡한 예제입니다. 쉽게 생각하면 map에 const char type 키로 만들고 예제를 만들어 보았습니다. 결과 확인해보면 정상적으로 나옵니다.

두번째 예제는 string 변형을 하기위해서 const를 제거한 char type으로 해봤습니다.

2.11
2.11
ab
0

cout << mTest["ab"] << endl;

cout << mTest[(char *)"ab"] << endl;

위와 같이 표현하고 있는 부분에서는 정상적으로 2.11 이 출력되었습니다만 아래쪽 buf로 만든 곳에서는 0이 출력되었습니다. 분명 map에는 정상적으로 "ab"가 전달 되었을 텐데......

이것이 map 사용시 주의해야할 점입니다.

위와 같이 사용하면 map에 char *의 포인터값을 key를 생성합니다. 그말은 즉 포인터 주소를 이용해서 map을 만들게 되고 해당 포인터의 값에는 영향을 받지 않습니다. 그러면 "ab" 할때 정상적으로 나오는 부분은 컴파일러가 RO(Read only)변수들을 모아서 같은 주소로 매핑을 하기 때문에 같은 주소를 지니기 때문입니다.

이것을 잘생각해보면 구조체의 포인터나 클래스의 포인터를 이용하는 경우도 안된다는 것을 알 수 있습니다.

string의 경우 어떻게 해야할까요?

대표적인것이 아래 STL string을 이용하는 방법입니다. 

추가로 속도를 더 높이기 위해서는 string의 hash값만 저장해서 이용하는 방법도 있습니다.

4.4 key가 string인 경우

구현은 간단합니다. key에 string을 사용해 주는것입니다.

#include <map>
#include <iostream>
#include <string>

using namespace std;

int test1()
{
	{
		map<string, float> mTest;
		
		mTest[string("abc")]=1.11;
		mTest[string("ab")]=2.11;
		mTest[string("bbb")]=3.11;
		
		char buf[20];
		buf[0]='a';
		buf[1]='b';
		buf[2]=0;
		cout << buf << endl;
		cout << mTest[string(buf)] << endl;
	}

	return 0;
}
int main()
{
	test1();
	return 0;
}

값이 정상적으로 잘 나옵니다.

ab
2.11