빠른 비교
cpp
#include <set>
#include <unordered_set>
std::set<int> s{3, 1, 4, 1, 5}; // 중복 자동 제거, 정렬
// s = {1, 3, 4, 5}
s.insert(2);
s.erase(3);
bool found = s.count(4) > 0; // 또는 s.contains(4) (C++20)
std::unordered_set<std::string> words;
words.insert("hello");
bool exists = words.count("hello") > 0;갈리는 기준
set vs unordered_set — 정렬 여부와 성능
set은 레드-블랙 트리로 항상 정렬된 상태를 유지합니다. 삽입·삭제·탐색이 O(log n)입니다. unordered_set은 해시 테이블로 평균 O(1)이지만 정렬 순서가 없고 최악 O(n)(해시 충돌)입니다.
cpp
std::set<int> s{5, 3, 1, 4, 2};
for (int x : s) std::cout << x << " "; // "1 2 3 4 5" — 정렬됨
std::unordered_set<int> u{5, 3, 1, 4, 2};
for (int x : u) std::cout << x << " "; // 순서 불정존재 확인 — count vs contains vs find
cpp
std::set<std::string> tags{"cpp", "stl", "containers"};
// count — 0 또는 1 반환 (set은 중복 없음)
if (tags.count("cpp")) { ... }
// contains (C++20) — 가장 명확
if (tags.contains("cpp")) { ... }
// find — 반복자 반환 (위치 정보 필요 시)
auto it = tags.find("stl");
if (it != tags.end()) use(*it);multiset / unordered_multiset — 중복 허용
set/unordered_set은 중복을 허용하지 않습니다. 같은 값을 여러 번 저장해야 하면 multiset/unordered_multiset을 사용합니다.
cpp
#include <set>
#include <unordered_set>
std::multiset<int> ms{3, 1, 4, 1, 5, 1};
// ms = {1, 1, 1, 3, 4, 5} — 중복 유지, 정렬
ms.count(1); // 3 — 1이 몇 개인지
ms.insert(1); // 또 하나 추가
ms.erase(ms.find(1)); // 1 하나만 삭제 (erase(key)는 모두 삭제)
// 동일 값의 범위 순회
auto [lo, hi] = ms.equal_range(1); // 모든 1의 구간
for (auto it = lo; it != hi; ++it)
std::cout << *it << " "; // 1 1 1 1
// unordered_multiset — 해시 기반, 정렬 없음
std::unordered_multiset<std::string> words;
words.insert("hello");
words.insert("hello"); // 중복 허용
words.count("hello"); // 2사용자 정의 타입 — 비교 함수 또는 해시
set은 operator<가, unordered_set은 operator==와 해시 함수가 필요합니다.
cpp
struct Point { int x, y; };
// set — operator< 제공
struct PointCmp {
bool operator()(const Point& a, const Point& b) const {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
};
std::set<Point, PointCmp> ps;
// unordered_set — 해시 + == 제공
struct PointHash {
size_t operator()(const Point& p) const {
return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 16);
}
};
struct PointEq {
bool operator()(const Point& a, const Point& b) const {
return a.x == b.x && a.y == b.y;
}
};
std::unordered_set<Point, PointHash, PointEq> ups;체크포인트
| 상황 | 적합한 선택 |
|---|---|
| 중복 제거 + 정렬 순서 필요 | std::set |
| 중복 제거 + 빠른 조회 | std::unordered_set |
| 중복 허용 + 정렬 | std::multiset |
| 중복 허용 + 빠른 조회 | std::unordered_multiset |
| 존재 확인 (C++20) | s.contains(key) |
| 존재 확인 (C++17 이하) | s.count(key) > 0 |
| 중복 개수 확인 | ms.count(key) (multiset) |
| 중복 중 하나만 삭제 | ms.erase(ms.find(key)) |
| 벡터 중복 제거 | set 생성 후 복사, 또는 sort + unique |
주의할 점
set의 원소는 수정할 수 없습니다. 수정이 필요하면 삭제 후 재삽입해야 합니다.
cpp
std::set<std::string> s{"hello", "world"};
// ❌ set 원소 직접 수정 불가 (const 반복자)
auto it = s.find("hello");
*it = "HELLO"; // 컴파일 오류 — set 원소는 const
// ✅ 삭제 후 재삽입
s.erase(it);
s.insert("HELLO");참고 링크
1 sources