[C++] map과 unordered_map이란?

프로젝트에서 map을 활용하다 생긴 궁금증을 정리하기 위해서 이 글을 작성하게 됐습니다.

활용방법만 보러 오셨으면 사용법과 차이점만 보고 가셔도 무방합니다.

 

map과 unordered_map 자료구조에 대해서 설명하겠습니다.

 

공통점

map과 unordered_map의 공통점은 { key, value }를 저장하고 있는 자료구조 입니다.

key 값은 중복되지 않으며, value는 중복이 되도 상관 없습니다.

map 자료구조의 성질을 가지고 있기 때문에 비슷하게 사용되며, 알고리즘 문제 풀 때 자주 사용됩니다.

 

사용법

헤더

#include <map> -> map
#include <unordered_map> ->unordered_map

 

선언

map<key type, value type> M; -> map
unordered_map<key type, value type> U_M; -> unordered_map

예)
map<string, int> M; -> map
unordered_map<int, bool> U_M; -> unordered_map

 

 

데이터 포함 여부 확인

if(M.find("Seoul") == M.end()) cout << "서울은 포함되어 있지 않습니다.";
else cout << "서울은 이미 포함되어 있습니다.";

if(U_M.find(1) == U_M.end()) cout << "1은 포함되어 있지 않습니다.";
else cout << "1은 이미 포함되어 있습니다.";

 

찾고 싶은 데이터를 탐색할 때,

데이터가 존재한다면 해당 위치의 iterator를 반환하고,

존재하지 않는다면 end iterator를 반환합니다.

 

데이터 삽입

map
M.insert({ "Seoul", 02 });
M["Busan"] = 051;

unordered_map
U_M.insert({ 1, true });
U_M[0] = false;

 

Key를 이용한 데이터 접근

cout << M["Seoul"] << "\n";
cout << U_M[1] << "\n";

 

반복문을 이용한 데이터 접근

for(map<int, int>::iterator iter = M.begin(); iter != M.end(); iter++)
	cout << iter->first << " " << iter->second << "\n";
    
for (auto iter : U_M)
	cout << iter.first << " " << iter.second << "\n";

데이터 삭제

M.erase("Seoul");
U_M.erase(1);

모든 데이터 삭제

M.clear();
U_M.clear();

 

차이점

언뜻 보면 비슷해보지만, 차이를 모르고 사용했다간 시간 복잡도에서 예상치 못한 결과가 나올 수 있습니다.

 

map은 key 값을 기준으로 정렬해서 저장하며,

unordered_map은 정렬하지 않은 상태로 저장합니다.

 

코드를 보며 확인해보겠습니다.

 

#include <iostream>
#include <map>
#include <unordered_map>

using namespace std;

int main() {
	map<int, int> M;
	unordered_map<int, int> U_M;
	
	M.insert({ 1,1 });
	M.insert({ -1, 10 });
	M[10] = -1;

	cout << "map 출력\n";
	for (auto m : M) cout << "key : " << m.first << " value : " << m.second << "\n";
	cout << "\n";

	U_M.insert({ 10, 0 });
	U_M[-10] = 10;
	U_M[0] = 1;

	cout << "unordered_map 출력\n";
	for (auto um : U_M) cout << "key : " << um.first << " value : " << um.second << "\n";
}

 

[사진 1] 결과

 

[사진 1]을 보면  알 수 있듯이,

map은 삽입 순서와 관계 없이 key를 기준으로 정렬된 것을 확인할 수 있습니다.

unordered_map은 삽입된 순서대로 저장되어 있는 것을 확인할 수 있습니다.

 

이렇게 보면 자동으로 정렬해주는 map을 사용하는 것이 무조건 좋아보이기도 합니다.

 

하지만 시간 복잡도를 생각해본다면,

map은 데이터를 삽입할 때마다 정렬하기 때문에, unordered_map보다 더 많은 시간이 요구됩니다.

그래서 굳이 정렬된 데이터가 필요하지 않다면 unordered_map을 사용하는 것이 더 좋아보입니다.

---

 

이제부터는 프로젝트 하다가 생긴 궁금증을 정리하는 부분입니다.

 

https://end-of-code.tistory.com/entry/%EB%AF%B8%EB%A1%9C%EA%B2%8C%EC%9E%84-%EB%AF%B8%EB%A1%9C-%EC%83%9D%EC%84%B1-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%94%84%EB%A6%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[C++] 미로게임 | 미로 생성 알고리즘-프림 알고리즘

 

Prim 미로 생성 알고리즘에서 map에 Pos를 저장하는 코드가 있습니다.

 

map<Pos, int> _minCost;
_minCost[Pos(1, 1)] = 0;

 

코드를 간단하게 설명하면,

(1, 1) 위치의 값을 0으로 설정하는 코드입니다.

 

여기서 궁금했던건 "어떻게 Pos(1, 1)을 저장하고,  값을 변경하고 가져오는지" 였습니다.

 

보통 데이터를 넣고 가져올 때,

주소를 통해서 데이터를 주고 받게 됩니다.

 

Pos(1, 1)을 다른 곳에서도 사용해야 하는데,

모두 같은 주소를 가르키는지 궁금했습니다.

 

우선 데이터를 굳이 정렬해서 map에 저장할 필요가 없으니 unordered_map을 사용했습니다.

 

struct Pos {
	int row, col;

