[C++/STL] - set

1. set 이란

set은 Unique한 원소들을 특별한 순서에 따라 저장하는 컨테이너입니다. Unique한 원소들은 Set 컨테이너 안에 단 1개(Unique)만 있을 수 있음을 의미합니다. Set은 보통 이진 탐색 트리로 구현되어 있습니다.

2. 특징

• Set은 Unique한 원소들을 특별한 순서에 따라 저장하는 컨테이너입니다.
• Set은 이진 탐색 트리로 구현되어 있어 탐색, 삽입, 삭제에는 평균 O(logN) 시간이 소요됩니다.
• Set은 기본 조건자가 less인데, 이는 오름차순으로 정렬됩니다. 내림차순으로 정렬하려면 greater 조건자를 사용합니다.
• Set은 중복된 원소를 허용하지 않습니다. 중복된 원소를 갖고자 한다면 multiset을 사용해야 합니다.
• Set은 연관 컨테이너로 key라 불리는 원소(value)의 집합으로 이루어집니다.
• Set은 균형 이진 트리로 구현되어 있어 빠른 시간으로 원소를 탐색할 수 있으며, 이에 따라 다양한 탐색 함수를 제공합니다.
• Set은 원소의 삽입 순서에 영향을 받지 않습니다.
• Set에서 원소를 key라 하며 이 키를 비교하여 내부 원소를 정렬합니다.

3. 장단점

장점 :

• Set은 Unique한 원소들을 저장하는데, 이를 이진 탐색 트리로 구현하므로 탐색, 삽입, 삭제에는 평균 O(logN) 시간이 소요됩니다. 이를 통해 매우 빠른 속도로 데이터를 처리할 수 있습니다.
• Set은 중복된 원소를 허용하지 않으므로 중복된 데이터를 처리할 때 유용합니다.
• Set은 연관 컨테이너로 key라 불리는 원소(value)의 집합으로 이루어져 있어, 매우 편리하고 다양한 탐색 함수를 제공합니다.
• Set은 이진 균형 트리로 구현되어 있어 삽입, 삭제, 탐색 연산이 모두 O(logN) 시간 복잡도를 가집니다.
• Set은 데이터를 삽입할 때 자동으로 정렬해주므로, 데이터를 정렬하지 않아도 되고 이를 통해 코드 작성 시간을 절약할 수 있습니다.

단점 :

• Set은 데이터를 삽입할 때마다 이진 탐색 트리를 재조정해야 하므로, 연산 속도가 다른 컨테이너에 비해 느릴 수 있습니다.
• Set은 중복된 데이터를 허용하지 않으므로, 중복된 데이터를 다룰 때는 multiset을 사용해야 합니다.
• Set은 데이터를 삽입할 때 복사 생성자를 사용하기 때문에, 객체가 크거나 복잡한 경우 성능 문제가 발생할 수 있습니다.

4. 시간복잡도

1. 접근 - O(logN)
   Set은 이진 탐색 트리로 구현되어 있으므로, 임의 원소에 접근하려면 O(logN)의 시간이 소요됩니다.
2. 검색 - O(logN)
   Set은 이진 탐색 트리로 구현되어 있어, 평균적으로 O(logN)의 시간이 소요됩니다. 최악의 경우 O(N)의 시간이 소요될 수 있지만, 이는 매우 드문 경우입니다.
3. 삽입 및 삭제 - O(logN)
   Set은 이진 탐색 트리로 구현되어 있으므로, 삽입 및 삭제에는 평균적으로 O(logN)의 시간이 소요됩니다. 최악의 경우 O(N)의 시간이 소요될 수 있지만, 이는 매우 드문 경우입니다.

5. 사용법

1) 초기화

set<int> s; // 빈 set 생성

set<int> s1;
s1.insert(1);
s1.insert(2);
set<int> s2(s1); // s1을 복사하여 s2를 생성

set<int> s1;
s1.insert(1);
s1.insert(2);
set<int> s2(s1.begin(), s1.end()); // s1의 모든 원소를 복사하여 s2를 생성

set<int> s = {1, 2, 3}; // s를 {1, 2, 3}으로 초기화

2) 멤버 함수

Iterators
begin() : 첫 번째 원소를 가리키는 반복자를 리턴한다.
cbegin() : 첫 번째 원소를 가리키는 상수 반복자를 리턴한다.
end() : 마지막 원소를 가리키는 반복자를 리턴한다.
cend() : 마지막 원소를 가리키는 상수 반복자를 리턴한다.
rbegin() : 역 순차열의 첫 번째 원소를 가리키는 반복자를 리턴한다.
crbegin() : 역 순차열의 첫 번째 원소를 가리키는 상수 반복자를 리턴한다.
rend() : 역 순차열의 마지막 원소를 가리키는 반복자를 리턴한다.
crend() : 역 순차열의 마지막 원소를 가리키는 상수 반복자를 리턴한다.
upper_bound(key) : 지정한 key 요소를 가지고 있다면 해당 위치의 다음 위치의 반복자를 반환
lower_bound(key) : 지정한 key의 요소를 가지고 있다면 해당 위치의 반복자를 반환

Element access
back() : 마지막 원소를 리턴한다.
front() : 첫번째 원소를 리턴한다.
find(key) : key와 연관된 원소의 반복자 반환 (없으면 end()와 같은 반복자 반환)
★ operator[]는 사용 불가

Capacity
empty() : 원소 존재 유무를 체크한다. 아무것도 없으면 true, 있으면 false를 리턴한다.
size() : 원소의 개수를 리턴한다.
max_size() : 담을 수 있는 원소의 최대 개수를 리턴한다.

Modifiers
clear() : set의 모든 원소를 제거한다
insert(key) : key 추가
insert(iter,key) : iter위치에 key 추가
insert(first, last) : first iter부터 last iter까지 추가
emplace() : 원소 삽입시 컨테이너 내부에서 생성 후 임의 위치에 임의 값을 삽입한다.
erase(key) : 해당 key를 삭제한다.
erase(iterator pos) : pos위치의 원소 제거
erase(iterator first, iterator last) : first부터 last까지 제거
emplace() : 원소 삽입시 컨테이너 내부에서 생성 후 임의 위치에 임의 값을 삽입한다.