[C++] set, multiset, unordered_set 의 차이

 C++에서 자주 쓰이는 STL 자료구조들이다. set, multiset, unordered_set 은 비슷하면서도 다른 기능들을 가지고 있다. 처음으로 set과 multiset의 차이를 비교해보고 이후에 unordered_set에 대해 따로 알아보자.

 

[set VS multiset]

 set과 multiset의 공통점부터 다루고, 차이점에 대해서 다루겠다.

 

 둘의 공통점으로는 자가 균형 이진 검색 트리로 구성되어 있고, 노드 기반의 컨테이너인 점이다. 자가 균형 이진 검색 트리란, 간단히 말하자면 트리에서 삽입과 삭제가 일어나더라도 한 쪽으로 편향되지 않도록 트리의 높이를 작게 유지되며, "왼쪽 자식 노드는 오른쪽 자식 노드보다 항상 작다" 라는 성질을 만족한다. C++에서 사용되는 Set STL에 조금 더 자세히보자면, Red-Black Tree 로 구현되어 있다.

Red-Black Tree : AVL Tree 구조의 일종으로서 항상 Balanced 한 아키텍처를 유지할 수 있는 Tree

 

 set과 multiset의 가장 큰 차이점은 set은 말그대로 원소를 한 개 이상 가질 수 없는 집합을 나타내는 자료구조이다. 하지만, multiset은 한 종류의 원소를 여러 개 가질 수 있는 집합을 나타내는 자료구조이다. 

즉, set 은 중복된 값(노드)은 허용하지 않고, multiset은 중복된 값을 허용한다는 의미이다. 

 

set의 내부 구조

multiset의 내부 구조

 

set과 multiset는 insert, erase, find 연산 시간복잡도는 O(logN)으로 vector 보다는 훨씬 빠른 것을 알 수 있다. 그리고 컨테이너 내에 요소가 있는지 없는지 체크할 수 있는 count 연산도 O(logN) 시간복잡도를 가진다.

vector - insert : O(N), find : O(N), erase : O(N)   => 중간에 삽입/삭제일 경우에는 O(N)이지만, 마지막 위치에서의 삽입/삭제는 O(1)에 이뤄진다.  

 

 

[unordered_set]

 unordered_set은 set, multiset과는 내부 구현부터 차이가 난다. 원래 unordered_set이 아니라 hashset으로 만들려고 했으나 이런 이름이 많아서, unordered_set으로 만들었다고 한다. 원래 hashset으로 만들려고 했던 것에서 알 수 있듯이, unordered_set은 내부적으로 Hash로 구현되어 있다. 

 

 Hash의 특징으로는, insert, erase, find 시간복잡도가 O(1)에 가능하다. Hash 함수를 수행하는데에는 상수 시간이 걸리기 때문이다. 하지만 모든 연산이 O(1)에 마무리 된다는 것은 Hash 함수가 굉장히 잘 설계되어있다는 조건이 만족되어야 한다. 만약 Hash 함수가 잘 설계되지 않아서 최악의 경우(충돌이 많이 일어나는 경우)에는 O(N)까지 가능해진다.

 

 Hash에서 충돌이 일어날 경우에는 Chaining 혹은 Open Addressing 방법을 사용해서 충돌 회피를 한다. 

unordered_set 내부 구조

 

 자료구조들의 장점과 단점들을 정확히 파악하고 각 상황에 맞게 맞는 자료구조를 알맞게 사용하는 것이 문제해결에 도움될 것이다!!

 

Reference

• https://www.cplusplus.com/reference/
• https://leeminju531.tistory.com/26
• https://blog.daum.net/coolprogramming/82
• https://docs.microsoft.com/ko-kr/cpp/standard-library/unordered-set-class?view=msvc-170#remarks 
• https://subscription.packtpub.com/book/programming/9781787126824/4/ch04lvl1sec43/the-useful-adaptor--std--priority-queue-t