C++算法
C++ map 与 set 容器使用详解
C++ STL 中的 set 和 map 是常用的关联式容器。set 存储唯一键值并自动排序，底层为红黑树；map 存储键值对，同样基于红黑树实现高效查找。两者的构造函数、迭代器使用、增删查改操作及 multiset/multimap 的区别。通过 pair 类型讲解键值对存储，并结合力扣题目演示了实际应用场景，如数组交集、环形链表检测及随机链表复制等。
C++ STL 中的 set 和 map 是常用的关联式容器。set 存储唯一键值并自动排序，底层为红黑树；map 存储键值对，同样基于红黑树实现高效查找。两者的构造函数、迭代器使用、增删查改操作及 multiset/multimap 的区别。通过 pair 类型讲解键值对存储，并结合力扣题目演示了实际应用场景，如数组交集、环形链表检测及随机链表复制等。
vector: 动态数组，支持快速随机访问，尾部插入高效。list: 双向链表，支持快速插入/删除，但随机访问效率低。deque: 双端队列，支持头尾高效插入/删除。array: 固定大小数组，编译时确定大小。forward_list: 单向链表，内存占用更小。set和map要求键唯一；multiset和multimap允许重复键。set: 存储唯一键的有序集合。map: 存储键值对的有序映射。multiset: 允许重复键的有序集合。multimap: 允许重复键的有序映射。set的声明如下，T 就是set底层关键字的类型。set默认要求 T 支持小于比较，如果不支持，可以手动实现一个仿函数传给第二个模板参数。set底层存储数据的内存是从空间配置器上申请的，如果需要可以自己手动实现一个内存池，传给第三个参数。set的底层是用红黑树实现的，增删查的效率是 O(log n)，迭代器遍历走的是搜索树的中序遍历，所以遍历后的元素是有序的。template <class T, // set::key_type/value_type
class Compare = less<T>, // set::key_compare/value_compare
class Alloc = allocator<T> // set::allocator_type
>
class set;
set的构造我们只需关注一下几个即可
// empty (1) 无参默认构造
explicit set(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
// range (2) 迭代器区间构造
template <class InputIterator>
set(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
// copy (3) 拷贝构造
set(const set& x);
// initializer list (5) initializer 列表构造
set(initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
迭代器
// 迭代器是一个双向迭代器 iterator -> a bidirectional iterator to const value_type
// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();
#include <iostream>
#include <set>
using namespace std;
int main() {
// 去重 + 升序排序
set<int> s;
// 去重 + 降序排序，给一个大于的仿函数
// set<int, greater<int>> s;
// set<int, greater<int>> s = {1, 2, 7, 4, 9, 6};
// initializer_list 初始化
s.insert(2);
s.insert(1);
s.insert(5);
s.insert(6);
auto it = s.begin();
while(it != s.end()) {
//*it = 1; 不能修改里面的值
cout << *it << " ";
it++;
}
cout << endl;
// 插入一段 initilizer_list 的值，已经存在则插入失败
s.insert({1, 5, 3, 2, 7, 9});
for(auto e : s) {
cout << e << " ";
}
cout << endl;
// 插入 string 类对象，string 类对象比较是按照 ascii 码来比较大小的
set<string> strset = {"sort", "add", "insert"};
for(auto &e : strset) {
cout << e << " ";
}
cout << endl;
return 0;
}
erase, find的使用案例：
int main() {
set<int> s = {2, 7, 4, 3, 1, 9, 5, 0};
for(auto &e : s) {
cout << e << " ";
}
cout << endl;
// 删除最小值
s.erase(s.begin());
for(auto &e : s) {
cout << e << " ";
}
cout << endl;
// 删除输入的值，这个值有可能在，也有可能不在
int x;
cin >> x;
int num = s.erase(x);
if(num == 0) {
cout << x << "不存在!" << endl;
}
for(auto &e : s) {
cout << e << " ";
}
cout << endl;
// 直接查找，再利用迭代器删除
cin >> x;
auto pos = s.find(x);
if(pos != s.end()) {
s.erase(pos);
} else {
cout << x << "不存在" << endl;
}
for(auto &e : s) {
cout << e << " ";
}
cout << endl;
// 算法库中的查找 O(n) 不会这样使用
// auto pos1 = find(s.begin(), s.end(), x);
// set 自己实现的查找 O(log n)
auto pos2 = s.find(x);
// 利用 count 快速实现间接查找
cin >> x;
if(s.count(x)) {
cout << x << "在!" << endl;
} else {
cout << x << "不存在!" << endl;
}
return 0;
}
删除一段区间的值
int main() {
set<int> myset;
for(int i = 1; i < 10; i++) {
myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
}
for(auto e : myset) {
cout << e << " ";
}
cout << endl;
// 实现查找到的 [itlow, itup] 包含 [30, 60] 区间
// 返回>=30
auto itlow = myset.lower_bound(30);
// 返回>60
auto itup = myset.upper_bound(60);
// 删除这段区间的值
myset.erase(itlow, itup);
for(auto e : myset) {
cout << e << " ";
}
cout << endl;
return 0;
}
multiset和set基本完全相似，主要的区别点在于multiset支持键值冗余，那么insert/find/count/erase都围绕着支持键值冗余有所差异。
int main() {
multiset<int> s = {4, 6, 4, 3, 6, 7, 8, 9, 2, 5, 3, 7, 8, 9};
auto it = s.begin();
while(it != s.end()) {
cout << *it << " ";
++it;
}
cout << endl;
// 相比较 set 不同的是，x 可能会存在多个，find 查找的是中序的第一个
int x;
cin >> x;
auto pos = s.find(x);
while(pos != s.end() && *pos == x) {
cout << *pos << " ";
++pos;
}
cout << endl;
// 相比 set 不同的是 count 会返回 x 的实际个数
cout << s.count(x) << endl;
// 相比 set 不同的是 erase 会删掉里面的所有的 x
s.erase(x);
for(auto e : s) {
cout << e << " ";
}
cout << endl;
return 0;
}
题目连接： 349. 两个数组的交集
解题思路： 两个数组依次比较，小的++，相等的就是交集，同时++，其中一个结束就结束了
代码实现：
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
// 这里用 set 实现了对数组的排序 + 去重
set<int> s1(nums1.begin(), nums1.end());
set<int> s2(nums2.begin(), nums2.end());
// 小的++，相等就是交集
vector<int> ret;
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;
}
};
题目链接： 142. 环形链表 II
解题思路： 遍历这个环形链表，如果count为 0，就把此节点插入进set，如果不为 0，则此节点为入口点。
代码实现：
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
set<ListNode*> s;
ListNode* cur = head;
while(cur) {
if(s.count(cur)) return cur; // 等于 1 即为入口点
else s.insert(cur);
cur = cur->next;
}
return nullptr;
}
};
map的声明如下，Key 就是 map 底层关键字的类型，T 是 map 底层 Value 的类型，map 默认要求 Key 支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模板参数。map底层存储数据的内存是从空间配置器申请的。一般情况下我们都不需要传后面两个模板参数。map的底层使用红黑树实现的，增删查改的效率是 O(log n)，迭代器遍历走的是中序遍历，所以 Key 的值是有序的。
template <class Key, // map::key_type
class T, // map::mapped_type
class Compare = less<Key>, // map::key_compare
class Alloc = allocator<pair<const Key, T>> // map::allocator_type
>
class map;
map底层红黑树节点中的数据，使用 pair<Key,T>存储键值对数据。
pair是一个类模板，里面有两个成员变量，一个是first，一个是second。
typedef pair<const Key, T> value_type;
template <class T1, class T2>
struct pair {
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2()) {}
pair(const T1& a, const T2& b): first(a), second(b) {}
template <class U, class V>
pair(const pair<U, V>& pr): first(pr.first), second(pr.second) {}
};
template <class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y) {
return pair<T1, T2>(x, y);
}
map的构造我们只需关注以下接口即可
map支持正向迭代器遍历和反向迭代器遍历，遍历默认按 Key 的升序，因为底层是二叉搜索树，走的是中序遍历。支持迭代器也就支持范围 for。map支持value数据的修改，但不支持Key的修改。修改关键字的数据破坏了底层搜索树的结构。
// empty (1) 无参默认构造
explicit map(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
// range (2) 迭代器区间构造
template <class InputIterator>
map(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
// copy (3) 拷贝构造
map(const map& x);
// initializer list (5) initializer 列表构造
map(initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
// 迭代器是一个双向迭代器 iterator -> a bidirectional iterator to const value_type
// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();
map的增删查关注以下接口即可
map的增接口，插入的是 pair 的键值对数据，跟set有所不同，但是查和删的接口只用关键字 Key，跟set完全相似。不过 find 返回的是iterator，不仅仅可以找到 Key 在不在，还能找到映射的 Value，同时通过迭代还能修改 Value。
Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type, mapped_type>
// 单个数据插入，如果已经 key 存在则插入失败，key 存在相等 value 不相等也会插入失败
pair<iterator, bool> insert(const value_type& val);
// 列表插入，已经在容器中存在的值不会插入
void insert(initializer_list<value_type> il);
// 迭代器区间插入，已经在容器中存在的值不会插入
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
// 查找 k，返回 k 所在的迭代器，没有找到返回 end()
iterator find(const key_type& k);
// 查找 k，返回 k 的个数
size_type count(const key_type& k) const;
// 删除一个迭代器位置的值
iterator erase(const_iterator position);
// 删除 k，k 存在返回 0，存在返回 1 (原文档可能有误，通常返回 1 表示删除成功)
size_type erase(const key_type& k);
// 删除一段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
// 返回大于等于 k 位置的迭代器
iterator lower_bound(const key_type& k);
const_iterator lower_bound(const key_type& k) const;
map 第一个支持修改的方式是通过迭代器，迭代器遍历时或者 find 返回 Key 所在的 iterator 修改。map 还有一个非常重要的修改接口operator[]，但是operator[]不仅仅支持数据的修改，还支持插入数据和查找数据，所以它是一个多功能复合接口。
Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type, mapped_type>
// 查找 k，返回 k 所在的迭代器，没有找到返回 end()，如果找到了通过 iterator 可以修改 key 对应的 mapped_type 值
iterator find(const key_type& k);
// 文档中对 insert 返回值的说明
// The single element versions (1) return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to the element with an equivalent key in the map.
// The pair::second element in the pair is set to true if a new element was inserted or false if an equivalent key already existed.
// insert 插入一个 pair<key, T>对象
// 1、如果 key 已经在 map 中，插入失败，则返回一个 pair<iterator,bool>对象，返回 pair 对象 first 是 key 所在结点的迭代器，second 是 false
// 2、如果 key 不在 map 中，插入成功，则返回一个 pair<iterator,bool>对象，返回 pair 对象 first 是新插入 key 所在结点的迭代器，second 是 true
// 也就是说无论插入成功还是失败，返回 pair<iterator,bool>对象的 first 都会指向 key 所在的迭代器
// 那么也就意味着 insert 插入失败时充当了查找的功能，正是因为这一点，insert 可以用来实现 operator[]
// 需要注意的是这里有两个 pair，不要混淆了，一个是 map 底层红黑树节点中存的 pair<key, T>，另一个是 insert 返回值 pair<iterator, bool>
pair<iterator, bool> insert(const value_type & val);
mapped_type& operator[](const key_type& k);
// operator 的内部实现
mapped_type& operator[](const key_type& k) {
// 1、如果 k 不在 map 中，insert 会插入 k 和 mapped_type 默认值（默认值是用默认构造构造的），同时 [] 返回结点中存储 mapped_type 值的引用，那么我们可以通过引用修改返映射值。所以 [] 具备了插入 + 修改功能
// 2、如果 k 在 map 中，insert 会插入失败，但是 insert 返回 pair 对象的 first 是指向 key 结点的迭代器，返回值同时 [] 返回结点中存储 mapped_type 值的引用，所以 [] 具备了查找 + 修改的功能
pair<iterator, bool> ret = insert({k, mapped_type()});
iterator it = ret.first;
return it->second;
}
#include <map>
int main() {
pair<string, string> kv1 = {"left", "左边"};
// initializer_list 构造以及迭代遍历
map<string, string> dict = {{"left", "左边"}, {"right", "右边"}, {"insert", "插入"}, {"erase", "删除"}};
map<string, string>::iterator it = dict.begin();
while(it != dict.end()) {
// cout << *it << " "; // pair 不支持流提取和流插入，是一个结构体
// cout << (*it).first << ":" << (*it).second << endl;;
cout << it->first << ":" << it->second << endl;
// cout << it.operator->()->first << ":" << it.operator->()->second << endl;
// 原生写法
++it;
}
// map 的插入
// insert 插入 pair 的四种方式，对比之下最后一种最方便
pair<string, string> kv2("first", "第一个");
dict.insert(kv2); // 匿名对象
dict.insert(pair<string, string>("second", "第二个"));
// make_pair
dict.insert(make_pair("sort", "排序"));
// make_pair 是一个函数模板，不用声明模板参数，自己推导，在底层构造一个 pair 对象再返回
// 最后一种最好用
dict.insert({"auto", "自动的"}); // 支持隐式类型转换
// 支持范围 for 遍历
for(auto &e : dict) {
cout << e.first << ":" << e.second << endl;
}
cout << endl;
// 结构化绑定 C++17
// for (const auto& [k,v] : dict) {
// cout << k << ":" << v << endl;
// }
string str;
while(cin >> str) {
auto ret = dict.find(str);
if(ret != dict.end()) {
cout << "->" << ret->second << endl;
} else {
cout << "无此单词，请重新输入" << endl;
}
}
// first 是不能被修改的，但是 second 可以被修改
return 0;
}
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
// 统计水果出现的次数
string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"};
map<string, int> countMap;
// 先查找水果在不在 map 中
// 1. 不在，说明水果第一次出现，则插入水果 {水果，1}
// 2. 在，则查找到的水果对应的次数 +1
for(const auto& str : arr) {
auto ret = countMap.find(str);
if(ret == countMap.end()) { // 则证明在
countMap.insert({str, 1});
} else {
ret->second++;
}
}
// countMap[str]++; 第二种写法
for(const auto& e : countMap) {
cout << e.first << ":" << e.second << endl;
}
cout << endl;
return 0;
}
multimap 和 map 的使用基本完全类似，主要区别是 multimap 支持关键字 Key 冗余，那么insert/find/count/erase都围绕着支持键值冗余有所差异。这里和set和multiset基本一样，比如 find 时有多个 key 返回中序中的第一个。其次是 multimap 不支持 []，因为支持 key 冗余，[]就只能支持插入了，不支持修改。
题目连接： 138. 随机链表的复制
解题思路： 让原链表与拷贝链表通过map建立映射关系
代码实现：
class Solution {
public:
Node* copyRandomList(Node* head) {
map<Node*, Node*> nodeMap;
Node* copyhead = nullptr, *copytail = nullptr;
// 定义一个头一个尾
Node* cur = head;
while(cur) {
// 如果为空
if(copytail == nullptr) {
copyhead = copytail = new Node(cur->val);
}
// 如果不为空
else {
copytail->next = new Node(cur->val);
copytail = copytail->next;
}
// 让原节点和拷贝节点建立 map
nodeMap[cur] = copytail;
cur = cur->next;
}
// 处理 random
cur = head;
Node* copy = copyhead;
while(cur) {
// 原链表的 random 为空，则拷贝链表的 random 也为空
if(cur->random == nullptr) {
copy->random = nullptr;
} else {
copy->random = nodeMap[cur->random];
}
cur = cur->next;
copy = copy->next;
}
return copyhead;
}
};
题目链接： 692. 前 K 个高频单词
解题思路 1： 用排序找前 k 个单词，因为 map 中已经对 Key 单词排序过，也就意味着遍历 map 时次序相同的单词，字典序小的在前面，字典序大的在后面，那么我们将数据放到 vector 中用一个稳定的排序就可以实现上面特殊的要求，但 sort 底层是快排，是不稳定的，所以我们要用stable_sort，是稳定的。
代码实现：
class Solution {
public:
struct Compare {
bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) {
return kv1.second > kv2.second;
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
// 统计次数
map<string, int> countMap;
for(auto& str : words) {
countMap[str]++;
}
vector<pair<string, int>> v(countMap.begin(), countMap.end());
// 迭代器区间初始化
stable_sort(v.begin(), v.end(), Compare());
vector<string> retv;
for(size_t i = 0; i < k ;++i) {
retv.push_back(v[i].first); // 取的是每个 pair 对象中的单词
}
return retv;
}
};
解题思路 2： 将 map 统计出来的次序，放到 vector 中排序，或者放到 priority_queue 中选出前 k 个，利用仿函数强制控制次数相等的，字典序小的在前面。
代码实现：
class Solution {
public:
struct Compare {
bool operator()(const pair<string, int>& x, const pair<string, int>& y) {
return x.second > y.second || (x.second == y.second && x.first < y.first);
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> countMap;
for(auto& e : words) {
countMap[e]++;
}
vector<pair<string, int>> v(countMap.begin(), countMap.end());
// 仿函数控制降序，仿函数控制次数相等，字典序小的在前面
sort(v.begin(), v.end(), Compare());
// 取前 k 个
vector<string> strV;
for(int i = 0; i < k;++i) {
strV.push_back(v[i].first);
}
return strV;
}
};
class Solution {
public:
struct Compare {
bool operator()(const pair<string, int>& x, const pair<string, int>& y) const {
// 要注意优先级队列底层是反的，大堆要实现小于比较，所以这里次数相等，想要字典序小的在前面要比较字典序大的为真
return x.second < y.second || (x.second == y.second && x.first > y.first);
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> countMap;
for(auto& e : words) {
countMap[e]++;
}
// 将 map 中的<单词，次数>放到 priority_queue 中，仿函数控制大堆，次数相同按照字典序规则排序
priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> p(countMap.begin(), countMap.end());
vector<string> strV;
for(int i = 0; i < k;++i) {
strV.push_back(p.top().first);
p.pop();
}
return strV;
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online