std::set (STL)

set은 순서가 있는 고유한 원소의 집합이다. set은 중복을 허용하지 않고, 내부적으로 균형 이진 탐색 트리가 구현되어 있기 때문에 정렬된 상태로 데이터를 저장한다.

---

⦁ 특징

• 중복 허용 X: 중복된 값을 저장할 수 없다.
• 자동 정렬: 원소가 삽입될 때 자동으로 정렬된다.
• 시간 복잡도: 삽입, 삭제, 검색 연산의 평균 및 최악 시간 복잡도가 $O(\log N)$이다.
• 내부 구현: 균형 이진 탐색 트리로 구현되어 있다.

---

⦁ 예시

기본 예시

#include <set>

int main() {
    std::set<int> s;

    // 원소 삽입
    s.insert(5);
    s.insert(1);
    s.insert(3);
    s.insert(3);  // 중복 원소 삽입 (무시됨)

    // 원소 출력
    for (int x : s) {
        std::cout << x << " ";
    }

    return 0;
}

출력:

1 3 5

내림차순 정렬 예시

#include <set>

int main() {
    // 내림차순 정렬을 위한 사용자 정의 비교 함수
    std::set<int, std::greater<int>> s = {10, 20, 30};

    s.insert(25);
    s.insert(5);

    for (int x : s) {
        std::cout << x << " ";
    }

    return 0;
}

출력:

30 25 20 10 5

기본적으로 set은 오름차순으로 정렬되지만, 사용자 정의 비교 함수를 통해 내림차순 정렬도 가능하다.

---

⦁ 함수

함수	설명
insert(value)	원소 삽입. 이미 존재하는 경우 삽입하지 않음
erase(value)	특정 값을 가진 원소 삭제
find(value)	특정 값을 가진 원소를 검색. 없으면 end() 반환
count(value)	특정 값이 존재하면 1, 없으면 0 반환
size()	집합의 원소 개수를 반환
empty()	집합이 비어 있으면 true 반환
clear()	모든 원소를 제거
begin() / end()	시작/끝 반복자를 반환
lower_bound(value)	주어진 값 이상의 첫 번째 원소의 반복자를 반환
upper_bound(value)	주어진 값보다 큰 첫 번째 원소의 반복자를 반환
equal_range(value)	lower_bound와 upper_bound를 한 번에 반환

---

⦁ set과 unordered_set의 차이

특징	set	unordered_set
정렬 여부	자동 정렬	정렬되지 않음
구현 방식	균형 이진 탐색 트리	해시 테이블
시간 복잡도	$O(\log N)$	평균 $O(1)$, 최악 $O(N)$
사용 용도	정렬된 데이터를 유지해야 하는 경우	빠른 검색이 필요한 경우