核心特性
- 有序唯一/可重複：
set 元素唯一，multiset 允許重複，皆依 Compare (預設 less<T>) 遞增排序。
- 底層紅黑樹：插入/刪除/查找均為 O(log n)，迭代器失效規則：僅指向被刪除元素的迭代器失效，其餘保持有效。
- 元素需滿足：
Assignable、CopyConstructible、LessThanComparable (或提供自訂 Compare 滿足 Strict Weak Ordering)。
常用建構函數
set<T> s1; // 空容器
set<T, Compare> s2(comp); // 自訂排序準則
set<T> s3(s2); // 複製建構
set<T> s4(first, last); // 區間建構
set<T, Compare> s5(first, last, comp); // 區間+自訂排序
核心操作函數速查
| 分類 | 函數 | 回傳/說明 |
|---|
| 容量 | size() | 元素個數 |
empty() | 是否為空 |
max_size() | 理論最大容量 |
operator==/!=/</>/<=/>= | 字典序比較 |
| 查找 | count(k) | 鍵值為 k 的元素數 (set 為 0/1，multiset 可 >1) |
find(k) | 指向首個 k 的迭代器，無則 end() |
lower_bound(k) | 首個 !comp(elem, k) (即 ≥ k) 的迭代器 |
upper_bound(k) | 首個 comp(k, elem) (即 > k) 的迭代器 |
equal_range(k) | pair<lower_bound, upper_bound> |
| 修改 | insert(val) | set 回傳 pair<iter, bool>；multiset 回傳 iter |
insert(pos, val) | 提示位置插入，回傳迭代器 |
insert(first, last) | 區間插入，無回傳 |
erase(k) | 移除所有 k，回傳移除數量 |
erase(pos) / erase(first, last) | 移除指定位置/區間，無回傳 |
clear() | 清空容器 |
| 交換 | swap(s2) | 常數時間交換內容 |
operator= | 複製賦值 |
迭代器類別
iterator / const_iterator：雙向迭代器，++/--、*、->。reverse_iterator / const_reverse_iterator：rbegin()/rend() 反向遍歷。- 元素視為 const：
*it 為 const T&，不可透過迭代器修改元素值 (需刪除重插)。
set vs multiset 插入語意差異
// set：唯一性檢查
pair<set<int>::iterator, bool> r = s.insert(42);
if (r.second) cout << "插入成功" << *r.first;
else cout << "已存在" << *r.first;
// multiset：允許重複，直接回傳迭代器
multiset<int> ms;
ms.insert(42);
ms.insert(42); // 兩個 42 共存
auto range = ms.equal_range(42); // 取得所有 42 的區間
自訂排序準則範例
// 降序 set
struct Desc { bool operator()(int a, int b) const { return a > b; } };
set<int, Desc> descSet = {5, 2, 9, 1}; // 9,5,2,1
// 依字串長度排序
struct ByLen { bool operator()(const string& a, const string& b) const {
return a.size() < b.size() || (a.size() == b.size() && a < b);
}};
set<string, ByLen> lenSet;
效能與使用建議
- 大量插入時，先
vector 收集 → sort + unique → set 區間建構，比逐筆 insert 快得多。
- 需頻繁查找、範圍查詢、有序遍歷用
set/multiset；單純查找用 unordered_set (O(1) 平均)。
- 避免在迭代器遍歷中直接
erase(it++) 以外方式刪除，C++11 起 erase 回傳下一有效迭代器：it = s.erase(it)。
