std::set
- 1. 概述
- 定義
- 特點
- 2. 內部實現
- 3. 性能特征
- 4. 常用 API
- 5. 使用示例
- 6. 自定義比較器
- 7. 注意事項與優化
- 8. 使用建議
1. 概述
定義
template<class Key,class Compare = std::less<Key>,class Allocator = std::allocator<Key>
>
class std::set;
特點
-
有序：所有元素按嚴格弱序（由 Compare 決定）排列，不保證相同鍵的重復出現（鍵唯一）。
-
唯一鍵：插入時如果集合中已有相同元素，不會增加新的節點。
-
底層結構：通常基于紅黑樹（balanced binary search tree）實現。
2. 內部實現
-
紅黑樹
- 平衡二叉查找樹，保證從根到任一葉子路徑的“黑色節點數”相同，從而令樹高度為 O(log n)。
-
節點結構
- 每個節點存儲：
- 元素值 Key
- 左/右子指針和父指針
- 一個顏色標記（紅或黑）
- 每個節點存儲：
-
拷貝與移動
- 拷貝時會對整棵樹進行深拷貝；移動構造則接管底層指針，無需逐節點復制。
3. 性能特征
| 操作 | 平均復雜度 | 最壞復雜度 | 備注 |
|---|---|---|---|
| insert | O(log n) | O(log n) | 包括查找插入位置與調整平衡 |
| erase | O(log n) | O(log n) | 按鍵刪除時需旋轉與重著色 |
| find | O(log n) | O(log n) | |
| clear | O(n) | O(n) | 釋放所有節點 |
| 遍歷 | O(n) | O(n) | 中序遍歷即可 |
-
內存開銷：
- 每個節點需存儲三個指針（左右、父）和一個顏色字段，相比哈希表更緊湊但比 std::vector 等順序容器要高。
-
迭代器失效規則：
- 插入和刪除會使僅被刪除的節點的迭代器失效，其他節點迭代器保持有效。
4. 常用 API
// 構造與析構
std::set<Key> s1; // 默認構造
std::set<Key> s2({k1, k2, k3}); // 初始化列表
std::set<Key, Compare> s3(comp); // 指定比較器// 大小與容量
bool empty() const noexcept;
size_t size() const noexcept;
size_t max_size() const noexcept;// 元素訪問
iterator find(const Key& key);
size_t count(const Key& key) const; // 要么 0，要么 1// 插入
std::pair<iterator,bool> insert(const Key& key);
iterator insert(iterator hint, const Key& key);
template<class... Args>
std::pair<iterator,bool> emplace(Args&&... args);// 刪除
size_t erase(const Key& key);
iterator erase(iterator pos);
iterator erase(iterator first, iterator last);// 遍歷
iterator begin() noexcept;
iterator end() noexcept;
const_iterator cbegin() const noexcept;
const_iterator cend() const noexcept;// 有序查詢
iterator lower_bound(const Key& key); // ≥ key 的第一個位置
iterator upper_bound(const Key& key); // > key 的第一個位置
std::pair<iterator,iterator> equal_range(const Key& key);// 比較器與分配器訪問
Compare key_comp() const;
Compare value_comp() const; // 同 key_comp
Allocator get_allocator() const noexcept;// 交換
void swap(std::set& other) noexcept;
5. 使用示例
#include <set>
#include <iostream>int main() {std::set<int> s;// 插入s.insert(3);s.emplace(1);s.insert({5, 2, 4});// 查找if (s.find(2) != s.end()) {std::cout << "2 存在\n";}// 遍歷（中序：1,2,3,4,5）for (int x : s) {std::cout << x << " ";}std::cout << "\n";// 有序查詢auto it = s.lower_bound(3); // 指向 3std::cout << "lower_bound(3): " << *it << "\n";// 刪除s.erase(3); // 刪除值為 3 的節點// 范圍刪除s.erase(s.begin(), s.lower_bound(4)); // 刪除所有 <4 的元素// 清空s.clear();
}
6. 自定義比較器
當需要自定義排序規則（如降序或復合鍵）時，可提供自定義比較器：
struct Desc {bool operator()(int a, int b) const {return a > b; // 降序}
};std::set<int, Desc> s_desc; // 插入后，將按從大到小順序存儲
對于復合類型：
struct Person {std::string name;int age;
};struct ByAgeName {bool operator()(Person const& a, Person const& b) const {if (a.age != b.age) return a.age < b.age;return a.name < b.name;}
};// 年齡升序，若年齡相同則按名字升序
std::set<Person, ByAgeName> roster;
7. 注意事項與優化
-
避免不必要的拷貝
- insert(const Key&) 會拷貝一次；若可移動，優先使用 insert(Key&&) 或 emplace()。
-
hint 參數
- insert(hint, key)：若能提供一個接近正確位置的迭代器 hint，可將插入復雜度降到常數時間。
-
批量插入
- 對初始化列表或范圍插入，建議先 reserve()（C++23 起支持）或構造時傳入范圍，以減少重平衡次數。
-
避免迭代器失效
- 刪除或插入僅影響相關節點迭代器，其他迭代器保持有效。
8. 使用建議
-
適用場景
- 需要自動排序且元素唯一時，首選 std::set。
- 需要查詢前驅/后繼、區間操作（lower_bound、upper_bound、中序遍歷）時非常方便。
-
不適用場景
- 需要允許重復鍵或多對一映射時，改用 std::multiset 或 std::map。
- 對性能有極致要求且不在意順序時，可考慮 std::unordered_set（哈希實現，平均 O(1)）。
