C++ STL 中 set 和 map 容器的使用。set 基于红黑树实现，用于 key 搜索，支持有序存储且自动去重；map 同样基于红黑树，用于 key/value 搜索，key 有序。文章涵盖了构造方式、迭代器遍历、增删查操作（insert, find, erase, count, lower_bound, upper_bound）以及 multiset/multimap 的差异。通过代码示例演示了 pair 类型的使用、operator[] 的功能特性，并结合 LeetCode 题目展示了在链表判环和前 K 个高频单词统计中的实际应用。
概述
序列式容器和关联式容器是 STL 的重要组成部分。序列式容器（如 vector、list）逻辑结构为线性序列，元素按存储位置顺序保存和访问。关联式容器（如 map、set）逻辑结构通常是非线性的，元素按关键字保存和访问。
使用 set 和 map 头文件：
#include <set>
#include <map>
set 的声明如下，T 就是 set 底层关键字的类型。set 默认要求 T 支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模板参数。set 底层是用红黑树实现，增删查效率是 O(logN)，迭代器遍历是走的搜索树的中序，所以是有序的。
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 支持正向和反向迭代遍历，遍历默认按升序顺序。set 的 iterator 和 const_iterator 都不支持迭代器修改数据，修改关键字数据会破坏底层搜索树的结构。
底层代码展示：
// 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& = 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 begin(); iterator end();
reverse_iterator rbegin(); reverse_iterator rend();
相关函数原参数展示：
Member types
key_type -> The first template parameter (T)
value_type -> The first template parameter (T)
// 单个数据插入，如果已经存在则插入失败
pair<iterator,bool> insert (const value_type& val);
// 列表插入，已经在容器中存在的值不会插入
void insert (initializer_list<value_type> il);
// 迭代器区间插入，已经在容器中存在的值不会插入
template <class InputIterator> void insert (InputIterator first, InputIterator last);
// 查找 val，返回 val 所在的迭代器，没有找到返回 end()
iterator find (const value_type& val);
// 查找 val，返回 Val 的个数
size_type count (const value_type& val) const;
// 删除一个迭代器位置的值
iterator erase (const_iterator position);
// 删除 val，val 不存在返回 0，存在返回 1
size_type erase (const value_type& val);
// 删除一段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);
// 返回大于等 val 位置的迭代器
iterator lower_bound (const value_type& val) const;
// 返回大于 val 位置的迭代器
iterator upper_bound (const value_type& val) const;
int main() {
set<int> s;
s.insert(19);
s.insert(5);
s.insert(10);
int arr[] = { 2,6,4,8 ,5};
//去重插入
s.insert(arr, arr + 4);
for (auto e : s) cout << e << " ";
cout << endl;
set<string> str({ "hello", "world", "love" });
// 遍历 string 比较 ascll 码大小遍历
for (auto& e : str) {
cout << e << " ";
}
cout << endl;
int n;
cin >> n;
int num = s.erase(n);
if (num == 0) cout << n << "不存在" << endl;
else cout << "删除成功" << endl;
for (auto e : s) cout << e << " ";
return 0;
}
不能给常量赋值：
set<int> ::iterator it = s2.begin();
while (it != s2.end()) {
cout << *it << " ";
*it = 1; //错误写法
it++;
}
int main() {
set<int> s = { 4,2,7,2,8,5,9 };
for (auto e : s) {
cout << e << " ";
}
cout << endl;
auto pos = s.find(7);
if (pos != s.end()) {
s.erase(pos);
}
for (auto e : s) {
cout << e << " ";
}
cout << endl;
int x;
cout << "删除的数" << endl;
cin >> x;
auto pos1 = find(s.begin(), s.end(), x); //O(N)查找
while (pos1 != s.end()) {
cout << x << "存在，并删除成功！" << endl;
break;
}
for (auto e : s) {
cout << e << " ";
}
cout << endl;
// 利用 count 间接实现快速查找
int y;
cin >>y;
if (s.count(y)) {
cout << y << "在！" << endl;
} else {
cout << y << "不存在！" << endl;
}
return 0;
}
我们通过了 set 自带的查找以及算法库的查找，然后也用了 set 中的 count 进行了间接查找，通过数据的次数进行判断。
// 返回大于等 val 位置的迭代器
iterator lower_bound (const value_type& val) const;
// 返回大于 val 位置的迭代器
iterator upper_bound (const value_type& val) const;
两个函数的区间是左闭右开的：
int main() {
set<int>s;
for (int i = 1; i <= 9; i++) {
s.insert(i * 10);
}
auto it = s.begin();
while (it != s.end()) {
cout << *it << " ";
it++;
}
cout << endl;
auto itlow = s.lower_bound(30); //set<int>:: iterator itup = s.upper_bound(70);
auto itup = s.upper_bound(70);
s.erase(itlow, itup);
for (auto e : s) {
cout << e << " ";
}
//lower_bound（30）返回一个迭代器 30，而 upper_bound（70）返回一个迭代器 80。
return 0;
}
multiset 和 set 的使用基本完全类似，主要区别点在于 multiset 支持值冗余，那么 insert/find/count/erase 都围绕着支持值冗余有所差异，具体参看下面的样例代码理解。
int main() {
// 相比 set 不同的是，multiset 是排序，但是不去重
multiset<int> s = { 4,2,7,2,4,8,4,5,4,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;
}
在数据结构链表篇，我们采用了双指针的算法，先定义快慢指针判断链表是否带环，如果相遇，则链表有环存在，然后定义一个 meet 指针在相遇的位置，头结点和 meet 同时往前移动，相遇的时候就是环的位置。
在学习了 set 之后，我们可以将节点存放到 set 中，当 set 中节点个数重复的时候说明有环的存在，就可以返回该节点位置。
class Solution { public:
ListNode *detectCycle(ListNode *head) {
set<ListNode*>s;
ListNode*cur=head;
while(cur){
if(s.count(cur)) return cur;
else s.insert(cur);
cur=cur->next;
}
return NULL;
}
};
map 的声明如下，Key 就是 map 底层关键字的类型，T 是 map 底层 value 的类型，set 默认要求 Key 支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模板参数，map 底层存储数据的内存是从空间配置器申请的。一般情况下，我们都不需要传后两个模板参数。map 底层是用红黑树实现，增删查改效率是 O(logN)，迭代器遍历是走的中序，所以是按 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>存储键值对数据。
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 的支持正向和反向迭代遍历，遍历默认按 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& = 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 begin(); iterator end();
reverse_iterator rbegin(); reverse_iterator rend();
map 增接口，插入的 pair 键值对数据，跟 set 所有不同，但是查和删的接口只用关键字 key 跟 set 是完全类似的，不过 find 返回 iterator，不仅仅可以确认 key 在不在，还找到 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
size_type erase (const key_type& k);
// 删除一段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);
// 返回大于等 k 位置的迭代器
iterator lower_bound (const key_type& k);
// 返回大于 k 位置的迭代器
const_iterator lower_bound (const key_type& k) const;
前面提到 map 支持修改 mapped_type 数据，不支持修改 key 数据，修改关键字数据，破坏了底层搜索树的结构。map 第一个支持修改的方式时通过迭代器，迭代器遍历时或者 find 返回 key 所在的 iterator 修改，map 还有一个非常重要的修改接口 operator[]，但是 operator[] 不仅仅支持修改，还支持插入数据和查找数据，所以他是一个多功能复合接口。
需要注意从内部实现角度，map 这里把我们传统说的 value 值，给的是 T 类型，typedef 为 mapped_type。而 value_type 是红黑树结点中存储的 pair 键值对值。
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>
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;
}
int main() {
map<string, string>dict{ { "left","左边"},{"right", "右边"}, { "insert", "插入"}};
pair<string, string>kv( "first","第一个" );
dict.insert(kv);
dict.insert(pair<string, string>{"second", "第二个"});
dict.insert(make_pair("third", "第三个"));
dict.insert({ "string","字符串" });
// 插入时只看 key，value 不相等不会更新
dict.insert({ "left", "自动的 xxxx" });
map<string, string>::iterator it = dict.begin();
while (it != dict.end()) {
//cout << (*it).first << "->" << (*it).second << endl;
//it->first+='x'; key 不能修改
//it->second += 'x';//值可以修改
cout << it->first << ":" << it->second << endl;
// << it.operator->()->first << ":"<<it.operator->()->second << endl;
it++;
}
dict.insert({ "string","字符串串"});//string 存在，插入失败
cout << "输入查询的单词" << endl;
string s;
while (cin >> s) {
auto ret = dict.find(s);
if (ret != dict.end()) {
cout << "->" << ret->second << endl;
break;
} else {
cout << "没有该单词，请重新输入！" << endl;
}
}
dict.erase("second");
auto it1 = dict.find("first");
dict.erase(it1);
for (auto s : dict) {
cout << s.first << "->" << s.second << endl;
}
return 0;
}
前提引入 如果我们要统计一个物件的数目，我们就可以采 map 结构，例如下面代码：
int main() {
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
map<string, int>countMap;
for (auto&s : arr) {
auto pos = countMap.find(s);
if (pos == countMap.end()) {
countMap.insert({ s,1 });
} else pos->second++;
}
for (auto s : countMap) {
cout << s.first << "->" << s.second << endl;
}
return 0;
}
先查找水果在不在 map 中 1、不在，说明水果第一次出现，则插入{水果，1}2、在，则查找到的节点中水果对应的次数++
这里使用常见的 insert 来进行数数，通过对 [] 的认识，我们可以利用它的特点同样的来实现计数的功能。
int main() {
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
map<string, int>cm;
for (const auto& str : arr) {
cm[str]++;
}
for (auto& s : cm) {
cout << s.first << "->" << s.second << endl;
}
return 0;
}
[] 拆分讲解
int main() {
map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
// key 不存在->插入 {"insert", string()}
dict["insert"];
// 插入 + 修改
dict["left"] = "左边";
// 修改
dict["left"] = "左边、剩余";
// key 存在->查找
cout << dict["left"] << endl;
for (auto s : dict) {
cout << s.first << "->" << s.second << endl;
}
return 0;
}
multimap 和 map 的使用基本完全类似，主要区别点在于 multimap 支持关键值 key 冗余，那么 insert/find/count/erase 都围绕着支持关键值 key 冗余有所差异，这里跟 set 和 multiset 完全一样，比如 find 时，有多个 key，返回中序第一个。其次就是 multimap 不支持 []，因为支持 key 冗余，[] 就只能支持插入了，不能支持修改。
前 k 个高频单词 692. 前 K 个高频单词 - 力扣（LeetCode）
解决思路 1 用排序找前 k 个单词，因为 map 中已经对 key 单词排序过，也就意味着遍历 map 时，次数相同的单词，字典序小的在前面，字典序大的在后面。那么将数据放到 vector 中用一个稳定的排序就可以实现上面特殊要求，但是 sort 底层是快排，是不稳定的，所以要用 stable_sort，是稳定的。
代码 1：
class Solution { public:
static bool compare(const pair<string,int>&s1,const pair<string,int>&s2){
return s1.second>s2.second;
}
vector<string> topKFrequent(vector<string>& words, int k) {
map<string,int> m;
for(auto &s:words){
m[s]++;
}
vector<pair<string,int>> v(m.begin(),m.end());
stable_sort(v.begin(),v.end(),compare);
vector<string>v1;
for(int i=0;i<k;i++){
v1.push_back(v[i].first);
}
return v1;
}
};
代码 2：
class Solution { public:
struct Compare {
bool operator()(const pair<string, int>& x, const pair<string, int>& y) const {
return x.second > y.second;
}
};
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());
// 仿函数控制降序
stable_sort(v.begin(), v.end(), Compare());
//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;
}
};
解决思路 2 将 map 统计出的次数的数据放到 vector 中排序，或者放到 priority_queue 中来选出前 k 个。利用仿函数强行控制次数相等的，字典序小的在前面。
class Solution { public:
static bool compare(const pair<string,int>&s1,const pair<string,int>&s2){
return s1.second>s2.second ||(s1.second==s2.second && s1.first<s1.first);
}
vector<string> topKFrequent(vector<string>& words, int k) {
map<string,int> m;
for(auto &s:words){
m[s]++;
}
vector<pair<string,int>> v(m.begin(),m.end());
sort(v.begin(),v.end(),compare);
vector<string>v1;
for(int i=0;i<k;i++){
v1.push_back(v[i].first);
}
return v1;
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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