Set
기본적으로 set의 특징은 중복이 없고 항상 정렬이 된 상태를 유지한다는 것이다.
이러한 구조를 유지하기 위해서 가장 유리한 것은 binary search tree 를 유지하는 것이다.
근데 이런 일반적인 구조는 정렬된 자료가 들어올 때 unbalanced tree를 이룰 수 있다.
그러면 삽입, 삭제, 탐색 전부 O(n)이 되므로 set 을 쓰는 의미가 없다.
그래서 실제로 구현은 red-black tree를 사용한다.
Method
•
선언
#include<set>
set<int> s;
C++
복사
•
삽입
s.insert(7);
C++
복사
시간 복잡도 : O(lgN)
•
탐색
s.find(k);
C++
복사
iterator 반환
없으면 s.end() 반환
시간 복잡도 : O(lgN)
s.count(k);
C++
복사
1개 또는 0개 로 위와 마찬가지로 탐색 가능
s.size()
C++
복사
데이터 총 개수 반환
반복적으로 계속 데이터를 삽입하고 안에 존재하는지 확인하는 부분에서 낮은 시간복잡도로 유용하게 사용할 수 있는 class이다.