set, unorderd_set

Set

key만 있는 map 혹은 정렬된 집합

set은 map과 구조가 매우 유사하다. 

단, key만 있고 value가 없는 map이라고 생각할 수 있다.

따라서, 사용법도 map과 크게 다르지 않다.

set은 이진 탐색 트리로 구현되어 있어 탐색, 삽입, 삭제에는 평균 O(logN) 시간이 소요된다.

 

정렬된 집합 이라고 정의한 이유는 set이 갖는 값들이 중복을 허락하지 않고 정렬되어 있기 때문이다. 

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

벡터, 리스트 같이 원소들의 연속된 순서에 의미를 가지는 Sequence Container가 아닌,

Key로서 접근에 의미를 가지는 Associative Container이다.

 

map 컨테이너와의 차이점

• map에서는 Key가 특정 Value 값과 연결된다.
  • map의 원소는 std::pair다.
  • Map[value] = 5 이런 느낌.
• set에서는 Key가 True or False bool 타입의 Value 값과 연결된다.
  • 즉, 해당 Key 데이터가 set에 존재하는지에 대한 개념을 다룬다.
  • Set[value] => true (set에 value가 존재한다.)
  • set의 원소는 타입이 다양하다.

 

위와 같이 클라이언트 정보를 다루는 세션을 저장하는 컨테이너로 사용.

중복 저장이 안되는 특성과 빠르게 삽입하고 검색할 수 있기 때문.

 

---

MultiSet

• set과 다르게 중복 원소를 허락한다.
• 중복 Key가 있어도 insert 연산을 무시하지 않는다.

---

unordered_set 

 

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

(그래서 원래는 <unordered_set>가 아닌 <hashset> 으로 지으려고 했으나 그런 이름을 가진 헤더가 많아 그냥 이렇게 지었다고 한다.)

 

• 원소를 해시 함수로 찾으니까 정렬될 필요가 없다.
• 해시 함수로 리턴값만 받아 바로 주소를 찾아가면 되므로 탐색 시간이 O(1) 상수시간 밖에 안걸린다.
• 하지만 해시 충돌이 많이 일어나 한 버킷 안에 서로 다른 원소들이 몰려서 저장되게 되면 최악의 경우에는 O(N) 시간이 걸릴 수 있다.

---