您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

STL set 容器完全指南：底層原理、核心操作與性能分析

編輯：關於C++

前言

std::set 是 C++ STL 中基於紅黑樹實現的有序關聯容器，元素唯一且自動排序。本文從底層數據結構、迭代器失效機制、時間複雜度特性、核心成員函數用法、實戰代碼示例五個維度全面解析，助你高效掌握這個高性能容器。

一、底層原理：紅黑樹

數據結構：紅黑樹（RB-Tree），一種自平衡二叉搜索樹，統計性能優於普通 AVL 樹。
節點佈局：每個節點包含值、顏色（紅/黑）、父/左/右指針，類似鏈表節點。
插入/刪除高效原因：僅調整指針指向，無內存拷貝與移動開銷。
迭代器穩定性：迭代器本質是節點指針，內存地址不變 ⇒ 插入/刪除其他元素不會導致迭代器失效（被刪除元素的迭代器除外）。

二、時間複雜度與擴展性

操作	平均/最壞複雜度	說明
查找	O(log n)	二分搜索，樹高 ~ log₂(n)
插入	O(log n)	查找位置 + 旋轉調整（常數次）
刪除	O(log n)	查找節點 + 旋轉調整
遍歷	O(n)	中序遍歷即有序序列

擴展性極強：元素從 1 萬增至 2 萬，查找比較次數僅從 14 次增至 15 次（log₂ 增長極慢）。

三、核心成員函數速查表

1. 容量與狀態

begin()          // 首元素迭代器
end()            // 尾後迭代器
rbegin()/rend()  // 反向迭代器
empty()          // 是否為空
size()           // 元素個數
max_size()       // 理論最大容量
clear()          // 清空所有元素

注意：begin()/end() 不檢查空容器，使用前建議先 empty() 判斷。

2. 查找與計數


find(key)              // 找到返回迭代器，否則 end()
count(key)             // set 中鍵值唯一，返回 0 或 1（實用性較低）
lower_bound(key)       // 首個 ≥ key 的迭代器
upper_bound(key)       // 首個 > key 的迭代器
equal_range(key)       // 返回 pair

3. 插入操作


insert(value)                    // 返回 pair
insert(first, last)              // 區間插入，返回 void
insert(iterator hint, value)     // 帶提示位置插入（C++11）
emplace(args...)                 // 原地構造，避免拷貝/移動

4. 刪除操作


erase(iterator pos)              // 刪除單個元素
erase(iterator first, last)      // 刪除區間
erase(key)                       // 按鍵值刪除，返回刪除個數

警告：erase 不進行合法性檢查，傳入無效迭代器行為未定義。

四、實戰代碼示例

1. 基礎操作演示

#include 
#include 
using namespace std;

int main() {
    set s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(1); // 重複值被忽略

    cout << "size: " << s.size() << endl; // 3
    cout << "elements: ";
    for (int x : s) cout << x << ' '; // 1 2 3
    cout << endl;

    // 查找
    auto it = s.find(2);
    if (it != s.end()) cout << "found: " << *it << endl;

    // 範圍查詢
    auto range = s.equal_range(2);
    cout << "lower_bound(2): " << *range.first << endl;  // 2
    cout << "upper_bound(2): " << *range.second << endl; // 3

    // 刪除
    s.erase(s.begin());        // 刪除 1
    s.erase(3);                // 刪除鍵值 3
    cout << "after erase: ";
    for (int x : s) cout << x << ' '; // 2
    cout << endl;
    return 0;
}

2. 區間插入與批量構造

int arr[] = {5, 2, 8, 1, 9};
set s(arr, arr + 5); // 直接從數組構造，自動去重排序
// 或
vector v = {5, 2, 8, 1, 9};
set s2(v.begin(), v.end());

3. 自定義比較器（降序/自定義類型）


// 降序 set
set> desc = {1, 3, 2}; // 3 2 1

// 自定義結構體
struct Student {
    string name;
    int score;
    bool operator<(const Student& other) const {
        return score < other.score; // 按分數升序
    }
};
set students = {{"Alice", 90}, {"Bob", 85}};

4. 高級用法：區間查詢與統計

set scores = {60, 75, 80, 85, 90, 95};
// 統計 [80, 90] 分數段人數
auto it_low = scores.lower_bound(80);
auto it_up  = scores.upper_bound(90);
int count = distance(it_low, it_up); // 3 (80,85,90)