[C++] std::map

<정의>

- map은 각 노드가 key와 value 쌍으로 이루어진 트리이다.(중복 허용 x)

- map은 first, second가 있는 pair 객체로 저장되는 데 first- key로 second- value로 저장된다.

- C++의 map의 내부 구현은 검색, 삽입, 삭제가 O(logn) 인 레드블랙트리로 구성되어 있다.

<형태>

map <key, value> map1;

 

<정렬 방법>

- map은 자료를 저장할때 내부에서 자동으로 정렬한다.

- map은 key를 기준으로 정렬하며 오름차순으로 정렬한다.

- 내림차순으로 정렬하고 싶은 경우: map <int, int, greater> map1; 

(만약 다른 방법으로 int데이터를 내림차순으로 정렬하고 싶을 경우, 데이터에 '-'를 붙여 삽입하여 처리하면 내림차순으로 정렬된다.)

 

<map 사용법>

1. 헤더 포함

- map을 사용하려면 헤더에 #include <map> 처리를 해야한다.

 

2. map 선언하기

- map의 기본 구조는 map <key type, value type> 이름이다.

#include <map>
map<string, int> m;

 

3. 데이터 찾기 (find)

- map에서 데이터를 찾을 때는 iterator을 사용한다.

- 데이터를 끝까지 찾지 못했을 경우, iterator는 map.end()를 반환한다.

if (m.find("Alice") != m.end())
	cout << "find" << endl;
else 
	cout << "not find" << endl;

 

4. 데이터 삽입 (insert, operator[])

- map은 중복을 허용하지 않는다. insert를 수행할때, key가 중복되면 insert가 수행되지 않는다.

- 중복되면 그것은 key의 역할을 제대로 하지 않는다.

//함수 원형
pair insert( const value_type& _Val ); 
iterator insert( iterator _Where, const value_type& _Val );
template void insert( InputIterator _First, InputIterator _Last );

map<string, int> m;

m.insert({"Cam", 300});	//insert()
m[Cam]=300;	//operator[]

5. 반복문 데이터 접근 (first, second)

- 인덱스 기반 반복문 활용: 인덱스 기반은 iterator을  활용하여 begin()부터 end()까지 찾는다.

//인덱스기반
for (auto iter = m.begin() ; iter !=  m.end(); iter++)
	cout << iter->first << " " << iter->second << endl;
cout << endl;

- 범위 기반 반복문 활용

for (auto iter : m)
	cout << iter.first << " " << iter.second << endl;

 

6. map에서 삭제하기 (erase, clear)

- 특정 위치의 요소 삭제

m.erase(m.begin()+2);

- key값을 기준으로 요소 삭제

m.erase("Alice");

- map의 모든 요소 삭제

m.erase(m.begin(), m.end());	//1
m.clear();	//2

 

7. map 사용 예제 (삽입, 찾기, 반복문 구현)

#include <iostream>
#include <map>
using namespace std;
map<string, int> mapset;
int main(void) {

	mapset.insert({ "Alice", 100 });
	mapset[Bob] = 200;
    
	string s;
	cin >> s;
	mapset[s]++;	//mapset[s]가 없다면 mapset[s]=0으로 만들고 나서 ++연산자를 실행한다.

	if (mapset.find("Alice") != mapset.end()) 
		cout << "find" << endl;
	else
		cout << "not find" << endl;

	//인덱스기반
	for (auto iter = mapset.begin() ; iter !=  mapset.end(); iter++)
		cout << iter->first << " " << iter->second << endl;
	cout << endl;

	//범위기반
	for (auto iter : mapset)
		cout << iter.first << " " << iter.second << endl;

	return 0;
}