跳到主要内容
set 和 map 底层实现详解及 LeetCode 高频算法实战 | 极客日志
C++ 算法
set 和 map 底层实现详解及 LeetCode 高频算法实战 set 与 map 基于红黑树实现,提供有序存储与高效查找。内容涵盖构造方式、迭代器使用、删除时的迭代器失效处理及 lower_bound 用法。通过两个数组交集、环形链表检测、随机链表深拷贝及前 K 个高频单词四个 LeetCode 案例,展示如何结合容器特性解决实际问题,避免暴力解法,提升算法思维与编码效率。
人间失格 发布于 2026/3/16 更新于 2026/5/22 13 浏览set 与 map 底层实现详解
set 类的实现
set 的声明中,T 代表底层关键字的类型。默认情况下,set 要求类型 T 支持比较运算;如果不支持或需要自定义排序规则,可以通过仿函数作为第二个模板参数传入。
内存方面,set 底层数据由空间配置器分配,若需优化性能,可自定义内存池并传给第三个参数。
核心特性:
底层结构 :红黑树(RB Tree)。
时间复杂度 :增删查均为 O(logN)。
有序性 :迭代器遍历遵循中序遍历,天然升序排列。
set 的构造和迭代器
插入整数时,set<int> s 会自动完成排序和去重。
#include <iostream>
#include <set>
using namespace std;
int main () {
set<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;
return 0 ;
}
降序排列 :使用 greater<int> 作为比较器,比根节点大的数传向左子树,反之向右,实现降序。
此外,set 支持 initializer_list 初始化列表插入,重复值会被自动忽略。
s.insert ({2 , 3 , 4 , 5 });
for (auto e : s) {
cout << e << " " ;
}
set: erase 和 find
删除操作 由于 set 默认升序,删除最小值可直接移除起始迭代器:
删除指定值时,erase 返回被删除元素的个数(对于 set 通常是 0 或 1):
int x;
cin >> x;
int num = s.erase (x);
if (num == 0 ) {
cout << x << "不存在" << endl;
} else {
cout << x << "删除成功" << endl;
}
更推荐的方式 是使用 find 获取迭代器后删除,这样能避免多次查找开销:
auto pos = s.find (x);
if (pos != s.end ()) {
s.erase (pos);
cout << x << "删除成功" << endl;
} else {
cout << x << "不存在" << endl;
}
注意迭代器失效问题 :
调用 erase(pos) 后,pos 指向的节点已被销毁,该迭代器立即失效。此时再访问 *pos 会导致野指针错误。如果是删除根节点,虽然红黑树结构通过替代法维持了平衡,但原迭代器依然无效。
查找效率 容器自带的 find 方法效率更高(O(logN)),优于算法库中的 std::find(O(N)):
auto pos1 = find (s.begin (), s.end (), x);
auto pos2 = s.find (x);
set: count 利用 count 进行存在性判断。在 set 中,元素唯一,返回值非 0 即 1。
if (s.count (x)) {
cout << x << "在集合中" << endl;
} else {
cout << x << "不在集合中" << endl;
}
set: lower_bound 和 upper_bound #include <iostream>
#include <set>
using namespace std;
int main () {
set<int > mset;
for (int i = 1 ; i < 10 ; i++) {
mset.insert (i * 10 );
}
auto itlow = mset.lower_bound (30 );
auto itup = mset.upper_bound (50 );
mset.erase (itlow, itup);
for (auto e : mset) {
cout << e << " " ;
}
return 0 ;
}
multiset 和 set multiset 与 set 用法类似,主要区别在于允许键值冗余(不去重)。multiset 仅排序,保留所有重复项。
查找时,find 会返回中序遍历遇到的第一个匹配项。通过不断递增迭代器,可以遍历出所有相同的值。
map:insert map 的 insert 返回值为 pair<iterator, bool>。
插入成功 :返回新插入节点的迭代器和 true。
插入失败 :返回已存在 key 对应节点的迭代器和 false。
pair<iterator, bool > ret = insert ({k, mapped_type ()});
map: operator[] operator[] 是 map 最便捷的访问方式,其内部逻辑如下:
mapped_type& operator [](const key_type& k) {
pair<iterator, bool > ret = insert ({k, mapped_type ()});
iterator it = ret.first;
return it->second;
}
Key 不存在 :尝试插入 {k, 默认值}。插入成功后,返回新值的引用。适合统计词频等场景。
Key 存在 :插入失败,直接返回已存在值的引用。适合修改映射值。
int main () {
string myarray[] = {"秋" , "冬" , "夏" , "春" , "夏" , "秋" , "夏" , "春" , "夏" , "秋" , "秋" , "冬" };
map<string, int > countMap;
for (const auto & e : myarray) {
countMap[e]++;
}
for (const auto & it : countMap) {
cout << it.first << ":" << it.second << endl;
}
return 0 ;
}
multimap 和 map 的差异
Key 冗余 :multimap 支持 Key 重复,map 不支持。
Find 行为 :multimap 的 find 返回第一个匹配的迭代器,若有多个相同 Key,需配合 equal_range 或循环遍历。
Operator[] :multimap 不支持 operator[],因为无法确定修改哪一个重复 Key 对应的值。
LeetCode 经典题目实战
两个数组的交集
将两个数组分别转为 set,去除重复元素并排序。
使用双指针遍历两个 set。
若 *it1 < *it2,说明 it1 当前值不可能是交集,it1++。
若相等,加入结果集,两指针均 ++。
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;
}
};
环形链表
遍历链表,检查当前节点是否在 set 中。
若在,说明遇到环,返回该节点。
若不在,插入 set 并继续向后。
若走到 nullptr,无环。
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 ;
}
};
随机链表的复制 思路 :深拷贝需要处理 random 指针,使用 map<Node*, Node*> 建立原节点与新节点的映射关系。
第一遍遍历:创建新节点,建立映射 randomMap[ptr] = copytail。
第二遍遍历:根据映射表设置新节点的 random 指针。
class Solution {
public :
Node* copyRandomList (Node* head) {
map<Node*, Node*> randomMap;
Node* copyhead = nullptr , *copytail = nullptr ;
Node* ptr = head;
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;
}
Node* copy = copyhead;
ptr = head;
while (ptr) {
if (ptr->random) {
copy->random = randomMap[ptr->random];
}
copy = copy->next;
ptr = ptr->next;
}
return copyhead;
}
};
前 K 个高频单词 思路 :统计频率 -> 转换为 Vector -> 自定义排序。
使用 map<string, int> 统计词频,map 天然按键字典序排序。
将 map 转为 vector<pair<string, int>>。
使用 stable_sort 进行稳定排序。当频率相同时,保持原有顺序(即字典序)。
取前 K 个元素。
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 map 底层结构 红黑树 红黑树 遍历顺序 升序(中序) Key 升序(中序) 修改 Value 不支持(Key 不可变) 支持(Value 可变) 修改 Key 不支持(破坏树结构) 不支持(破坏树结构) 迭代器 双向迭代器 双向迭代器
总结来说,set 关注 Key 的唯一性与有序性,而 map 在此基础上增加了 Key 到 Value 的映射能力。在实际开发中,理解它们的底层机制有助于写出更高效、更安全的代码。
相关免费在线工具 加密/解密文本 使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
Gemini 图片去水印 基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
Markdown转HTML 将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online