[C++] STL map Container 사용 방법 정리 (feat. map & [hash_map]unordered_map & multi_map)

* 다음 포스팅은 STL map Container의 사용 방법 및

map & multimap & unordered_map[hash_map]에 관련된 내용을 포함하고 있습니다.

Hash Table에 관한 선수지식이 부족하신 분들은 다음 포스팅을 참고해 주세요.

→ [DataStructure] Hash 자료구조 개념 정리

 

* 개인적인 공부 내용을 기록하는 용도로 작성한 글 이기에 잘못된 내용을 포함하고 있을 수 있으며,

지속적으로 수정해 나갈 예정입니다.

---

_Contents

#1 About map container

#1.1 map & multimap

- map container Time Complexity

#1.2 unordered_map[hash_map]

- unordered_map Time-Complexity

- hash map

#1.3 map vs multimap vs unordered_map

#2 STL map container 사용법

-1 Declare 선언

-2 Insert 원소 삽입

-2.1 Insert Member Function

-2.2 std::operator::[]

-3 Search 원소 탐색

-4 Access 원소 접근

-5 Erase 원소 삭제

---

-2.2 std::operator::[] 관련 내용 추가 ... 2022-09-23

---

#1 About map container

오늘 설명드릴 map container는 Associative container 의 일종입니다. 

Associative container (연관 컨테이너) 는 객체를 일정한 규칙에 따라 조직화 하여 Key - Value 형태로 원소를 저장하며, Key 값을 통해 Value에 접근합니다.

따라서 map container도 마찬가지로 Key값을 이용해 빠르게 container의 value에 접근할 수 있지만 요소의 위치를 지정할 수는 없습니다.

 

#1.1 map & multimap

C++ STL은 다양한 형태의 map container를 제공합니다.

우선 map과 multi_map의 특징에 대해 정리해 보도록 하겠습니다.

첫 번째로 가장 기본이 되는 map 입니다. map은 key값을 기준으로 정렬된 상태로 자료를 저장합니다. 또한 key 값의 중복을 허용하지 않습니다.

반면에 multi_map은 컨테이너의 이름에서 유추할 수 있듯이 key 값의 중복을 허용합니다.

map과 multi_map은 Key 값의 중복 허용 여부만 다른 뿐 사용 방법은 동일합니다.

 

- map container Time Complexity

map과 multimap은 Red-Black-Tree 라는 균형 이진 트리 자료구조로 구현되어 있기에 삽입/삭제/탐색 연산이 O(logN)의 시간이 소요됩니다. 일반 이진 탐색 트리 자료구조는 최악의 경우 O(N)의 시간이 소요되기에 이러한 단점을 보완하기 위해 고안된 자료구조입니다.

 

다음은 map 컨테이너와 multimap 컨테이너를 선언하여 비교한 예제입니다. (map 컨테이너에 대한 자세한 사용법은 이어서 따로 정리할 예정이니, 지금은 출력 결과만 확인해 주세요.)

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

int main(){
	map<string, int> myMap;
	myMap.insert(pair<string, int>("Apple", 100));
	myMap.insert(pair<string, int>("Banana", 200));
	myMap.insert(pair<string, int>("Orange", 300));
	myMap.insert(pair<string, int>("Orange", 300));	
	for(const auto& i : myMap)
		cout << "[" << i.first << ", " << i.second << "]" << " ";
	
	multimap<string, int> myMultiMap;
	myMultiMap.insert(pair<string, int>("Apple", 100));
	myMultiMap.insert(pair<string, int>("Banana", 200));
	myMultiMap.insert(pair<string, int>("Orange", 300));
	myMultiMap.insert(pair<string, int>("Orange", 300));
	cout << '\n';
	for(const auto& i : myMultiMap)
		cout << "[" << i.first << ", " << i.second << "]" << " ";	
	return 0;
}

[Output]
[Apple, 100] [Banana, 200] [Orange, 300]
[Apple, 100] [Banana, 200] [Orange, 300] [Orange, 300]

출력 결과를 확인해 보면 map 으로 선언된 myMap은 중복된 Orange Key를 제거하지만 multimap 으로 선언된 myMultiMap 컨테이너는 중복된 Orange Key를 제거하지 않음을 확인할 수 있습니다.

 

#1.2 unordered_map

unordered_map은 C++11 버전 부터 추가된 컨테이너로 이름에서도 유추할 수 있듯이 정렬되지 않은 형태로 자료를 저장합니다.

map과 동일하게 자료의 중복을 허용하지 않습니다.

Red-Black-Tree로 구현된 map & multimap 컨테이너와 달리 Hash Table을 기반으로 구현되어 있습니다.

