萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

C++ STL set/multiset 完全指南:從模板參數到紅黑樹實現與實操技巧

std::set 與 std::multiset 是 STL 中基於紅黑樹實現的有序關聯容器,提供對數級別的查找、插入、刪除,並自動維持元素有序。本文從模板定義、構造函數、核心操作到底層實現原理全面解析。

1. 模板定義與類型要求

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。

2. 底層實現:紅黑樹

  • 所有主流 STL 實現(libstdc++、libc++、MSVC STL)均以紅黑樹實現 set/multiset。
  • 紅黑樹性質:根/葉黑、紅節點子必黑、任意節點到葉子黑高相同。
  • 複雜度保證:插入/刪除/查找 O(log n) 最壞情況;迭代器失效規則:僅被刪除元素的迭代器失效,其餘保持有效。
  • 插入最多 2 次旋轉/重着色;查找路徑長度 ≤ 2×log₂(n+1)。

3. 常用構造與容量操作

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;       // 元素逐一比較(需同類型、同比較準則)

4. 查找與區間操作(核心優勢)

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 是區間查找、範圍刪除、統計頻次的瑞士軍刀。

5. 修改操作

// 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();           // 清空

6. 迭代器遍歷

// 正序
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)。

7. set vs multiset 關鍵差異

特性setmultiset
重複元素不允許允許
insert 返回值pair<iterator,bool>iterator
count(key)0 或 1≥0
適用場景鍵值唯一集合、去重詞頻統計、多鍵映射、區間計數

8. 實戰技巧與避坑

  • 自定義比較器:構造函數傳入函數對象/lambda,注意 Compare 必須可默認構造、拷貝。
  • 透明比較(C++14):std::less<> 支持異構查找 s.find("abc") 而不構造 string 對象(需 Key 支持)。
  • 節點提取/合併(C++17):extract()/merge() 可在容器間零開銷移動節點,不分配內存。
  • 避免迭代器失效誤用:遍歷時刪除用 it = s.erase(it) (C++11 返回下一個迭代器)。
  • 不適用場景:高頻隨機訪問用 vector+sort+binary_search;需鍵值映射用 map/unordered_map。

總結

set/multiset 是有序、無重/可重、對數級操作的利器。理解其紅黑樹本質、嚴格弱序要求、迭代器失效規則與 C++17 新特性,能在需要有序集合、區間查詢、去重統計的場景寫出高效、健壯的代碼。

copyright © 萬盛學電腦網 all rights reserved