1. 개요
std::set은 고유한 값을 자동으로 정렬하여 저장하는 연관 컨테이너입니다. 내부적으로 이진 탐색 트리(Red-Black Tree)를 기반으로 동작하며, <set> 헤더에 정의되어 있습니다.
#include <set>
std::set<int> s = {3, 1, 4};
2. 주요 특징
- 자동 정렬 (기본: 오름차순)
- 중복 허용하지 않음
- 균형 이진 트리 기반 (Red-Black Tree)
- 삽입/삭제/검색 시간 복잡도: O(log N)
- 반복자는 순서대로 순회
3. 주요 멤버 함수
🔹 크기 관련
| 함수 |
설명 |
empty() |
비었는지 확인 |
size() |
요소 수 반환 |
clear() |
모든 요소 삭제 |
🔹 삽입/삭제
| 함수 |
설명 |
insert(val) |
요소 삽입 |
emplace(args...) |
직접 생성하여 삽입 |
erase(val) |
값으로 제거 |
erase(iterator) |
반복자로 제거 |
erase(first, last) |
범위 삭제 |
swap(other) |
다른 set과 교환 |
🔹 탐색
| 함수 |
설명 |
find(val) |
값 탐색, 반복자 반환 |
count(val) |
값의 개수 (0 또는 1) |
lower_bound(val) |
val 이상 첫 위치 반복자 |
upper_bound(val) |
val 초과 첫 위치 반복자 |
equal_range(val) |
[lower, upper) 쌍 반환 |
4. 반복자 관련
| 함수 |
설명 |
begin() / end() |
정방향 반복자 |
rbegin() / rend() |
역방향 반복자 |
cbegin() / cend() |
const 반복자 |
5. 예제 코드
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s = {10, 20, 20, 30};
s.insert(25);
s.erase(10);
for (int val : s) {
cout << val << " ";
}
cout << endl;
if (s.find(20) != s.end()) {
cout << "20 found" << endl;
}
return 0;
}
6. std::set vs std::unordered_set
| 항목 |
std::set |
std::unordered_set |
| 정렬 여부 |
자동 정렬 |
정렬 없음 |
| 내부 구조 |
트리 |
해시 테이블 |
| 시간 복잡도 |
O(log N) |
평균 O(1) |
| 반복 순서 |
정렬됨 |
정의되지 않음 |
7. 커스텀 정렬
struct Descending {
bool operator()(int a, int b) const {
return a > b;
}
};
std::set<int, Descending> s2 = {1, 2, 3};
8. 주의사항
- 중복 값을 저장하려면
std::multiset 사용
- 반복자를 통해 원소를 직접 수정할 수 없음 (const)
- 기본 정렬은
operator< 기반
Comments