Search
Duplicate

[C++] set STL 을 알아보자.

간단소개
set STL에 대해 왜 사용하는지 알아보자.
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
C++
Scrap
태그
STL
c++
9 more properties

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이다.