std::set 與 std::multiset 是 STL 中基於紅黑樹實現的有序關聯容器,提供對數級別的查找、插入、刪除,並自動維持元素有序。本文從模板定義、構造函數、核心操作到底層實現原理全面解析。
namespace std {
template <class Key,
class Compare = std::less<Key>,
class Allocator = std::allocator<Key>>
class set;
template <class Key,
class Compare = std::less<Key>,
class Allocator = std::allocator<Key>>
class multiset;
}
Key:元素類型,必須滿足 Assignable、CopyConstructible、LessThanComparable(即支持拷賦、複製構造、operator< 或自定義 Compare)。Compare:嚴格弱序(Strict Weak Ordering)——非自反(!comp(x,x))、非對稱(comp(x,y)⇒!comp(y,x))、可傳遞(comp(x,y)&&comp(y,z)⇒comp(x,z))。Allocator:內存分配器,默認 std::allocator。set<int> s1; // 空集合,默認 less<int> 升序
set<int, greater<int>> s2; // 自定義降序
set<int> s3(s1); // 拷貝構造
set<int> s4(vec.begin(), vec.end()); // 區間構造,自動去重排序
multiset<int>> ms1(s4.begin(), s4.end()); // 允許重複元素
s1.size(); // 元素數量
s1.empty(); // 是否為空
s1.max_size(); // 理論最大容量
s1 == s2; // 元素逐一比較(需同類型、同比較準則)
auto it = s.find(key); // 精確查找,O(log n)
auto range = s.equal_range(key); // 返回 pair<lower_bound, upper_bound>
auto lb = s.lower_bound(key); // 首個 ≥ key
auto ub = s.upper_bound(key); // 首個 > key
size_t cnt = s.count(key); // multiset 計數,set 只能 0/1
equal_range 是區間查找、範圍刪除、統計頻次的瑞士軍刀。
// set 返回 pair<iterator, bool>,bool 表示是否插入成功
auto [it, inserted] = s.insert(value);
// multiset 直接返回 iterator
auto it = ms.insert(value);
// 帶提示插入(接近位置可加速)
s.insert(hint_it, value);
// 區間插入
s.insert(vec.begin(), vec.end());
// 刪除
s.erase(key); // 按鍵刪除,返回刪除數量
s.erase(it); // 按迭代器刪除
s.erase(first, last); // 區間刪除
s.clear(); // 清空
// 正序
for (auto it = s.begin(); it != s.end(); ++it) { ... }
for (const auto& v : s) { ... } // C++11 range-based for
// 逆序
for (auto it = s.rbegin(); it != s.rend(); ++it) { ... }
迭代器為雙向迭代器,不支持隨機訪問(無 it + n)。
| 特性 | set | multiset |
|---|---|---|
| 重複元素 | 不允許 | 允許 |
insert 返回值 | pair<iterator,bool> | iterator |
count(key) | 0 或 1 | ≥0 |
| 適用場景 | 鍵值唯一集合、去重 | 詞頻統計、多鍵映射、區間計數 |
Compare 必須可默認構造、拷貝。std::less<> 支持異構查找 s.find("abc") 而不構造 string 對象(需 Key 支持)。extract()/merge() 可在容器間零開銷移動節點,不分配內存。it = s.erase(it) (C++11 返回下一個迭代器)。vector+sort+binary_search;需鍵值映射用 map/unordered_map。set/multiset 是有序、無重/可重、對數級操作的利器。理解其紅黑樹本質、嚴格弱序要求、迭代器失效規則與 C++17 新特性,能在需要有序集合、區間查詢、去重統計的場景寫出高效、健壯的代碼。