[C++ STL] set

set이랑 unordered_set을 잘 구분해야한다

set을 unordered_set 처럼 생각하면 안된다!

보통 set하면 unordered_set 그림이 먼저 생각나는데

항상 생각해줘야할게 둘의 차이점은 정렬유무라는 것이다!!

 

일반 set은 정렬을 해줘야하기때문에 이진트리로 구현되어있지만

unordered_set은 정렬이 필요없기 때문에 hashtable로 구현되어있는 것이다!

 

---

1. 중복 X

2. 정렬 - 이진트리 - 노드기반

3. 추가 삭제 조회가 O(logN)

 

set은 항상 정렬된 상태를 유지하는 아키텍쳐가 필요할때 사용하는 것이다.
set은 언제나 정렬된 상태이기 때문에 따로 정렬이 필요가 없다

 

같은 원소가 이미 존재하면 나중에 오는 insert 는 무시된다

중복검사를 따로 해줄 필요 없이 그냥 insert만 해주면 되므로 매우 편리하다.

해당 원소가 있는지 조회를 할 필요가 없다는 것임

 

---

 

 

insert() O(logN)

erase(iterator) O(logN)

find(val) O(logN)

 

이진트리이므로 죄다 logN이다

근데 unordered_set은 O(1)임

 

clear()

empty()

size()

 

---

인지하고 있어야할게

insert 시 중복검사를 알아서 해준다는 것이다!

즉 따로 find(val)!=set.end()

이렇게 존재하는지 내가 검사를 안해줘도 된다는 거임