核心特性
| 特性 | set | multiset |
|---|
| 鍵值唯一性 | 唯一（無重複） | 允許重複 |
| 底層結構 | 紅黑樹（自平衡BST） | 紅黑樹 |
| 元素有序 | 是（按比較函數） | 是 |
| 插入/刪除/查找 | O(log n) | O(log n) |
| 迭代器 | 雙向、const | 雙向、const |
模板參數
template<
class Key, // 鍵類型
class Compare = less, // 比較函數（默認升序）
class Alloc = allocator // 分配器
> class set;
template<
class Key,
class Compare = less,
class Alloc = allocator
> class multiset;
構造函數
// 默認
set s1;
// 區間構造
vector v = {3,1,4,1,5};
set s2(v.begin(), v.end()); // {1,3,4,5}
// 拷貝構造
set s3(s2);
// 自定義比較（降序）
set> s4 = {3,1,4}; // {4,3,1}
核心操作
set
s.insert(x); // 插入，已存在則忽略，返回 pair
s.erase(x); // 刪除值為x的元素，返回刪除個數(0/1)
s.find(x); // 查找，返回迭代器或end()
s.count(x); // 計數（0/1）
s.clear(); // 清空
s.size(); // 大小
s.empty(); // 是否為空
multiset
ms.insert(x); // 插入，允許重複
ms.erase(x); // 刪除**所有**值為x的元素，返回刪除個數
ms.erase(iterator); // 刪除單個元素（需先find）
ms.count(x); // 計數（可>1）
ms.equal_range(x); // 返回 pair 區間
ms.lower_bound(x); // 首個>=x
ms.upper_bound(x); // 首個>x
自定義比較器示例
結構體比較
struct Student { int id; string name; };
// 方式1：仿函數
struct CmpId {
bool operator()(const Student& a, const Student& b) const {
return a.id < b.id;
}
};
set s;
// 方式2：lambda (C++11需包裝)
auto cmp = [](const Student& a, const Student& b){ return a.id < b.id; };
// set s(cmp); // 需傳遞實例
指針容器比較
struct Node { int val; };
struct CmpPtr {
bool operator()(const Node* a, const Node* b) const {
return a->val < b->val;
}
};
set s; // 按val排序指針
multiset 遍歷輸出
multiset ms = {3,1,4,1,5,9,2,6,5};
for(auto it = ms.begin(); it != ms.end(); ++it)
cout << *it << " "; // 1 1 2 3 4 5 5 6 9
總結選擇建議
- **需唯一鍵、有序、高效查找** → `set`
- **允許重複鍵、需統計頻率/區間查詢** → `multiset`
- **需鍵值對映射** → `map`/`multimap`
- **無序、極致查找速度** → `unordered_set`/`unordered_multiset` (C++11)
