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++编程的效率和质量。