[STL 컨테이너] set & unordered_set & multiset

🔔 set 컨테이너

#include <set>

• Associative Container 中 하나
• 원소는 중복 저장될 수 없다.
  • 같은 원소로 이미 들어있다면 나중에 오는 insert는 무시된다.
  • 중복 검사를 해야 한다면 그냥 set 컨테이너에 넣으면 중복 검사를 할 필요가 없이 그냥 insert만 해주면 되므로 편리하다.
• 자동으로 원소들이 순서대로 정렬되어 들어간다.

벡터, 리스트 같이 원소들의 연속된 순서에 의미를 가지는 Sequence Container 가 아닌, Key 로서 접근에 의미를 가지는 Associative Container이다.

map 컨테이너와 다른 점

• map에서는 Key가 특정 Value 값과 연결되나
  • A[“노래”] = 3 이런 느낌!
  • map의 원소는 std::pair다.
• set에서는 Key가 True or False bool타입의 Value값과 연결된다.
  • 즉, 해당 Key 데이터가 set에 존재하는지에 대한 개념을 다룬다.
  • 집합이라고 생각하믄 됨
  • A[“노래”] 👉 true.
    • A set에 “노래” 원소가 존재. 이런 느낌!
  • set의 원소는 타입이 다양하다.

함수

• begin()
  • 시작 반복자 리턴
• end()
  • 끝의 바로 다음 반복자 리턴
    • 컨테이너의 맨 끝에 빈 곳에 대한 반복자를 리턴한다.
• insert(원소)
  • 중복 원소는 허락하지 않으므로 기존 Key가 이미 있다면 insert 하지 않고 무시한다.
• erase(원소)
  • 원소 값에 대응하는 원소를 삭제
• clear()
  • 셋의 모든 원소 삭제
• find(원소)
  • 원소 값에 해당하는 반복자를 리턴한다.
  • 원소를 찾지 못한다면 end()를 호출한다.
    • 맨 끝에 빈 곳에 대한 반복자를 리턴
• empty()
  • map이 비어있으면 true, 아니면 false 리턴
• size()
  • 원소의 총 개수 리턴

🔔 multiset 컨테이너

set과 다르게 중복 원소를 허락한다.

• 중복 Key 가 있어도 insert 연산을 무시하지 않는다.

🔔 unordered_set 컨테이너

• 사용 방법은 set과 같다.

set과 다르게 정렬되지 않으며 해시 함수를 사용하여 원소를 탐색한다.

• 그래서 원래는 <unordered_set>가 아닌 <hashset> 으로 지으려고 했으나 그런 이름을 가진 헤더가 많아 그냥 이렇게 지었다고 한다. tmi
• 원소를 해시 함수로 찾으니까 정렬될 필요가 없음
  • Hash
    • 해시 함수 값이 동일하게 나오면 같은 상자 안에 저장된다.
      • 동일한 원소끼리는 당연히 해시 함수 리턴 값이 같으니 같은 상자 안에 저장되지만
      • 서로 다른 원소끼리도 우연히 해시 함수 값이 같으면 같은 상자 안에 저장될 수 있다.
        • 해시 충돌
• 해시 함수로 리턴값만 받아 바로 주소 찾아가면 되므로 탐색 시간이 \(O(1)\) 상수시간 밖에 안걸린다.
• But 해시 충돌이 많이 일어나 한 상자 안에 서로 다른 원소들이 몰려서 저장되게 되면 해당 상자 안에서 찾고자 하는 원소를 탐색해야 하므로
  • 최악의 경우 모든 원소가 한 곳에 모였을 때 \(O(N)\) 시간이 걸릴 수 있다.

내가 만든 클래스를 unordered_set 의 원소로 넣고 싶을 때

• 내 클래스에 맞는 직접 해시 함수를 만들어 주어야 한다.
  • 내 클래스
    • 정렬은 하지 않으니 < 연산자 오버로딩은 필요 없음
    • 해시 충돌이 일어날 때를 대비해 같은 상자 안에 있는 원소들끼리 비교해야 하므로 == 연산자 오버로딩도 해주어야 한다.
  • hash 템플릿 구조체를 내 클래스 타입으로 특수화
    • unordered_set은 해시 함수 계산을 위해 hash 객체를 사용하기 때문에
    • hash를 내 클래스 타입으로 특수화 하여 () 연산자 오버로딩을 한다.

      namespace std 
      {
      template <>
      struct hash<MyClass> {
          size_t operator()(const MyClass& myclass) const {
              hash<string> hash_func;  // C++에서 제공하는 string의 해시 함수 포인터
      
              return myclass.m_data1 ^ (hash_func(m_data2));
           }
      };
      }
      

    • XOR (비트연산) 하도록 사용자 정의를 해주었다.
      • 해시 함수 리턴값은 myclass.m_data1 ^ (hash_func(m_data2)) 의 결과가 된다.
    • 참고로 C++ 표준 클래스를 특수화 할 때는 namespace std 안에서 해주어야 한다.

C++ 은 int, double, string 등등 기본 데이터 타입들에 대한 해시 함수 포인터를 제공해주므로 이를 활요하면 된다. hash<T> hash_func

set 과 unordered_set 의 차이

• set은 정렬 되어있는 상태에서 탐색을 하므로 \(O(logN)\) 시간이 걸린다. 평균도 최악도!
• hash set은 해시 함수로 탐색을 하므로 평균 \(O(1)\) 상수 시간이 걸려 매우 빠르지만 해시 충돌이 너무 많이 일어나는 최악의 경우 \(O(n)\) 로 그냥 set보다 더 오래걸릴 수 있다.
• 원소의 개수가 많을수록 해시충돌이 일어날 확률도 높아지므로
  • 원소의 개수가 적고 빠른 성능을 원할 땐 unordered_set
  • 원소의 개수가 많아 안정성을 원할 땐 set

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기