[STL] Map

STL map

 

map은 key, value 페어로 이루어진 자료 구조입니다.

• Key에 대한 중복이 없습니다.
• 레드블랙 트리(Red-Black Tree 이하 RB Tree) 기반으로 되어있기 때문에 모든 데이터는 정렬되어 저장됩니다.
  • 빠른 검색 속도를 가집니다. ( $ O(\log(N)) $ )
• 인덱스가 따로 존재하지 않기 때문에 iterator를 사용합니다.

 

선언

• map <key, value>: key와 value를 pair 형태로 선언합니다.

 

Method

• begin(): beginning iterator를 반환
• end(): end iterator를 반환

• insert(make_pair(key,value): 맵에 원소를 pair 형태로 추가
• erase(key): 맵에서 key(키값)에 해당하는 원소 삭제
• clear(): 맵의 원소들 모두 삭제
• find(key): key(키값)에 해당하는 iterator를 반환, 못찾으면 end() iterator를 반환
• count(key): key(키값)에 해당하는 원소들(value들)의 개수를 반환
• empty(): 맵이 비어있으면 true 아니면 false를 반환
• size(): 맵 원소들의 수를 반환

 

구현 (C++)

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

using namespace std;


int main(){

	map <string, int > m;


	// insert(key,value)
	m.insert(make_pair("a", 1));
  	m.insert(make_pair("dest", 1));
	m["f"] = 6;


	// erase(key)
	m.erase("a");


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


	// find(key)
	if (m.find("src") == m.end()) cout << "Not found" << endl;


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


	map <string, int>::iterator it;

	for(it = m.begin(); it != m.end(); it++){
		cout << "m[" << it->first << "]: " << it->second << '\n';
	}

	return 0;

}

 

 

Unordered_map

map과 완전히 유사하나 자동으로 정렬되지 않는다는 점에서 차이가 있습니다. map의 경우요소 삽입, 제거가 빈번할 경우에는 성능이 저하됩니다. 그래서 그부분을 해결하기 위해 나온 것이 unordered_map입니다.

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
  unordered_map <string, int> scores;
  
  scores["doong"] = 100;
  scores["blue"] = 110;
  scores["yebali"] = 120;
  
  for (auto it = scores.begin(); it != scores.end(); ++it) {
    cout << it->first << " : " << it->second << endl;
  }
  
  return 0;
}

 

 

map과 unordered_map의 차이점

map과 unordered_map은 사용하는 방법은 완전 동일하므로 뭘 쓰든 상관없다.

게다가 적은 데이터라면 큰 차이도 안나므로 뭘 쓰건 상관없다.

 

- map은 균형트리인 red black tree로 구현

- unordered_map은 해시 테이블로 구현

 

hash table은 값이 많아지면 비둘기집의 원리에 의해서 필연적으로 해쉬충돌이 일어나고 그러면 한 해시버킷에 충돌적재가 일어나서 결국에 성능은 떨어지게 된다는 것이다. 테스트를 해보면 자료가 늘어나면 늘어날수록 성능은 unordered_map이 떨어진다.

 

데이터가 작다면 unordered_map이, 크다면 map이 유리하다.