[C++] STL - map, unordered_map

seunghyun·2023년 6월 28일

C++, 자료구조, 알고리즘

목록 보기

9/16

이전까지 시퀀스 컨테이너들 (vector, list) 에 대해서 다루어보았다. 시퀀스 컨테이너들은 말 그대로 '원소' 자체를 보관하는 컨테이너들이다.

이번에는 다른 종류의 컨테이너인 연관 컨테이너(associative container) 에 대해서 다루어본다. 연관 컨테이너는 시퀀스 컨테이너와는 다르게 키(key) - 값(value) 구조를 가진다. 다시 말해 특정한 키를 넣으면 이에 대응되는 값을 돌려준다 는 것이다. 물론 템플릿 라이브러리 이기 때문이 키와 값 모두 임의의 타입의 객체가 될 수 있다.

연관 컨테이너에는

특정 키가 연관 컨테이너에 존재하는지 유무를 확인할 수 있는 set 이 있고
특정 키에 대응되는 값이 무엇인지 질의할 수 있는 map이 있다.

C++ 에서는 위 두 가지 작업을 처리할 수 있는 연관 컨테이너라는 것을 제공한다. 물론 맵과 멀티맵을 셋 처럼 사용할 수 있다. 왜냐하면 해당하는 키가 맵에 존재하지 않으면 당연히 대응되는 값을 가져올 수 없기 때문이다.

하지만 맵의 경우 셋 보다 사용하는 메모리가 크기 때문에 키의 존재 유무 만 궁금하다면 셋을 사용하는 것이 좋다.

map

연관형 컨테이너 std::map 은 균형 이진 트리 (AVL) 이라는 자료구조로 구현되어 있으며, 키를 기준으로 정렬된 상태를 유지한다.

find( ) 의 시간복잡도 : O(logN)

std::map의 find() 함수를 사용하여 키를 검색하는 경우, 데이터 크기에 관계없이 빠른 검색 성능을 기대할 수 있다. find() 함수의 시간 복잡도는 O(log n)이다. 이는 이진 검색 트리의 특성에 따라 검색 대상이 저장된 요소들을 효율적으로 탐색할 수 있기 때문이다. 이진 검색 트리는 각 단계마다 현재 노드의 키와 찾고자 하는 키를 비교하여 다음에 이동할 방향을 결정하므로, 데이터의 크기에 비례하여 검색 시간이 로그 시간 복잡도로 감소한다.

추가, 삭제, 찾기를 하는 방법을 코드로 살펴보며 std::map 에 대해 자세히 알아보자!


/* 선언 */
map<int, Player*> m;

// -----------------------------------------

/* 추가 */
for (Player* player : v)
{
	m.insert(make_pair(int key = player->_id, Player* data = player));
}

// -----------------------------------------

/* 찾기 ... 키 값을 받아서 이터레이터를 반환하는 fine() */
std::map<int, Player*>iterator it = m.find(300); 
// 또는 auto 로 쉽게 저장하기!
auto it = m.find(300);

// -----------------------------------------

/* dereferencing */
auto whoami = *it;
// whoami.first; // 키 값
// whoami.second; // 값 값
// 위 세 문장과 아래 두 문장은 의미가 같다~
int key = it->first // 텔레포트 하고 덧셈 하기
Player* value = it->second; // 텔레포트 하고 덧셈 하기

// -----------------------------------------

/* 삭제 */
m.erase(it);
m.erase(200);
  
// -----------------------------------------

/* 순회 : 벡터와 달리 알아서 좀 정렬이 되어있다. */
// 사실 장점은 없다. 
for (auto it = m.begin(); it != m.end(); it++)
{
 	int key = it->first;
  	Player* p = it->second;
}
  
// -----------------------------------------

/* 더 빠르게 찾는 법. 쉬워서 많이들 쓴다. */
// 없는 키 값을 넣었다면 ? 
// C++ STL vs UE TMap 에서 작동하는 방식이 다르기 때문에 중요하다.
// 표준에서는 가지고 오되, 없으면 디폴트값을 추가해준다.
// 그러나 언리얼에서는 크래시가 난다.
Player* p = m[100]; // 100번째 키에 해당하는 값을 가지고 오세요

// -----------------------------------------

/* 비어있는가? */
m.empty(); // 사이즈가 0인지? isEmpty? true이면 데이터가 없다는 뜻이다.  
  
// 근데 언리얼에서는 empty 를 하면 clear 를 해서 데이터를 날려버린다.

[] 연산자를 이용하면 키로 검색하여 값을 알아낼 수 있다.
[] 연산자는 찾을 수 없는 경우 빈 문자열 ("") 을 리턴한다.

다음과 같이 at() 을 이용하여 검색을 할 수 있지만,
at() 은 찾을 수 없는 경우 예외를 발생시키므로 예외 처리 코드를 작성해야 하는 부담이 있다.

맵에 '키'의 데이터가 있는 지 검사하기 위해서는 전형적으로 다음 코드를 이용한다.

if(dic.find(eng) == dic.end()) // eng 의 '키'를 찾을 수 없다면 조건문은 true

STL std::map 의 멤버 함수와 연산자 함수

멤버와 연산자 함수	설명
insert(pair<> &element)	맵에 '키'와 '값'으로 구성된 pair객체 element 삽입
at(key_type& key)	맵에 '키'값에 해당하는 '값' 리턴
begin()	맵의 첫 번째 원소에 대한 참조 리턴
end()	맵의 끝(마지막 원소 다음)을 가리키는 참조 리턴
empty()	맵이 비어 있으면 true 리턴
find(key_type& key)	맵에서 '키'값에 해당하는 원소를 가리키는 iterator 리턴
erase(iterator it)	맵에서 it가 가리키는 원소 삭제
size()	맵에 들어 있는 원소의 개수 리턴
`operator[key_type& key]()`	맵에서 '키'값에 해당하는 원소를 찾아 '값' 리턴
`oprator=()`	맵 치환(복사)

unordered_map

hash_map 이라고 알려져있다.

비유를 하자면 살을 내주고 뼈를 취한다! 라고 할 수 있다.
메모리를 팔아서 CPU 성능을 얻겠다! 라는 의미이다.

아파트 우편함을 예시로 들어보자.
모든 사람이 같은 우편함을 쓰면 문제가 생길 것이다.
그래서 우리는 각 세대마다 우편함을 만든다.

find( ) 의 시간복잡도 : O(1)

#include <iostream>
using namespace std;
#include <unordered_map>
  
int main()
{
	unordered_map<int, int> um; 
}

// -----------------------------------------

/* 추가 */
um.insert(make_pair(10, 100)); 
um[20] = 200;
// 없으면 기본값으로 추가해준다.
  
// -----------------------------------------
  
/* 찾기 */
auto findIt = um.find(10);
if (findIt != um.end())
{
	cout << "찾음" << endl;
}
else
{
	cout << "없음" << endl;
} 
  
// -----------------------------------------
  
/* 삭제 */
um.erase(10);
  
// -----------------------------------------
  
/* 순회 */
for (auto it=um.begin(); it!=um.end(); it++)
{
	 int key = it->first;
	 int value = it->second;
}