[C++] STL unordered_set, unordered_map(Hash) 정리 및 사용법

Intro

• 전화번호부를 만들려고할때, 배열을 사용해서 만든다면 어떨까?

• 예를들어, 전화번호부에 {이름, 전화번호} 와 같은 데이터를 집어넣는다고 생각해보자.

• 그렇다면 내가 전화번호부에서 최서방의 전화번호를 찾으려면 어떻게해야될까?

• 배열로 구현했을때 그 방법은 하나하나 검사하는것이다.

• 전화번호부에 사람이 1000명, 10000명이 될경우에는 아주 비효율적인 방법이 될것이다. 이럴 때 사용하는것이 해쉬(Hash)다.

Hash란

Hash는 {key, value} 쌍으로 이루어진 데이터를 저장하는 자료구조다.

내가 찾고자하는 value의 key값만 알고있다면, key값으로 검색하여 key에 대응하는 value를 알 수 있다.

Hash의 장점은 검색과 저장의 시간복잡도가 O(1)으로, 굉장히 효율적인 데이터관리가 가능하다.

단, 충돌이 없어야한다. 충돌이란 새로 입력되는 데이터의 key값이 이미 테이블에 존재하는 경우 발생한다.

따라서 최대한 충돌이 발생하지 않도록 설계해야한다.

unordered_set

C++ 에서 데이터의 검색과 삽입 및 삭제등을 편하게하기 위한 내장함수들이 존재한다.

먼저, unordered_set은 key값만 존재하는 자료구조이다.

#include <iostream>
#include <unordered_set>
#include <string>

using namespace std;

int main()
{
	unordered_set<string> s;		// unordered_set 선언

	for (int i = 0;i < 5;i++)
	{
		string input;
		cin >> input;

		s.insert(input);			// 데이터 삽입
	}

	for (auto it = s.begin(); it != s.end(); it++)
	{
		cout << *it << "\n";		// 출력
	}
}

• 헤더를 추가해주어야하며, 데이터 삽입 및 출력이 되는것을 볼 수 있다.

unordered_set 사용시 주의점

• unordered_set은 이름 그대로 정렬이 되지않는다. 하지만 삽입한 순서는 유지된다.

• unordered_set은 중복을 허용하지 않는다. 따라서 중복된 데이터를 삽입하려하면 실패하게된다.

• 만약, 중복을 허용하고싶다면, unordered_multiset을 사용해야한다.

unordered_map

unordered_map은 unordered_set과 같지만 key와 value가 한쌍인 자료구조이다.

따라서 데이터를 삽입할 때 value로 같이 집어넣어야한다.

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

using namespace std;

int main()
{
	unordered_map<string, int> m;		// unordered_map 선언

	for (int i = 0;i < 5;i++)
	{
		string input;
		cin >> input;

		s.insert({input, i});			// 데이터 삽입
	}

	for (auto it = m.begin(); it != m.end(); it++)
	{
		cout << it -> first << " " << it -> second << "\n";		// 출력
	}
}

• 헤더를 추가해주어야하며, 데이터 삽입 및 출력이 되는것을 볼 수 있다.

응용

• 새로운 구조체를 만들어 unordered_map에 추가할수도 있다.

// 이름, 학년, 점수를 가지는 구조체 선언
typedef struct st{
    string name;
    int grade;
    int score;
}DATA;

unordered_map<int, DATA> db;            // 선언

db.insert({id, {Name, Grade, Score}})   // 데이터 삽입

auto it = db.find(id)                   // id(key)라는 key를 갖고있는지 검색

// 없을 때 처리
if(it == db.end())
    ...        
// 있을 때
else
{
    string name = it->second.name;
    int grade = it->second.grade;
    int score = it->second.score;
}