[Set, Map / Hash] Hash Set과 Custom Class

 

 

 

unordered_set에 사용자 정의 클래스 사용하기

1. unordered_set과 커스텀 클래스

• 이전 시간에는 unordered_set(해시 셋)의 내부 구조와 Find, Insert, Delete가 평균 O(1) 의 시간 복잡도를 가지는 이유를 알아보았다.
• 예제로 ABC, DEF, GHI와 같은 string 객체를 사용했다.
• 하지만 실제 개발에서는 기본 타입뿐만 아니라 사용자가 직접 만든 클래스(Custom Class) 도 unordered_set에 저장할 수 있다.

이번 시간에는 직접 만든 Cat 클래스를 unordered_set에 저장하는 방법을 알아본다.

 

 

2. 커스텀 클래스 저장 시 발생하는 오류

예를 들어 고양이 클래스를 정의한다.

class Cat
{
public:
    string name;
    int age;
};

그리고

unordered_set<Cat> cats;

cats.insert(kitty);
cats.insert(nabi);

를 실행하면 컴파일 에러가 발생한다.

이유는 unordered_set이 내부적으로 두 가지 정보를 필요로 하기 때문이다.

1. Hash 함수
2. Equality 비교 함수 (operator==)

현재 Cat 클래스에는 이 두 가지 정의가 없기 때문에 컴파일 오류가 발생한다.

 

 

 

3. 커스텀 Hash 함수 정의

C++에서는 사용자 정의 타입의 해시 함수를 만드는 방법이 두 가지 있다.

방법 1. Hash 함수 객체(Functor) 생성

• 별도의 Hash 클래스를 만든다.
• unordered_set 생성 시 해당 Hash 객체를 전달한다.

방법 2. std 네임스페이스에 hash 특수화

• std::hash<T>를 직접 정의한다.
• 그러면 별도의 Hash 전달 없이 사용할 수 있다.

이번 예제에서는 첫 번째 방법을 사용한다.

예:

struct CatHash
{
    size_t operator()(const Cat& cat) const
    {
        auto h1 = hash<string>()(cat.name);
        auto h2 = hash<int>()(cat.age);

        return h1 ^ h2;
    }
};

• 고양이 이름과 나이에 대한 해시값을 생성한다.
• 두 해시값을 조합하여 하나의 해시값을 만든다.

 

 

4. operator== 정의 필요성

Hash 함수만 만들어서는 부족하다.

unordered_set은 같은 버킷 안에 여러 객체가 존재할 수 있다.

예를 들어:

Bucket 4

ABC
GHI

처럼 같은 버킷에 들어온 두 객체를 구분해야 한다.

따라서 두 객체가 같은 객체인지 판단하는 비교 함수가 필요하다.

Cat 클래스에 다음과 같은 비교 연산자를 정의한다.

bool operator==(const Cat& other) const
{
    return name == other.name &&
           age == other.age;
}

이제 같은 버킷 안에서도 서로 다른 고양이를 구분할 수 있다.

 

 

5. unordered_set에 Hash 전달하기

Hash 객체를 만들었으면 unordered_set 생성 시 전달해야 한다.

unordered_set<Cat, CatHash> cats;

이제 Cat 객체를 정상적으로 저장할 수 있다.

예:

Cat kitty{"Kitty", 1};
Cat nabi{"Nabi", 2};

cats.insert(kitty);
cats.insert(nabi);

출력 결과:

Kitty 1
Nabi 2

정상적으로 저장되는 것을 확인할 수 있다.

 

 

6. 중복 제거 기능 확인

unordered_set은 set과 동일하게 중복을 허용하지 않는다.

예:

cats.insert(kitty);
cats.insert(nabi);
cats.insert(kitty);

결과:

Kitty 1
Nabi 2

이미 존재하는 Cat 객체는 추가되지 않는다.

 

 

7. std::hash 특수화 방법

앞의 방법 외에도 std 네임스페이스에 hash를 정의할 수 있다.

예:

namespace std
{
    template<>
    struct hash<Cat>
    {
        size_t operator()(const Cat& cat) const
        {
            ...
        }
    };
}

이렇게 하면

unordered_set<Cat> cats;

처럼 별도의 Hash 객체를 전달하지 않아도 된다.

 

 

 

8. unordered_multiset

지금까지 사용한 것은 중복을 허용하지 않는:

unordered_set

이다.

만약 중복 데이터를 허용하려면:

unordered_multiset

을 사용한다.

예:

unordered_multiset<Cat, CatHash> cats;

결과:

Kitty 1
Kitty 1
Nabi 2

처럼 동일한 객체를 여러 개 저장할 수 있다.

---

9. 핵심 정리

• unordered_set에 사용자 정의 클래스를 저장하려면 Hash 함수와 비교 함수가 필요하다.
• Hash 함수는 객체를 어떤 버킷에 저장할지 결정한다.
• operator==는 같은 버킷 안에서 객체가 동일한지 비교한다.
• Hash 함수 정의 방법:
  1. 커스텀 Hash Functor 생성
  2. std::hash 특수화
• unordered_set은 중복을 제거한다.
• unordered_multiset은 중복 저장이 가능하다.