目錄
一、set 基本概念
1.1 定義與特點
1.2 頭文件與聲明
1.3 核心特性解析
二、set 底層實現
2.1 紅黑樹簡介
2.2 紅黑樹在 set 中的應用
三、set 常用操作
3.1 插入元素
3.2 刪除元素
3.3 查找元素
3.4 遍歷元素
3.5 性能特征
四、set 高級應用
4.1 自定義比較函數
4.2 交集、并集和差集操作
4.3 與其他容器的結合使用
4.4?迭代器操作
4.5?性能優化技巧
五、set 與其他容器的比較
5.1 set 與 vector
5.2 set 與 unordered_set
5.3 選擇建議
六、注意事項與常見錯誤
6.1 迭代器失效問題
6.2 性能考慮
6.3 內存占用
6.4?易錯點提醒
七、應用場景與實戰案例
八、總結
九、參考資料
在 C++ 編程中，容器是非常重要的工具，它可以幫助我們高效地管理和操作數據。關聯容器是 C++ 標準模板庫（STL）中的一類特殊容器，它們通過鍵（key）來存儲和訪問元素。set?作為關聯容器的一種，在很多場景下都有著廣泛的應用。本文將全面深入地介紹?set?類型，包括其基本概念、底層實現、常用操作、高級應用以及與其他容器的比較等內容。
一、set 基本概念
1.1 定義與特點
set?是一種關聯容器，它用于存儲唯一的元素，并且這些元素會根據其值自動進行排序。在?set?中，鍵（key）和值（value）是相同的，即每個元素既是鍵也是值。由于?set?不允許有重復的元素，因此插入重復元素時會被忽略。
1.2 頭文件與聲明
要使用?set，需要包含?<set>?頭文件。以下是一個簡單的?set?聲明示例：
#include <iostream>
#include <set>int main() {std::set<int> mySet; // 聲明一個存儲 int 類型元素的 setreturn 0;
}1.3 核心特性解析
std::set是基于紅黑樹實現的有序關聯容器，其設計目標是通過平衡二叉搜索樹結構，在保證元素唯一性的同時，實現以下核心特性：
①自動排序機制
- 插入元素時自動按升序排列
- 默認使用
<運算符比較元素 - 支持自定義比較函數
②唯一性約束
- 不允許重復元素
- 插入重復值時自動去重
③對數時間復雜度操作
- 插入：O(log n)
- 刪除：O(log n)
- 查找：O(log n)
④內存動態管理
- 自動處理內存分配/釋放
- 支持迭代器失效保護
二、set 底層實現
2.1 紅黑樹簡介
set?通常使用紅黑樹（Red-Black Tree）作為底層數據結構。紅黑樹是一種自平衡的二叉搜索樹，它通過對節點進行著色（紅色或黑色）并遵循一些特定的規則來保持樹的平衡，從而保證了插入、刪除和查找操作的時間復雜度都是?O(logn)。
紅黑樹的主要特性包括：
- 每個節點要么是紅色，要么是黑色。
- 根節點是黑色。
- 每個葉子節點（NIL 節點，空節點）是黑色。
- 如果一個節點是紅色的，則它的兩個子節點都是黑色的。
- 對每個節點，從該節點到其所有后代葉節點的簡單路徑上，均包含相同數目的黑色節點。
2.2 紅黑樹在 set 中的應用
在?set?中，紅黑樹的節點存儲了?set?中的元素。當插入一個新元素時，set?會根據元素的值將其插入到紅黑樹的合適位置，并通過旋轉和著色操作來保持樹的平衡。查找元素時，set?會從根節點開始，根據元素的值與節點的值進行比較，然后遞歸地在左子樹或右子樹中查找，直到找到目標元素或到達葉子節點。
三、set 常用操作
3.1 插入元素
可以使用?insert()?函數向?set?中插入元素。如果插入的元素已經存在于?set?中，則插入操作會被忽略。
#include <iostream>
#include <set>int main() {std::set<int> mySet;mySet.insert(3);mySet.insert(1);mySet.insert(2);for (const auto& element : mySet) {std::cout << element << " ";}std::cout << std::endl;return 0;
}輸出：1 2 3，因為?set?會自動對元素進行排序。
3.2 刪除元素
可以使用?erase()?函數從?set?中刪除元素。erase()?函數有多種重載形式，可以根據元素的值或迭代器來刪除元素。
#include <iostream>
#include <set>int main() {std::set<int> mySet = {1, 2, 3, 4, 5};mySet.erase(3); // 根據元素的值刪除auto it = mySet.find(4);if (it != mySet.end()) {mySet.erase(it); // 根據迭代器刪除}for (const auto& element : mySet) {std::cout << element << " ";}std::cout << std::endl;return 0;
}3.3 查找元素
可以使用?find()?函數在?set?中查找元素。如果找到元素，則返回指向該元素的迭代器；如果未找到，則返回?end()?迭代器。
#include <iostream>
#include <set>int main() {std::set<int> mySet = {1, 2, 3, 4, 5};auto it = mySet.find(3);if (it != mySet.end()) {std::cout << "Found: " << *it << std::endl;} else {std::cout << "Not found" << std::endl;}return 0;
}3.4 遍歷元素
可以使用范圍?for?循環或迭代器來遍歷?set?中的元素。
#include <iostream>
#include <set>int main() {std::set<int> mySet = {1, 2, 3, 4, 5};// 使用范圍 for 循環遍歷for (const auto& element : mySet) {std::cout << element << " ";}std::cout << std::endl;// 使用迭代器遍歷for (auto it = mySet.begin(); it != mySet.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}3.5 性能特征
| 操作 | 時間復雜度 | 說明 |
|---|---|---|
| insert() | O(log n) | 插入新元素 |
| erase() | O(log n) | 刪除元素 |
| find() | O(log n) | 查找元素 |
| count() | O(log n) | 統計元素出現次數 |
| size() | O(1) | 獲取元素數量 |
| empty() | O(1) | 檢查是否為空 |
四、set 高級應用
4.1 自定義比較函數
默認情況下，set?使用?std::less?作為比較函數來對元素進行排序。如果需要自定義排序規則，可以在聲明?set?時提供自定義的比較函數。
#include <iostream>
#include <set>// 自定義比較函數，實現降序排序
struct Greater {bool operator()(const int& a, const int& b) const {return a > b;}
};int main() {std::set<int, Greater> mySet = {1, 2, 3, 4, 5};for (const auto& element : mySet) {std::cout << element << " ";}std::cout << std::endl;return 0;
}4.2 交集、并集和差集操作
可以使用?<algorithm>?頭文件中的?set_intersection()、set_union()?和?set_difference()?函數來實現?set?的交集、并集和差集操作。
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>int main() {std::set<int> set1 = {1, 2, 3, 4, 5};std::set<int> set2 = {3, 4, 5, 6, 7};std::vector<int> intersection;std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(intersection));std::cout << "Intersection: ";for (const auto& element : intersection) {std::cout << element << " ";}std::cout << std::endl;std::vector<int> unionSet;std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(unionSet));std::cout << "Union: ";for (const auto& element : unionSet) {std::cout << element << " ";}std::cout << std::endl;std::vector<int> difference;std::set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(difference));std::cout << "Difference (set1 - set2): ";for (const auto& element : difference) {std::cout << element << " ";}std::cout << std::endl;return 0;
}4.3 與其他容器的結合使用
set?可以與其他容器（如?vector、list?等）結合使用，以實現更復雜的功能。例如，可以將?vector?中的元素插入到?set?中進行去重和排序。
#include <iostream>
#include <set>
#include <vector>int main() {std::vector<int> vec = {3, 1, 2, 3, 4, 2};std::set<int> mySet(vec.begin(), vec.end());for (const auto& element : mySet) {std::cout << element << " ";}std::cout << std::endl;return 0;
}4.4?迭代器操作
std::set<int> s = {1, 3, 5, 7, 9};// 反向迭代器
std::cout << "反向遍歷: ";
for (auto rit = s.rbegin(); rit != s.rend(); ++rit) {std::cout << *rit << " ";
}// 迭代器失效處理
auto it = s.find(5);
s.erase(it); // 迭代器失效，不可繼續使用4.5?性能優化技巧
批量插入優化：
std::set<int> s;
s.insert({1, 2, 3, 4, 5}); // C++11初始化列表優化emplace原位構造：
s.emplace(10); // 直接在容器內構造對象，避免臨時對象拷貝預留空間（C++11起）：?
s.reserve(100); // 預分配內存減少重分配次數五、set 與其他容器的比較
| 操作 | set | unordered_set | vector有序 |
|---|---|---|---|
| 插入 | O(log n) | O(1)平均 | O(n) |
| 查找 | O(log n) | O(1)平均 | O(log n)二分 |
| 刪除 | O(log n) | O(1)平均 | O(n) |
| 內存占用 | 較高 | 較低 | 緊湊 |
| 有序性 | 始終有序 | 無序 | 需排序 |
5.1 set 與 vector
- 存儲方式：
vector?是一種順序容器，它使用連續的內存空間存儲元素；而?set?是一種關聯容器，使用紅黑樹存儲元素。 - 元素特性：
vector?允許有重復的元素，并且元素的順序是按照插入的順序排列的；set?不允許有重復的元素，并且元素會自動排序。 - 查找效率：
vector?的查找操作的時間復雜度為?O(n)，而?set?的查找操作的時間復雜度為?O(logn)。
5.2 set 與 unordered_set
- 底層實現：
set?使用紅黑樹作為底層數據結構，而?unordered_set?使用哈希表作為底層數據結構。 - 排序特性：
set?中的元素會自動排序，而?unordered_set?中的元素是無序的。 - 查找效率：
unordered_set?的查找操作的平均時間復雜度為?O(1)，而?set?的查找操作的時間復雜度為?O(logn)。
5.3 選擇建議
- 如果需要存儲唯一的元素并且要求元素有序，那么可以選擇?
set。 - 如果只需要存儲唯一的元素，不關心元素的順序，并且對查找效率有較高的要求，那么可以選擇?
unordered_set。 - 如果需要存儲多個相同的元素，并且對元素的順序有要求，那么可以選擇?
vector。
六、注意事項與常見錯誤
6.1 迭代器失效問題
在對?set?進行插入或刪除操作時，可能會導致迭代器失效。例如，在刪除一個元素后，指向該元素的迭代器將失效。因此，在使用迭代器時，需要特別注意避免迭代器失效的問題。
#include <iostream>
#include <set>int main() {std::set<int> mySet = {1, 2, 3, 4, 5};auto it = mySet.find(3);if (it != mySet.end()) {mySet.erase(it); // 刪除元素后，it 迭代器失效// 不能再使用 it 迭代器}return 0;
}6.2 性能考慮
雖然?set?的插入、刪除和查找操作的時間復雜度都是?O(logn)，但在某些情況下，可能會有性能瓶頸。例如，當需要頻繁插入和刪除元素時，紅黑樹的旋轉和著色操作可能會影響性能。此時，可以考慮使用?unordered_set?來提高性能。
6.3 內存占用
由于?set?使用紅黑樹作為底層數據結構，它需要額外的內存來存儲節點的指針和顏色信息。因此，在對內存占用有嚴格要求的場景下，需要謹慎使用?set。
6.4?易錯點提醒
修改元素值：直接修改元素會導致未定義行為
auto it = s.begin();
// *it = 10; // 錯誤！元素是const的迭代器失效：僅刪除操作會使指向被刪元素的迭代器失效
自定義比較函數：需保證嚴格弱序關系
// 錯誤示例：未實現嚴格弱序
struct BadCompare {bool operator()(int a, int b) {return a <= b; // 應該用<}
};七、應用場景與實戰案例
案例1：數據去重排序
std::vector<int> nums = {5, 2, 5, 1, 3, 2};
std::set<int> unique_nums(nums.begin(), nums.end());// 輸出：1 2 3 5
for(int num : unique_nums) {std::cout << num << " ";
}案例2：字典序管理
std::set<std::string> dictionary;void add_word(const std::string& word) {dictionary.insert(word);
}bool check_spelling(const std::string& word) {return dictionary.count(word);
}八、總結
set作為STL中的有序唯一集合容器，在需要維護有序數據且保證元素唯一性的場景中表現卓越。通過紅黑樹實現的高效操作使其成為處理排序、去重、快速查找等需求的理想選擇。掌握set的特性和正確使用方式，將顯著提升C++編程能力。
九、參考資料
- ?《C++ Primer（第 5 版）》這本書是 C++ 領域的經典之作，對 C++ 的基礎語法和高級特性都有深入講解。
- 《Effective C++（第 3 版）》書中包含了很多 C++ 編程的實用建議和最佳實踐。
- 《C++ Templates: The Complete Guide（第 2 版）》該書聚焦于 C++ 模板編程，而
using聲明在模板編程中有著重要應用，如定義模板類型別名等。 - C++ 官方標準文檔：C++ 標準文檔是最權威的參考資料，可以查閱最新的 C++ 標準（如 C++11、C++14、C++17、C++20 等）文檔。例如，ISO/IEC 14882:2020 是 C++20 標準的文檔，可從相關渠道獲取其詳細內容。