[C에서 C++로 넘어가기] - 8. map, unordered_map

C++에서 사용가능한 컨테이너인 map에 대해서 소개하겠습니다.

컨테이너가 무엇인지에 대해서는 아래 게시글에 설명이 있으니 참고해 주세요

https://sirius7.tistory.com/91

[C에서 C++로 넘어가기] - 6. vector

---

map이란?

 

map은 #include <map> 헤더를 선언한 후 사용 가능하며,

<key, value> 쌍으로 이루어진 자료구조의 하나입니다. 

 

map의 특징을 정리하면 다음과 같습니다.

• key를 first로, value를 second로 저장
• key 중복 허용 X
• vector처럼 자동으로 메모리를 할당함 (크기 지정 필요X)
• 이진 탐색 트리(BST) 기반
  • 탐색, 삽입, 삭제가 O(logn) 시간복잡도를 가짐
  • 삽입과 동시에 자동으로 정렬됨 → 삽입,삭제 빈번히 일어나는 경우 비효율적

원소를 탐색하는데 O(n) 시간이 걸리는 벡터와 달리

원소를 탐색하는데 O(logn) 시간복잡도를 가지기 때문에,

map은 원소를 빠른 시간내에 검색해야 할 때 주로 사용하게 됩니다.

 

---

map의 사용법

 

간단한 예제 코드는 다음과 같습니다.

#include<iostream>
#include<string>
#include<map>
using namespace std;

int main(void) {

	// 선언
	map<int, string> m1;

	// 삽입
	m1.insert(pair<int, string>(1, "samsung"));
	m1.insert(pair<int, string>(54, "apple"));
	// 이렇게도 삽입 가능
	m1[12] = "lg";
	m1[23] = "sony";

	// 탐색(접근)
	cout << m1.find(12)->first << " , " << m1.find(12)->second << "\n";
	cout << m1.find(54)->first << " , " << m1.find(54)->second << "\n";
	cout << m1[23] << "\n";

	cout << "\n";

	map<int, string>::iterator iter;
	for (iter = m1.begin(); iter != m1.end(); iter++) {
		cout << iter->first << " , " << iter->second << "\n";
	}

	// 삭제
	m1.erase(54);

	return 0;
}

 

• find(key)
  • map안에서 key를 찾으면 그에 대응하는 값을 참조로 반환한다.
  • key 값을 찾지 못한다면 end()를 호출한다

---

unordered_map

 

 

unordered_map의 특징

• #include <unordered_map>
• map과 달리 삽입, 삭제시 자동으로 정렬되지 않음
• 해시테이블 기반
  • O(1)의 탐색, 삽입, 삭제 속도
  • 최악의 경우는 O(n)시간 소요 (키 충돌이 빈번한 경우)

 

unordered_map은 해시테이블 기반이므로,

일반적으로 탐색, 삽입, 삭제가 O(1)시간에 일어나는 매우 빠른 컨테이너입니다.

따라서, 정렬이 필요하지 않은 경우에 유용하게 사용할 수 있습니다.

 

물론, 해시테이블 기반이므로 해시테이블의 단점인 키 충돌시 속도가 느려진다는 점이 있으며,

데이터가 적은 경우 다른 컨테이너 사용이 더 효율적입니다.