set 类的实现
set 的声明中，T 代表底层关键字类型。默认要求 T 支持比较运算，若需自定义规则可传入仿函数作为第二个模板参数。内存分配方面，底层从空间配置器申请，也可自行实现内存池。
set 基于红黑树实现，增删查复杂度为 O(logN)。迭代器遍历遵循中序遍历，因此数据天然有序（升序）。
set 的构造和迭代器
插入整数时，set<int> s 会自动完成排序与去重。
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
// set<int, greater<int>> s; // 降序排列
s.insert(4);
s.insert(3);
s.insert(8);
s.insert(9);
s.insert(2);
s.insert(6);
auto it = s.begin();
while (it != s.end()) {
cout << *it << " ";
++it;
}
cout << endl; // 输出：2 3 4 6 8 9
return 0;
}
注意：set 不支持修改元素值，一旦修改会破坏红黑树结构，编译器通常会报错。
支持 initializer_list 初始化，重复插入会被忽略。
set: erase 和 find
删除最小值可直接使用 s.erase(s.begin())。
查找元素时，容器自身的 find 效率高于算法库的 find（O(logN) vs O(N)）。
// 直接删除指定值，返回删除的元素个数
int num = s.erase(x);
if (num == 0) {
cout << x << "不存在" << endl;
} else {
cout << x << "删除成功" << endl;
}
// 通过迭代器删除
auto pos = s.find(x);
if (pos != s.end()) {
s.erase(pos);
cout << x << "删除成功" << endl;
}
迭代器失效问题：调用 erase 后，指向被删除节点的迭代器立即失效，切勿再次解引用。
set: count
利用 count 判断元素是否存在，存在返回 1，否则返回 0。
set: lower_bound 和 upper_bound
用于查找区间。lower_bound 返回第一个大于等于目标值的迭代器，upper_bound 返回第一个大于目标值的迭代器。两者结合可实现左闭右开区间的删除。
set<int> mset;
for (int i = 1; i < 10; i++) mset.insert(i * 10);
auto itlow = mset.lower_bound(30); // >= 30
auto itup = mset.upper_bound(50); // > 50
mset.erase(itlow, itup); // 删除 [30, 50] 区间内的值
multiset 和 set
区别在于 multiset 允许键值冗余，仅排序不去重。查找时会返回中序遍历的第一个匹配项，配合迭代器自增可遍历所有相同键值。
map: insert
insert 返回值是 pair<iterator, bool>。插入成功返回新节点迭代器和 true；插入失败（Key 已存在）返回已有节点迭代器和 false。这使其兼具插入与查找功能。
map: operator[]
内部逻辑相当于先尝试插入 {k, mapped_type()}，若 Key 不存在则创建默认值，若存在则直接返回引用。
string myarray[] = {"秋", "冬", "夏", "春", ...};
map<string, int> countMap;
for (const auto& e : myarray) {
countMap[e]++; // 自动处理计数逻辑
}
若 Key 不存在，operator[] 会构造默认值（如 int 为 0），再返回引用进行自增；若 Key 存在，直接返回引用自增。这使得统计词频变得异常简单。
multimap 和 map 的差异
multimap 支持 Key 冗余，不支持 operator[]（因为无法确定修改哪一个冗余值），但支持 find 返回第一个匹配项。
力扣题目实战
1. 两个数组的交集
利用 set 去重特性，将两数组转为 set 后，使用双指针遍历寻找相等元素。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> ret;
set<int> s1(nums1.begin(), nums1.end());
set<int> s2(nums2.begin(), nums2.end());
auto it1 = s1.begin();
auto it2 = s2.begin();
while (it1 != s1.end() && it2 != s2.end()) {
if (*it1 < *it2) {
++it1;
} else if (*it1 > *it2) {
++it2;
} else {
ret.push_back(*it1);
++it1;
++it2;
}
}
return ret;
}
};
2. 环形链表
利用 set 存储访问过的节点指针。若当前节点已在 set 中，说明发现环，返回该节点；若遍历结束未重复，则无环。
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
set<ListNode*> s;
ListNode* cur = head;
while (cur) {
if (s.count(cur)) return cur;
s.insert(cur);
cur = cur->next;
}
return nullptr;
}
};
3. 随机链表的复制
深拷贝 random 指针需要建立原节点与新节点的映射关系。先用一次遍历构建 next 并记录映射 randomMap[ptr] = copytail，第二次遍历根据映射设置 random 指针。
class Solution {
public:
Node* copyRandomList(Node* head) {
map<Node*, Node*> randomMap;
Node* copyhead = nullptr, *copytail = nullptr;
Node* ptr = head;
// 第一次遍历：构建 next 并建立映射
while (ptr) {
if (!copytail) {
copytail = copyhead = new Node(ptr->val);
} else {
copytail->next = new Node(ptr->val);
copytail = copytail->next;
}
randomMap[ptr] = copytail;
ptr = ptr->next;
}
// 第二次遍历：设置 random
Node* copy = copyhead;
ptr = head;
while (ptr) {
if (ptr->random) {
copy->random = randomMap[ptr->random];
}
copy = copy->next;
ptr = ptr->next;
}
return copyhead;
}
};
4. 前 k 个高频单词
统计词频用 map，排序用 vector + stable_sort。利用 map 天然的字典序特性，配合稳定排序，可实现'频率降序，频率相同则字典序升序'的规则。
class Solution {
public:
struct kvFunction {
bool operator()(const pair<string, int>& w1, const pair<string, int>& w2) {
return w1.second > w2.second; // 次数多的在前
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> countMap;
for (auto& it : words) countMap[it]++;
vector<pair<string, int>> v(countMap.begin(), countMap.end());
stable_sort(v.begin(), v.end(), kvFunction());
vector<string> ret;
for (int i = 0; i < k; i++) {
ret.push_back(v[i].first);
}
return ret;
}
};
set 和 map 的构造对比
- Set: 支持正向/反向遍历，默认升序。迭代器不可修改 key，否则破坏树结构。
- Map: 支持正向/反向遍历，按 key 升序。value 可修改，key 不可修改。
两者底层均为红黑树，保证了高效的查找与有序性。