Hash Table이란 Key값을 Hash Function에 대입하여 Hash 값으로 바꾼 뒤, 추출한 Hash 값을 기반으로 데이터를 함께 저장하는 방식입니다.

Hash 자료구조에 대한 자세한 설명은 다음 게시글을 참고해 주세요

→ Hash 자료구조 개념 정리

 

- unordered_map Time-Complexity

Hash 자료구조를 기반으로 구현되어 있어 삽입/삭제/추가 연산이 O(1)시간이 소요됩니다. 따라서 자료가 많아질수록 unordered_map 컨테이너의 효율은 크게 증가합니다. 단, Hash Function 의존도가 높아 유사한 key값이 많아질 경우 해시 충돌이 발생할 수 있다는 단점이 있습니다.

 

다음은 map container와 unordered_map container를 비교한 예제입니다. 

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

int main(){
	map<string, int> myMap;
	myMap.insert(pair<string, int>("Apple", 100));
	myMap.insert(pair<string, int>("Banana", 200));
	myMap.insert(pair<string, int>("Orange", 300));
	myMap.insert(pair<string, int>("Orange", 300));	
	for(const auto& i : myMap)
		cout << "[" << i.first << ", " << i.second << "]" << " ";
	
	unordered_map<string, int> um;
	um.insert(pair<string, int>("Apple", 100));
	um.insert(pair<string, int>("Banana", 200));
	um.insert(pair<string, int>("Orange", 300));
	um.insert(pair<string, int>("Orange", 300));
	cout << '\n';
	for(const auto& i : um)
		cout << "[" << i.first << ", " << i.second << "]" << " ";	
	
	
	return 0;
}

[Result]
[Apple, 100] [Banana, 200] [Orange, 300]
[Orange, 300] [Apple, 100] [Banana, 200]

우선, 두 container 모두 중복된 Orange Key를 제거합니다.

그러나 입력된 Key 값을 ASCII 순으로 정렬하는 map container와 달리 unordered_map container는 자료를 오름차로 정렬하지 않습니다. 

 

- hash_map

hash_map은 C++ STL에서 제공하지 않는 비표준 컨테이너 입니다.

C++11 이전에는 프로그래머가 원하지 않아도 자동으로 자료가 정렬되는 std::map container를 사용해야 했기에 불필요한 오버헤드를 감수 해야만 했습니다.

따라서 프로그래머들은 namespace stdext에 존재하는 비표준 컨테이너인 hash_map을 사용했습니다.

그러나 C++11 표준부터 앞에서 소개드린 Hash Table로 구현된 std::unordered_map 이라는 새로운 컨테이너가 등장했습니다.

따라서 hash_map은 오늘날 사용되지 않게 되었습니다. (hash_map을 사용하고자 하면 할 수 있지만 사용 시 경고가 출력됩니다.)

그러므로 hash 자료구조로 구현된 map을 사용하고자 하신다면 unordered_map 컨테이너를 사용하시면 됩니다.

 

#1.3 map vs multimap vs unordered_map

1. map

- 원소를 Key값을 기준으로 자동으로 정렬한다.

- 중복을 허용하지 않는다.

- Red-Black-Tree 자료구조를 기반으로 설계되어 탐색/삭제/추가 연산이 평균 O(logN) 시간이 걸린다.

 

2. multimap

- 원소를 Key값을 기준으로 자동으로 정렬한다.

- 중복을 허용한다.

- Red-Black-Tree 자료구조를 기반으로 설계되어 탐색/삭제/추가 연산이 평균 O(logN) 시간이 걸린다.

 

3. unordered_map

- 원소를 자동으로 정렬하지 않는다.

- 중복을 허용하지 않는다.

- Hash Table을 기반으로 설계되어 탐색/삭제/추가 연산이 평균 O(1) 시간이 걸린다. (최악의 경우 O(logN))

---

#2 STL map container 사용법

map 컨테이너의 사용방법에 대해 간략하게 정리해 보도록 하겠습니다.

(unordered_map, multimap 의 사용법은 map과 동일하니 따로 정리하지 않겠습니다.)

 

우선 map container를 사용하기 위해선 map header를 include 해 줘야 합니다. (unordered_map 이라면 unordered_map header를 include 합니다.)

다음으로 std를 생략하기 위해 using namespace std; 를 작성해 네임스페이스를 생략합니다.

#include <map>
using namespace std;

 

1. Declare : 선언

map은 자료를 pair로 저장합니다.

STL pair에 대한 내용은 다음 포스팅에 정리되어 있습니다.

→ Pair Container 사용법 정리 With Vector, Typedef, sort

map<key, value> 변수이름 형태로 선언하며 first에 저장되는 값이 key  second에 저장되는 값이 value 입니다.

