[c++][자료구조] Map STL 정리 및 예제

◎ key , value 가 pair 형태로 연결되어 있는 자료 구조.

◎ 이진 탐색 트리의 일종이다. (레드 블랙 트리)
◎ 값을 찾을 때 시간 복잡도가 O(logN)으로 빠른 편이다.
◎ 삽입 / 삭제 할 때 시간 복잡도는 O(logN)으로 오래 걸린다.
◎ key 값을 기준으로 자동 정렬 되어 있다.
◎ key값이 중복 불가능 하다. 즉 , key 값이 유일하다.

◎ 메모리가 자동으로 동적 할당 된다.

 

STL 사용법

헤더 파일 

#include <map>

 

선언

 

map <int, string> m;

key , value 순으로 선언.

 

map <int , string ,greater<int>> m; // 내림차순

key 기준으로 기본 오름차순 이지만 greater를 사용하면 내림차순으로 바뀐다.

 

 

값 삽입 4가지 방법.

m.insert( {0,"zero"} );

m.insert(make_pair(1, "first")); // make pair 함수 사용

m.insert(pair<int,string>(2 , "second")); // pair 사용

m.emplace(4,"fourth"); // emplace로 효율적인 삽입

 

 

 

Index를 활용하는 방법

 

1) value 반환

map<int,int>m={ {1,100} ,{2,200} ,{3,300} };

cout<< m[2] << endl; // 200 출력

 

m[key 값] : key 값에 연결된 value 값을 반환한다.

 

 

2) 값 삽입

m[4] = 400 ; // {4,400} 이 추가 된다.

m[5]++; // {5,1} 이 추가 된다.

 

 

3) 값 수정

m[5] = 500; // (5,1) -> (5,500) 으로 바뀜

 

 

반복을 이용하여 데이터 접근

 

 

1) iter 사용

map<int , int > m = { {1,100} , {2,200} , {3,300} };
map<int , int> ::iterator iter;

for(iter = m.begin() ; iter != m.end() ; iter++){
	cout << iter->first << ' '<< iter->second << endl;
}

// 출력 : 
//1 100
//2 200
//3 300

 

2) 범위 기반 반복문 사용

map<int , int > m = { {1,100} , {2,200} , {3,300} };
map<int , int> ::iterator iter;

for(auto x : m){
	cout << x.first <<' ' << x.second << endl;
}


// 출력 : 
//1 100
//2 200
//3 300

 

 

기본 함수들

 

 

m.clear()      /      m.count(key)    /      m.empty()

map <int , string > m={ {1,"a"} , { 2,"b"} , {3,"c"} , {4,"d"} };

cout << m.count(1) << m.empty(); // 출력 : 1 0

m.clear(); // m = {}

cout << m.count(1) << m.empty(); // 출력 : 0 1

 

m.clear() : 모든 원소 삭제.

m.count(key) : key 원소 몇 개 있는지 반환. (Map 은 중복 X 이므로 없으면 0 , 있으면 1 반환)

m.empty() : 비어있으면 1 , 아니면 0 반환.

 

 

iterator 선언

 

map<int,string> :: iterator iter;

 

 

iterator를 반환 하는 함수

 

m.begin()      /      m.end()         /       m.rbegin()        /        m.rend()

map<int,int> m={ {1,100} , {2,200} , {3,300} };

cout << m.begin()->second << endl; // 출력 : 100
cout << m.end()->second << endl; // 출력 : 쓰레기 값
cout << m.rbegin()->second << endl; // 출력 : 300
cout << m.rend()->second << endl; // 출력 : 쓰레기 값

 

m.begin() : 맨 앞 원소 가리킴.

m.end() : 맨 마지막 원소의 바로 뒤를 가리킴.

m.rbegin() : m을 거꾸로 했을 때 맨 앞 원소를 가리킴.

m.rend() : m을 거꾸로 했을 때 마지막 원소의 바로 뒤를 가리킴.

 

 

m.insert( pair )     /      m.erase( iter )        /      m.erase(iter1 , iter2)

map<int,int> m = { {1,100} , {2,200} , {3,300} };

m.insert( {4,400} ); // (4,400) 삽입


//m.erase(3); // (3,300) 삭제
m.erase(m.begin()); // (1,100) 삭제
m.erase( m.begin() , m.end() ); // 모든 원소 삭제

 

m.erase(iter) : iter가 가리키는 원소 삭제.

m.erase(iter1,iter2) : iter1 ~ iter2 까지 삭제.

m.erase(key값) : key값에 해당하는 원소 삭제 (키 값으로도 삭제 가능.)

 

 

 

m.find(key 값) 

 

 

값이 있을 때

map<int,int> m = { {1,100} , {2,200} , {3,300} };
map<int,int>::iterator iter;

iter = m.find(3);
cout << iter->second ; // 300 출력

 

key 값을 가리키는 iterator 반환

 

 

값이 없을 때

map<int,int> m = { {1,100} , {2,200} , {3,300} };
map<int,int>::iterator iter;

iter = m.find(4);

if(iter==m.end()) cout << "Not Found.";
else{
	cout << iter->second;
}

// Not Found. 출력