C++의 표준 연관 컨테이너들(associative container)

연관 컨테이너는 키-값 구조를 가짐

키의 존재 유무만 궁금 -> 셋, 멀티셋
키에 대응하는 값이 궁금 -> 맵, 멀티맵

셋

내부적으로 이진 검색 트리 구조로 구성되어 있음.
실제로 셋 내부적으로 원소들이 정렬된 상태를 유지하기 때문!

• 삽입, 삭제: O(logN)
• 검색: O(logN)

즉, 원소를 검색하는데 필요한 횟수는 트리의 높이와 일치.
셋 안에는 중복된 원소들이 없다는 게 또 하나의 특징.

균형 잡힌 트리 구조를 지향
(이진 검색 트리에서 균형잡히지 않은, 편향된 트리 구조를 지양하기 위해 여러 다른 규칙 적용)

커스텀 객체를 셋에 삽입해 보자!

커스텀 객체를 셋에 삽입할 때, < 연산자에 대한 메소드를 명시해야 한다.
셋 내부에서 비교 연산자로 셋에 삽입하기 때문이다.

strict weak ordering

operator <를 설계할 때

1. A < B , B < A 중 하나는 반드시 True여야 함
   -> 매몰되기 쉬운 실수!
2. A < A 는 거짓
3. A < B 이고 B < C 이면 A < C
4. A == B 이면 A < B 와 B < A 둘 다 거짓
5. A == B 이고 B == C 이면 A == C

맵

맵의 경우 키에 대응되는 값까지도 같이 보관함

[] 연산자 주의할 점

디폴트 생성자로 0을 만들어서 초기화할 수 있음.
따라서 find()로 있는 지 먼저 확인 후 초기화하는 게 베스트

멀티셋과 멀티맵

멀티셋과 멀티맵은 중복된 원소를 허락
(셋, 맵은 중복 원소 불허)

키로 값 부르기(중복되는 경우)

auto range = m.equal_range(1);

위의 경우 키가 1인 값들을 range에 받아 begin, end를 std::pair로 만들어서 세트로 리턴함.

정렬되지 않은 셋과 맵(unordered_set, unordered_map)

말 그대로 원소들이 정렬되지 않아 있음.
따라서 반복자로 원소들을 하나씩 출력하면 거의 랜덤한 순서로 나옴

실제 unordered_set의 모든 원소들을 반복자로 출력하면 딱히 순서대로 나오지는 않음.

장점

insert, erase, find 모두 O(1)에 수행

-> 상수 시간에 원소 삽입, 검색이 가능

구현 방법 - 해시 함수

해시함수는 1부터 D까지의 값을 반환, 그 해시값을 원소를 저장할 상자의 번호로 삼음.
해시 함수는 구조상 1 ~ D까지 고른 값을 반환하도록 설계함.

같은 원소를 해시 함수에 전달하면 같은 해시값을 리턴.
-> 원소의 탐색을 빠르게 수행

=> 그러나, 해시 충돌의 경우와 rehash의 경우, 최악의 경우 O(n)이 될 수 있음.

보통의 경우 안전하게 맵, 셋을 이용
만약 최적화가 매우 필요한 작업일 경우: 해시 함수, 상자 개수를 잘 설계해서 unordered_set, unordered_map을 사용하는 게 좋음.

커스텀 객체에 해시 함수 반영

functor를 사용해보자(객체이지만 함수인 척을 하는 객체).

class Todo {
  int priority; // 중요도. 높을 수록 급한것! std::string job_desc;
public:
  Todo(int priority, std::string job_desc)
        : priority(priority), job_desc(job_desc) {}
  bool operator==(const Todo& t) const {
  	// **!! 해시 충돌 발생 시 상자 안 원소들과 비교해야 하기 때문**
    if (priority == t.priority && job_desc == t.job_desc)
      return true; return false;
  }
  friend std::ostream& operator<<(std::ostream& o, const Todo& t);
  friend struct std::hash<Todo>; 
};

// Todo 해시 함수를 위한 함수객체(Functor) // 를 만들어줍니다!
namespace std {
  template <>
  struct hash<Todo> {
    size_t operator()(const Todo& t) const {
      hash<string> hash_func;
      return t.priority ^ (hash_func(t.job_desc));
    } 
  };
} // namespace std

return문 -> priority는 int값(해시값 그 자체로 쓰기로 함), string의 해시값은 hash_func 객체로 이용해서 계산, 이를 XOR시킴.

namespace문 -> 특정 namespace 안에 새로운 클래스/함수 추가 위해서는 위처럼 명시적으로 namespace를 써줘야 하기 때문(여기 참고)