map<string, int> myMap;

 

2. Insert : 원소 삽입

2.1 Insert member function

map에 자료를 추가하는 연산은 insert member function을 사용합니다.

앞서 pair를 사용해 map을 선언했으니, 삽입 연산 또한 pair를 이용합니다.

	myMap.insert(pair<string, int>("Apple", 100));
	myMap.insert(pair<string, int>("Banana", 200));
	myMap.insert(pair<string, int>("Orange", 300));

 

2.2 std::map::operator[] 

Access element operaor [] 를 이용해 map에 key-value 쌍을 추가할 수 있습니다.

opeartor[]는 키에 접근할 때도 사용되며, map container에 키값이 존재하지 않는 경우 size를 1 증가시키고 새로운 key-value 원소를 추가합니다.

 

example code1) map에 key 값이 존재하는 경우

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

int main(){
	map<string,int> myMap;
	myMap.insert(pair<string,int>("Key1", 1));
	cout << "Key1 → " myMap["Key1"] << endl;
	return 0;
}

Key1 → 1

 

example code2) map에 key 값이 존재하지 않는 경우

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

int main(){
	map<string,int> myMap;
	myMap.insert(pair<string,int>("Key1", 1));
	// Key2의 Value를 따로 지정해 주지 않았기에 default-value 0으로 초기화 됩니다.
	cout << "Key2 → " << myMap["Key2"] << endl;
	myMap["Key3"] = 3;
	cout << "Key3 → " << myMap["Key3"] << endl;
	return 0; 
}

Key2 → 0
Key3 → 3

 

3. Search : 원소 탐색

map container의 자료를 탐색하는 방법은 2가지로 나뉩니다.

첫 번째는 iterator를 사용해 원소에 순차적으로 접근하는 방법 입니다.

	map<string, int>::iterator it;
	for(it = myMap.begin(); it != myMap.end(); it++)
		cout << "[" << (*it).first << ", " << it -> second << "]" << " ";

 

혹은 auto keyword와 C++11 버전 이상부터 추가된 Range-Based-For 문법을 활용하면 더 깔끔하게 원소에 접근할 수 있습니다.

	for(const auto& i : myMap)
		cout << "[" << i.first << ", " << i.second << "]" << " ";

range-based-for 문법에 대한 내용은 다음 포스팅을 참고해 주세요.

→ range-based-for 범위 기반 for문

 

4. Access : 원소 접근

map container는 map_name[key_name] 형태로 value에 접근 혹은 수정할 수 있습니다.

다음은 "Orange" Key 의 Value를 300에서 400으로 수정한 예시입니다.

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

int main(){
	map<string, int> myMap;
	myMap.insert(pair<string, int>("Apple", 100));
	myMap.insert(pair<string, int>("Banana", 200));
	myMap.insert(pair<string, int>("Orange", 300));
	myMap["Orange"] = 400;
	for(const auto& i : myMap)
		cout << "[" << i.first << ", " << i.second << "]" << " ";
	return 0;
}

[Output]
[Apple, 100] [Banana, 200] [Orange, 400]

 

5. Erase - 원소 삭제

- iterator로 원소를 지정하여 삭제하기

첫 번째는 erase 멤버함수의 인자를 iterator로 지정하여 삭제하는 방법입니다.

다음은 myMap의 첫 번째 Key 값인 Apple을 iterator로 지정한 뒤 erase 멤버 함수의 인자로 보내어 삭제한 에제입니다.

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

int main(){
	map<string, int> myMap;
	myMap.insert(pair<string, int>("Apple", 100));
	myMap.insert(pair<string, int>("Banana", 200));
	myMap.insert(pair<string, int>("Orange", 300));
	map<string, int>::iterator it = myMap.begin();
	myMap.erase(it);
	for(const auto& i : myMap)
		cout << "[" << i.first << ", " << i.second << "]" << " ";
	return 0;
}

[Output]
[Banana, 200] [Orange, 300]

 

- key값으로 원소를 지정하여 삭제하기

두 번째 방법은 erase 멤버함수의 인자로 키값을 보내어 삭제하는 방법입니다.

다음은 Banana Key를 erase 멤버함수의 인자로 보내어 삭제한 예시입니다.

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

int main(){
	map<string, int> myMap;
	myMap.insert(pair<string, int>("Apple", 100));
	myMap.insert(pair<string, int>("Banana", 200));
	myMap.insert(pair<string, int>("Orange", 300));
	myMap.erase("Banana");
	for(const auto& i : myMap)
		cout << "[" << i.first << ", " << i.second << "]" << " ";
	return 0;
}

[Output]
[Apple, 100] [Orange, 300]\

---

Related

→ map vs multimap