[자료구조 C/C++] #03. Set

Set이란??

set은 key라고 불리는 원소들의 집합으로
이루어진 컨테이너입니다. set안에 들어가는 key값들은 중복될 수 없으며 자동으로 정렬이 됩니다.
set의 구조는 이진균형트리구조를 이루기 때문에 원소의 삽입, 삭제, 검색의 시간복잡도가 O(logN)이 듭니다.

마지막으로 메모리는 동적할당이 됩니다.

 

Set의 사용법?

가장 먼저 set이라는 헤더파일을 불러와야 합니다.
set변수를 선언할 때는 set<data type>변수
=> set<int>s

 

Set의 멤버함수

s.begin() => 첫 번째 원소의  반복자를 반환합니다.
s.end() => 마지막 원소의 다음 반복자를 반환합니다.
s.empty() => set이 비어있으면 true를, 비어있지 않으면 false를 반환합니다.
s.clear() => set의 모든 원소들을 삭제합니다.
s.find(a) => k와 관련된 원소의 반복자를 반환하며 원소가 없을 시에는 end()와 같은 결과를 반환합니다.
s.erase(iter) => 반복자가 가리키는 원소를 삭제합니다.
s.erase(key) => 해당되는 key를 삭제합니다.
s.erase(start,end) => start부터 end까지의 원소들을 삭제합니다.
s.size() => set의 원소 개수를 반환합니다.
s.rbegin() => 역방향으로 첫 번째 원소의 반복자를 반환합니다.
s.rend() => 역방향으로 마지막 원소의 다음 반복자를 반환합니다.
s.lower_bound(a) => 원소 k가 시작되는 구간의 반복자 입니다.
s.upper_bound(a) => 원소 a가 끝나는 구간의 반복자 입니다.
s.insert(k) => k를 set에 삽입합니다.
s.insert(iter,k) => iter가 가리키는 위치부터 k를 삽입할 위치를 탐색하여 삽입합니다.
s.count(k) => k의 개수를 반환합니다.  set의 특성상 리턴값은 0아니면 1입니다.

 

기타

 

중복된 원소를 사용하고 싶으면 multiset을 사용할 수 있습니다.

오름차순이 아니라 내림차순으로 정렬하고 싶으시면 greater를 사용할 수 있습니다.
정렬을 하고 싶지 않으시면 unordered_map이라는 헤더파일을 불러와서 사용할 수 있습니다.
set은 인덱스형식으로 원소를 삽입할 수 없으며 key값으로만 되어있기 때문에 출력하기 위해서는 iterator를
사용하셔야 합니다.