	Pos(int row, int col) : row(row), col(col) {}
};

int main() {
	unordered_map<Pos, int> U_M;
	
	U_M[Pos(1, 1)] = 10;
	cout << U_M[Pos(1, 1)];
}

 

Pos 구조체를 만들어서 위치를 받고 unordered_map에 넣어줬습니다.

코드를 컴파일 하면 C2280 오류가 납니다.

 

이유를 찾아보니,

map과 달리 unordered_map은 key를 해쉬화하여 사용하며,

오류가 발생하는 이유는 Pos 타입을 해쉬화 하기 위한 해쉬 함수가 내장되어 있지 않아 나타나는 오류라고 합니다.

 

그래서 unordered_map을 map으로 바꿔서 다시 작성했습니다.

 

struct Pos {
	int row, col;

	Pos(int row, int col) : row(row), col(col) {}
};

int main() {
	map<Pos, int> M;
	
	M[Pos(1, 1)] = 10;
	cout << M[Pos(1, 1)];
}

 

코드를 컴파일 하면 이번엔 C2676 오류가 납니다.

오류를 해석해보면 '<' 연산자가 정의되지 않아서 오류가 났습니다.

즉, Pos 구조체에 operator< 함수를 추가해주면 됩니다.

 

struct Pos {
	int row, col;

	Pos(int row, int col) : row(row), col(col) {}
	bool operator<(Pos o) const {
		return false;
	}
};

int main() {
	map<Pos, int> M;
	
	M[Pos(1, 1)] = 10;
	cout << M[Pos(1, 1)]; //10 출력
}

 

코드를 실행하면 10이 잘 출력이 됩니다.

 

이젠 여러 개의 Pos를 입력 받아서 값이 잘 저장되고 변경되는지 확인하면 됩니다.

 

int main() {
	map<Pos, int> M;
	
	for (int i = 0; i < 10; i++) M[Pos(i, i)] = i;
	
	for (auto iter : M) 
		cout << "row : " << iter.first.row << " col : " << iter.first.col << " value : " << iter.second << "\n";

	cout << "map의 크기 : " << M.size() << "\n";
}

 

0부터 9까지의 위치를 map에 저장시키는 것이 목표입니다.

예상했던 결과는 0부터 9까지 저장된 결과를 출력하고, map의 크기는 10이 출력되는 것을 예상했습니다.

 

[사진 2] 예상하지 못한 결과

 

[사진 2]를 보면 예상과는 전혀 다른 결과가 나왔습니다.

이상한 값이 출력됐고, map에는 1개의 데이터만 저장되어 있습니다.

 

이 문제를 해결하기 위해 operator<를 변경했습니다.

 

struct Pos {
	int row, col;

	Pos(int row, int col) : row(row), col(col) {}

	bool operator<(Pos o) const {
		if (row == o.row) return col < o.col;
		return row < o.row;
	}
};

int main() {
	map<Pos, int> M;
	
	for (int i = 0; i < 10; i++) M[Pos(i, i)] = i;
	
	for (auto iter : M) 
		cout << "row : " << iter.first.row << " col : " << iter.first.col << " value : " << iter.second << "\n";

	cout << "map의 크기 : " << M.size() << "\n";
}

 

[사진 3] 원하는 결과

 

operator를 적절히 변경하니 원하는 결과가 나왔습니다.

 

Map 자료구조는 데이터를 저장하는 방식이 operator와 연관이 있는 것 같습니다.

 

또 발견한 다른 오류가 있습니다.

 

map<Pos, Pos> parent;
parent[Pos(1, 1)] = Pos(1, 1);

 

이 코드를 실행하면 C2512 오류가 납니다.

Pos에 기본 생성자가 없어서 발생하는 오류입니다.

 

추측상 map에 Pos(1, 1)을 저장할 때, value에 Pos(1, 1)을 바로 넣어주지 않고 Pos 기본 생성자를 먼저 만들고 Pos(1, 1)으로 변경하는 것 같습니다.

그래서 value를 만들어줄 때, 기본 생성자가 없어 발생하는 오류인 것 같습니다.

 

Pos 구조체에 기본 생성자를 추가해주면 위의 오류는 해결됩니다.

 

예를 들면, 아래 코드는 기본 생성자가 없기 때문에 C2512 오류가 납니다.

struct Pos {
	int row, col;

	Pos(int row, int col) : row(row), col(col) {}

	bool operator<(Pos o) const {
		if (row == o.row) return col < o.col;
		return row < o.row;
	}
};

int main() {
	map<Pos, Pos> M;
	
	M[Pos(1, 1)] = Pos(1, 1);
}

 

아래는 정상 실행되는 코드입니다.

struct Pos {
	int row, col;
	
	Pos() { row = -1, col = -1; }
	Pos(int row, int col) : row(row), col(col) {}
	
	bool operator<(Pos o) const {
		if (row == o.row) return col > o.col;
		return row > o.row;
	}
};

int main() {
	map<Pos, Pos> M;
	
	M[Pos(1, 1)] = Pos(1, 1);
}

 

기본 생성자 Pos()를 추가했기 때문에, 컴파일 오류 없이 정상 실행됩니다.

---

제가 공부한 부분을 정리한 내용이기 때문에 틀린 부분 있을 수 있습니다!!

혹시 틀린 부분이 있으면 알려주세요!!