set是C++中的一種關聯容器，具有以下特點：

• 存儲唯一元素（不允許重復）

• 元素自動排序（默認升序）

• 基于紅黑樹實現（平衡二叉搜索樹）

• 插入、刪除和查找的時間復雜度為O(log n)

---

前言

在C++標準模板庫(STL)中，set和pair是兩個非常重要且常用的組件。set是一種關聯式容器，提供高效的查找、插入和刪除操作；pair則是將兩個值組合成一個單元的實用工具。本文將深入探討它們的特性、用法以及實際應用場景。

1.?pair?模板類詳解

1.1?pair?的基本概念

pair?是 C++ 標準模板庫中的一個實用模板類，定義在?<utility>?頭文件中。它將兩個值組合成一個單元，這兩個值可以是相同或不同的類型。

#include <utility>  // 包含pair的定義
#include <iostream>
using namespace std;int main() {// 創建pair的三種方式pair<int, string> p1(1, "Apple");  // 直接構造auto p2 = make_pair(2, "Banana");  // 使用make_pair函數pair<int, string> p3 = {3, "Orange"};  // C++11統一初始化// 訪問pair的成員cout << "p1: " << p1.first << ", " << p1.second << endl;cout << "p2: " << p2.first << ", " << p2.second << endl;cout << "p3: " << p3.first << ", " << p3.second << endl;return 0;
}

pair<T1, T2>?模板接受兩個類型參數? ? ?first?和?second?是pair的兩個公有成員，用于訪問存儲的值? ? ? ?make_pair?可以自動推導類型，比直接構造更簡潔

1.2?pair?的比較操作

pair支持比較運算符，按照字典序進行比較：先比較first，如果first相等再比較second。

pair<int, int> a(1, 2);
pair<int, int> b(1, 3);
pair<int, int> c(2, 1);cout << boolalpha;
cout << (a < b) << endl;  // true (1==1, 2<3)
cout << (a < c) << endl;  // true (1<2)
cout << (b < c) << endl;  // true (1<2)

2.?set?容器詳解

set?的構造和初始化

#include <iostream>
#include <set>
using namespace std;int main() {// 空setset<int> s1;// 初始化列表(C++11)set<int> s2 = {3, 1, 4, 1, 5};  // 實際存儲1,3,4,5// 使用數組范圍初始化int arr[] = {2, 4, 6, 4, 2};set<int> s3(arr, arr + 5);  // 存儲2,4,6// 拷貝構造set<int> s4(s3);// 輸出set內容cout << "s2: ";for(int num : s2) cout << num << " ";cout << "\ns3: ";for(int num : s3) cout << num << " ";return 0;
}

set?會自動去重和排序? ? ?可以使用數組指針作為迭代器范圍初始化? ? 基于范圍的for循環可以方便地遍歷set

set?的常用操作

插入元素

set<string> fruits;
fruits.insert("Apple");
fruits.insert("Banana");
fruits.insert("Orange");// 檢查插入是否成功
auto ret = fruits.insert("Apple");  // 嘗試重復插入
if(!ret.second) {cout << "Apple already exists in set" << endl;
}

刪除元素

// 通過值刪除
fruits.erase("Banana");// 通過迭代器刪除
auto it = fruits.find("Orange");
if(it != fruits.end()) {fruits.erase(it);
}// 刪除范圍
set<int> nums = {1, 2, 3, 4, 5};
nums.erase(nums.find(2), nums.find(4));  // 刪除[2,4)

查找元素

set<int> s = {10, 20, 30, 40, 50};// 使用find()
auto it = s.find(30);
if(it != s.end()) {cout << "Found: " << *it << endl;
}// 使用count()
if(s.count(25) > 0) {cout << "25 exists" << endl;
} else {cout << "25 doesn't exist" << endl;
}

如果找到元素：返回指向該元素的迭代器? ?如果找不到元素：返回?s.end()，即指向?set?末尾的迭代器（不指向任何有效元素）。

set?與?pair?的結合使用

// 使用pair作為set的元素
set<pair<int, string>> studentScores;
studentScores.insert({90, "Alice"});
studentScores.insert({85, "Bob"});
studentScores.insert({95, "Charlie"});// 遍歷
for(const auto& entry : studentScores) {cout << entry.second << ": " << entry.first << endl;
}/*
輸出：
Bob: 85
Alice: 90
Charlie: 95
*/

性能對比

操作	時間復雜度	說明
insert()	O(log n)	插入元素并保持有序
erase()	O(log n)	刪除元素
find()	O(log n)	查找元素
count()	O(log n)	檢查元素是否存在
size()	O(1)	獲取元素數量
empty()	O(1)	檢查是否為空

pair、set?和?map?的聯系與區別

特性	std::pair	std::set	std::map
元素類型	任意兩種類型的組合	單一類型	pair<const Key, Value>
元素數量	固定兩個成員(first和second)	動態變化	動態變化
排序方式	無排序	按元素值排序	按鍵排序
唯一性	不適用	元素值唯一	鍵唯一
訪問方式	直接訪問.first和.second	通過迭代器	通過鍵或迭代器
查找效率	不適用	O(log n)	O(log n)
插入操作	直接構造	insert()/emplace()	insert()/emplace()/operator[]
典型應用場景	多返回值、map元素	需要唯一且有序的集合	鍵值對關聯存儲
內存結構	連續存儲兩個成員	樹狀結構	樹狀結構
修改限制	兩個成員都可修改	元素不可修改(只能刪除后插入)	鍵不可修改，值可修改

std::set?的 "元素值唯一"

含義：set?中存儲的每個元素值都必須是唯一的，不能有重復。

std::set<int> numbers = {1, 2, 2, 3}; // 實際存儲：{1, 2, 3}

??????底層機制：set?在插入新元素時，會檢查是否已存在相同的值。如果存在，則不會插入。

std::map?的 "鍵唯一"

含義：map?中每個元素的鍵（key）必須是唯一的，但值（value）可以重復

std::map<std::string, int> ages = {{"Alice", 25},{"Bob", 25},    // 值可以重復{"Alice", 30}   // 鍵重復！第二個 "Alice" 會覆蓋第一個
};

兩個鍵?"Alice"?沖突時，后者會覆蓋前者的值（最終?"Alice"?對應?30）。值?25?可以重復出現（如?"Alice"?和?"Bob"?的值都是?25）

---

總結

pair?和?set?是C++ STL中非常重要的兩個組件：

pair 用于將兩個值組合成一個單元? ?set?用于維護一個唯一、有序的集合

它們可以單獨使用，也可以結合使用（例如?set<pair<T1, T2>>）。理解它們的特性和正確使用方式，可以大大提高C++編程的效率和質量。

?