Set

기본적으로 set의 특징은 중복이 없고 항상 정렬이 된 상태를 유지한다는 것이다.

이러한 구조를 유지하기 위해서 가장 유리한 것은 binary search tree 를 유지하는 것이다.

출처 : https://leeminju531.tistory.com/26

출처 : https://leeminju531.tistory.com/26

근데 이런 일반적인 구조는 정렬된 자료가 들어올 때 unbalanced tree를 이룰 수 있다.

그러면 삽입, 삭제, 탐색 전부 O(n)이 되므로 set 을 쓰는 의미가 없다.

그래서 실제로 구현은 red-black tree를 사용한다.


Method

#include<set>
set<int> s;
s.insert(7);

시간 복잡도 : O(lgN)

s.find(k);

iterator 반환

없으면 s.end() 반환