정의
- Set은 key값을 이용하여 대응하는 방식인 연관 컨테이너(Associative Container)이다.
- Set은 균형 이진 트리로 구현되었다.
** 이진 탐색 트리: 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자신 노드
- key라고 불리는 원소들의 집합으로 이루어진 컨테이너이다.
- 수학에서 집합과 같은 의미로 사용된다.
시간 복잡도
- 탐색, 검색, 삽입, 삭제 시 평균적으로 O(logN)의 시간 복잡도를 가진다.
- 검색, 삽입, 삭제 시 최악의 경우 O(N)의 시간이 소요될 수 있으나 이는 매우 드물다.
특징
- key 값은 중복이 허용되지 않는다.(유일성을 갖는다.)
** 중복 원소를 허용하고 싶다면 Multiset을 사용하면 된다.
- 원소가 삽입되면 삽입 순서와는 상관없이 자동으로 정렬되며 기본적으론 오름차순이다.
->이 특징을 모두 만족하는 자료구조는 이진 트리이다.
즉, Set은 Red-Black 트리 구조(균형 이진 트리 구조)로 구현되었다. - 탐색 시 inorder 탐색을 한다.
- 필요에 따라 메모리를 할당(동적 할당)한다.
장점
이진 탐색 트리 기반이므로 검색이 아주 빠르고 자동 정렬이 된다. 매우 빠른 속도로 데이터를 처리할 수 있다.
따라서 아래와 같은 경우 set을 사용하면 유용하다.
- 삽입과 동시에 정렬해야 할 때
- key를 검색할 때
- 빠른 검색으로 존재 여부를 신속하게 알고 싶을 때
단점
데이터를 삽입할 때마다 이진 탐색 트리를 재조정해야 하므로 연산 속도가 다른 컨테이너에 비해 느리다.
데이터를 삽입할 때 복사 생성자를 사용하므로 객체가 크거나 복잡하면 성능 문제가 발생할 수 있다.
참고 사이트
https://blockdmask.tistory.com/79
https://hwan-shell.tistory.com/130
https://luv-n-interest.tistory.com/964
https://velog.io/@jimojjing/CSTL-set
