demo

#include <iostream>
#include <set>int main() {// 創建一個存儲整數的std::setstd::set<int> mySet;// 插入元素mySet.insert(300);mySet.insert(1);mySet.insert(2);mySet.insert(3);  mySet.insert(3);  // 重復元素不會被插入mySet.insert(300);  // 重復元素不會被插入mySet.insert(300);  // 重復元素不會被插入// 輸出集合中的元素std::cout << "Set elements: ";for (auto it = mySet.begin(); it != mySet.end(); ++it){std::cout << *it << " ";}std::cout << std::endl;// 查找元素auto findIt = mySet.find(2);if (findIt != mySet.end()){std::cout << "Element 2 found in the set." << std::endl;} else{std::cout << "Element 2 not found in the set." << std::endl;}// 刪除元素mySet.erase(1);std::cout << "Set elements after erasing 1: ";for (auto it = mySet.begin(); it != mySet.end(); ++it){std::cout << *it << " ";}std::cout << std::endl;// 檢查集合是否為空if (mySet.empty()) {std::cout << "The set is empty." << std::endl;}else{std::cout << "The set is not empty." << std::endl;}// 獲取集合的大小std::cout << "The size of the set is: " << mySet.size() << std::endl;// 清除集合中所有內容mySet.clear();std::cout << "Set elements after clearing: ";for (auto it = mySet.begin(); it != mySet.end(); ++it){std::cout << *it << " ";}std::cout << std::endl;// 再次檢查集合是否為空if (mySet.empty()){std::cout << "The set is empty after clearing." << std::endl;} else {std::cout << "The set is not empty after clearing." << std::endl;}return 0;
}    

代碼解釋：

1. 創建集合：使用std::set<int> mySet;創建一個存儲整數的std::set。
2. 插入元素：通過insert方法向集合中插入元素，重復元素不會被插入。
3. 遍歷集合：使用迭代器遍歷集合中的元素并輸出。
4. 查找元素：使用find方法查找指定元素，如果找到則返回指向該元素的迭代器，否則返回end()。
5. 刪除元素：使用erase方法刪除指定元素。
6. 檢查集合是否為空：使用empty方法檢查集合是否為空。
7. 獲取集合大小：使用size方法獲取集合中元素的數量。

底層原理

在C++標準庫中，std::set 是一個關聯容器，用于存儲唯一的元素，并且這些元素會按照一定的順序排列（默認是升序）。它的底層通常基于紅黑樹（Red - Black Tree）這種自平衡二叉搜索樹（Self - Balancing Binary Search Tree）來實現

1. 二叉搜索樹基礎

二叉搜索樹（Binary Search Tree，BST）是一種二叉樹，對于樹中的每個節點，其左子樹中的所有節點的值都小于該節點的值，而右子樹中的所有節點的值都大于該節點的值。這種特性使得在二叉搜索樹中進行查找、插入和刪除操作的平均時間復雜度為 $O(logn)$，其中 $n$ 是樹中節點的數量。

2. 紅黑樹的特性

紅黑樹是一種自平衡的二叉搜索樹，它在每個節點上增加了一個存儲位來表示節點的顏色（紅色或黑色）。通過對任何一條從根到葉子的路徑上各個節點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出兩倍，因而是接近平衡的。紅黑樹必須滿足以下五個性質：

• 每個節點要么是紅色，要么是黑色。
• 根節點是黑色。
• 每個葉子節點（NIL節點，空節點）是黑色的。
• 如果一個節點是紅色的，則它的兩個子節點都是黑色的。
• 對每個節點，從該節點到其所有后代葉節點的簡單路徑上，均包含相同數目的黑色節點。

3. std::set 基于紅黑樹的實現優勢

• 有序性：由于紅黑樹是一種二叉搜索樹，插入到 std::set 中的元素會根據元素的鍵值自動排序。例如，插入整數時會按照從小到大的順序排列。
• 唯一性：在插入元素時，紅黑樹會進行比較，如果發現元素已經存在，則不會插入，保證了 std::set 中元素的唯一性。
• 高效的查找、插入和刪除操作：紅黑樹的自平衡特性保證了樹的高度始終保持在 $O(logn)$ 級別，因此查找、插入和刪除操作的時間復雜度都是 $O(logn)$。

4. 插入操作

當向 std::set 中插入一個新元素時，底層的紅黑樹會執行以下步驟：

• 按照二叉搜索樹的規則找到新元素應該插入的位置。
• 將新元素插入到該位置，并將其顏色設置為紅色。
• 檢查紅黑樹的性質是否被破壞，如果破壞了則通過一系列的顏色調整和旋轉操作來恢復紅黑樹的性質。

5. 刪除操作

當從 std::set 中刪除一個元素時，紅黑樹會執行以下步驟：

• 按照二叉搜索樹的規則找到要刪除的節點。
• 如果該節點有兩個子節點，則用其右子樹中的最小節點替換該節點，然后刪除右子樹中的最小節點。
• 刪除節點后，檢查紅黑樹的性質是否被破壞，如果破壞了則通過一系列的顏色調整和旋轉操作來恢復紅黑樹的性質。

6. 查找操作

查找操作相對簡單，根據二叉搜索樹的特性，從根節點開始比較，如果要查找的元素值小于當前節點的值，則在左子樹中繼續查找；如果大于當前節點的值，則在右子樹中繼續查找；如果相等，則找到了該元素。由于紅黑樹的高度為 $O(logn)$，因此查找操作的時間復雜度也是 $O(logn)$。

綜上所述，std::set 基于紅黑樹實現，利用紅黑樹的特性保證了元素的有序性、唯一性以及高效的查找、插入和刪除操作。