[c++] STL map container 사용

특징

1. pair형태로 저장 map<key, value> m;

ex) map<int, int> m; 

 

2. 노드 기반의 균형이진트리구조, logN의 검색속도 보장

 

3. key는 고유하다.  중복 불가능

 

4. key값을 기준으로! 자동 정렬된다.  default 는 오름차순

 

cf) unordered_map은 정렬되지 않은 map으로 hash table기반이고 map은 레드블랙트리 기반이다.

RB Tree(레드블랙트리)는 BST에 self-balancing 기능을 추가한 것으로 O(logN)을 보장하며 밸런싱된다.

참고: gracefulprograming.tistory.com/3

[C++] map vs hash_map(unordered_map)

기본형태

map<key, value>: key와 value를 pair의 형태로 선언한다.

ex) map<int, int> m1;

 

- iterator가 있다.

begin(): beginning iterator를 반환

end(): end iterator를 반환

for(auto i=m.begin(); i!=m.end(); i++)

 

- 추가 및 삭제 

insert(make_pair(key, value));

insert(pair<int, string>(key, value));

erase(key): key에 해당하는 원소 삭제

clear(): 맵의 원소들 모두 삭제

 

조회

find(key): key에 해당하는 iterator반환. 위치 반환 아님!

만약 존재하지 않는다면 map.end()와 같은 값을 리턴한다. 따라서 존재 여부를 확인하고 싶다면

if(map.find('key') != map.end()) //존재한다면

 

count(key) : key에 해당하는 원소들 개수를 반환

 

기타

empty(): if map is empty then return true, else return false

size(): 맵 원소들의 수 반환

 

코드 예시

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

using namespace std;

int main(){

	// map
	// <string, int> => <key, value>
	map< string, int > m;


	// insert(key,value)
	m.insert(make_pair("a", 1));
	m.insert(make_pair("b", 2));
	m.insert(make_pair("c", 3));
	m.insert(make_pair("d", 4));
	m.insert(make_pair("e", 5));
	m["f"] = 6; // also possible


	// erase(key)
	m.erase("d");
	m.erase("e");
	m.erase(m.find("f")); // also possible


	// empty(), size()
	if(!m.empty()) cout << "m size : " << m.size() << '\n';


	// find(key)
	cout << "a : " << m.find("a")->second << '\n';
	cout << "b : " << m.find("b")->second << '\n';


	// count(key)
	cout << "a count : " << m.count("a") << '\n';
	cout << "b count : " << m.count("b") << '\n';


	// begin(), end()
	cout << "traverse" << '\n';
    // map< string, int >::iterator it; also possible 
	for(auto it = m.begin(); it != m.end(); it++){
		cout << "key : " << it->first << " " << "value : " << it->second << '\n';
	}

	return 0;

}