c++ unordered_set 사용 기록

unordered set을 사용하기 위해서는 직접 hash 구조체와

operator==를 정의해 주어야 한다.

 

hash 구조체를 namespace std에 지정하면 별도로 hash 구조체를 안 넣어줘도 된다.

unordered set은 time complexity가 O(1)이다.

 

코드 >>

#include <iostream>
#include <string>
#include <unordered_set>
 
class Cat
{
public:
    explicit Cat(int age, std::string name) : mAge{ age }, mName{ name } {};
    void speak() const
    {
        std::cout << mAge << " " << mName << std::endl;
    }
    int age() const
    {
        return mAge;
    }
    const std::string& name() const
    {
        return mName;
    }
private:
    int mAge;
    std::string mName;
};
 
struct CatHash
{
    std::size_t operator()(Cat const& c) const noexcept
    {
        std::size_t h1 = std::hash<int>{}(c.age());
        std::size_t h2 = std::hash<std::string>{}(c.name());
        return h1 ^ h2;
    }
};
 
bool operator==(const Cat& lhs, const Cat& rhs) noexcept
{
    return (lhs.age() == rhs.age() && lhs.name() == rhs.name());
}
 
// unordered_set을 사용하는 다른 방법
 
struct hello
{
    bool operator()(int a, int b) {
        return true;
    }
};
 
namespace std
{
    template<>
    struct hash<Cat>
    {
        std::size_t operator()(Cat const& c) const noexcept
        {
            std::size_t h1 = std::hash<int>{}(c.age());
            std::size_t h2 = std::hash<std::string>{}(c.name());
            return h1 ^ h2;
        }
    };
}
 
int main()
{
    // unorder_set은 time complexity가 O(1)이다.
    // 데이터가 증가해서 rehashing이 일어나면
    // O(n)이 time complexity이다.
    // 미리 reserve를 해 놓는다.
    std::unordered_set<std::string> uordSet;
    uordSet.reserve(10000);
    uordSet.emplace("abc"); // O(1)
    uordSet.emplace("def");
    uordSet.emplace("ghi");
    uordSet.emplace("jkl");
    uordSet.emplace("123123");
    uordSet.emplace("ㅁㅇ러ㅏㅁㄹ");
    uordSet.emplace("dfad");
    uordSet.emplace("qerqrad");
    uordSet.emplace("daf");
    uordSet.emplace("asfwr");
    uordSet.emplace("adflb");
    uordSet.emplace("jkadfal");
 
    for (const std::string& str : uordSet)
    {
        std::cout << str << std::endl;
    }
    uordSet.find("abc"); //O(1)
    uordSet.erase("abc"); // O(1) 사실 hash를 사용하기에 가능
    // hash function은 1:1 함수이다.
    // input이 같으면 output도 같고, input이다르면 output도다름
    // stack, heap 이외에도 hash는 bucket이라는 통에 저장된다.
    std::cout << "hash abc : " << std::hash<std::string>{}("abc") << " bucket abc: "  <<uordSet.bucket("abc") << std::endl;
    std::cout << "hash def : " << std::hash<std::string>{}("def") << " bucket def: " << uordSet.bucket("def") << std::endl;
    std::cout << "hash ghi : " << std::hash<std::string>{}("ghi") << " bucket ghi: " << uordSet.bucket("ghi") << std::endl;
    std::cout << "hash jkl : " << std::hash<std::string>{}("jkl") << " bucket jkl: " << uordSet.bucket("jkl") << std::endl;
    
    // HashSet의 Bucket count
    std::cout << "bucket count : " << uordSet.bucket_count() << std::endl;
 
 
    Cat kitty{ 1, "kitty" };
    Cat nabi{ 2, "nabi" };
 
    //std::cout << (kitty == nabi) << std::endl;
 
    //std::unordered_set<Cat, CatHash> cats;
    
    /// <summary>
    /// std에 미리 넣어 두었으면 굳이 CatHash를 등록하지 않아도 된다.
    /// </summary>
    /// <returns></returns>
    std::unordered_set<Cat> cats;
    cats.emplace(kitty);
    cats.emplace(nabi);
    // unordered_set은 중복을 허용하지 않는다.
    cats.emplace(1, "kitty");
    cats.emplace(2, "nabi");
 
    for (const auto& cat : cats)
    {
        cat.speak();
    }
 
    
    return 0;
}