跳到主要内容C++ 标准库:map 与 set 容器详解与实战 | 极客日志C++算法
C++ 标准库:map 与 set 容器详解与实战
C++ 标准库中 map 与 set 是常用的关联式容器,基于红黑树实现,提供 O(logn) 的查找效率。内容涵盖序列式与关联式容器的区别,set/multiset 的唯一性约束,map/multimap 的键值对管理。通过构造函数、迭代器遍历、增删查改接口详解,结合 pair 类型与 [] 运算符特性,辅以力扣真题演示数组去重、链表环检测及高频词统计等场景,助您深入理解 STL 核心机制。
观心1 浏览 C++ 标准库:map 与 set 容器详解与实战
在 C++ STL 中,容器主要分为序列式和关联式两大类。理解它们的区别是掌握数据结构的关键。
1. 序列式容器和关联式容器
1.1 序列式容器
- 核心特征
- 按插入顺序存储:物理顺序与插入顺序一致。
- 允许重复元素:可存储多个相同值。
- 通过位置访问:支持索引或迭代器直接访问。
- 常见容器
vector: 动态数组,随机访问快,尾部插入高效。
list: 双向链表,插入/删除快,随机访问慢。
deque: 双端队列,头尾操作高效。
array: 固定大小,编译期确定。
forward_list: 单向链表,内存占用小。
- 适用场景
- 需保持插入顺序(如日志、历史记录)。
- 频繁随机访问(如 vector 的 [] 操作)。
- 需要高效头尾操作(如 deque)。
1.2 关联式容器
- 核心特征
- 按键存储:基于键值对(key-value)组织。
- 自动排序:默认按升序排列。
- 唯一性:
set/map 要求键唯一;multiset/multimap 允许重复。
- 常见容器
set: 唯一键的有序集合。
map: 键值对的有序映射。
multiset: 允许重复键的有序集合。
multimap: 允许重复键的有序映射。
- 适用场景
- 快速查找(如字典、数据库索引)。
- 需自动排序(如排行榜)。
- 需要唯一性约束(如用户 ID 管理)。
2. set 系列的使用
2.1 set 类的介绍
set 底层由红黑树实现,增删查效率为 O(log n)。迭代器遍历遵循中序遍历,因此元素天然有序。默认要求元素类型支持小于比较,若不支持可传入仿函数。
template <class T,
class Compare = less<T>,
class Alloc = allocator<T>>
class set;
2.2 set 的构造函数和迭代器
构造时通常只需关注无参、区间拷贝及初始化列表构造。迭代器为双向迭代器。
explicit set(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
template<class InputIterator>
set(InputIterator first, InputIterator last,
const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
set(const set& x);
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();
2.3 set 的增删查
set 的核心在于去重和排序。插入已存在元素会失败,遍历结果始终有序。
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
s.insert(2); s.insert(1); s.insert(5); s.insert(6);
auto it = s.begin();
while(it != s.end()) {
cout << *it << " ";
++it;
}
cout << endl;
s.insert({1, 5, 3, 2, 7, 9});
for(auto e : s) {
cout << e << " ";
}
cout << endl;
set<string> strset = {"sort", "add", "insert"};
for(auto &e : strset) {
cout << e << " ";
}
cout << endl;
return 0;
}
2.4 find 和 erase 的使用样例
删除操作需注意返回值。erase(key) 返回删除的元素个数,find 返回迭代器。
int main() {
set<int> s = {2, 7, 4, 3, 1, 9, 5, 0};
s.erase(s.begin());
int x; cin >> x;
int num = s.erase(x);
if(num == 0) {
cout << x << "不存在!" << endl;
}
cin >> x;
auto pos = s.find(x);
if(pos != s.end()) {
s.erase(pos);
} else {
cout << x << "不存在" << endl;
}
cin >> x;
if(s.count(x)) {
cout << x << "在!" << endl;
} else {
cout << x << "不存在!" << endl;
}
return 0;
}
删除一段区间的值可以使用 lower_bound 和 upper_bound 定位范围。
int main() {
set<int> myset;
for(int i = 1; i < 10; i++) {
myset.insert(i * 10);
}
auto itlow = myset.lower_bound(30);
auto itup = myset.upper_bound(60);
myset.erase(itlow, itup);
return 0;
}
2.5 multiset 和 set 的差异
multiset 允许键值冗余。find 返回第一个匹配项,count 返回总个数,erase(key) 会删除所有匹配项。
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;
int x; cin >> x;
auto pos = s.find(x);
while(pos != s.end() && *pos == x) {
cout << *pos << " ";
++pos;
}
cout << endl;
cout << s.count(x) << endl;
s.erase(x);
return 0;
}
2.6 力扣实战示例
两个数组的交集
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
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;
}
};
环形链表 II
使用 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 nullptr;
}
};
3. map 系列的使用
3.1 map 类的介绍
map 存储键值对,底层同样是红黑树。Key 必须唯一且有序,Value 可修改但 Key 不可变。
template <class Key,
class T,
class Compare = less<Key>,
class Alloc = allocator<pair<const Key, T>>>
class map;
3.2 pair 类型介绍
map 内部节点存储 pair<const Key, T>。first 为键,second 为值。
template<class T1, class T2>
struct pair {
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
};
template<class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y);
3.3 map 的构造与遍历
支持迭代器遍历,默认按 Key 升序。value 数据可修改,但 Key 不可修改。
explicit map(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
template<class InputIterator>
map(InputIterator first, InputIterator last,
const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
map(const map& x);
map(initializer_list<value_type> il,
const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
3.4 map 的增删查
插入的是 pair 键值对。find 返回迭代器,可直接修改 Value。
pair<iterator, bool> insert(const value_type& val);
void insert(initializer_list<value_type> il);
iterator find(const key_type& k);
size_type count(const key_type& k) const;
iterator erase(const_iterator position);
size_type erase(const key_type& k);
iterator erase(const_iterator first, const_iterator last);
3.5 map 的数据修改
除了通过迭代器修改,operator[] 是一个多功能接口。它既能查找也能插入,还能修改。
mapped_type& operator[](const key_type& k) {
pair<iterator, bool> ret = insert({k, mapped_type()});
iterator it = ret.first;
return it->second;
}
注意:insert 返回的 pair<bool> 中的 bool 表示是否新插入成功,而 map 节点本身存的是 pair<Key, T>,不要混淆。
3.6 构造遍历以及增删查改样例
#include <map>
int main() {
map<string, string> dict = {
{"left", "左边"},
{"right", "右边"},
{"insert", "插入"},
{"erase", "删除"}
};
for(auto it = dict.begin(); it != dict.end(); ++it) {
cout << it->first << ":" << it->second << endl;
}
dict.insert(make_pair("sort", "排序"));
dict.insert({"auto", "自动的"});
for(auto& e : dict) {
cout << e.first << ":" << e.second << endl;
}
string str;
while(cin >> str) {
auto ret = dict.find(str);
if(ret != dict.end()) {
cout << "->" << ret->second << endl;
} else {
cout << "无此单词" << endl;
}
}
return 0;
}
3.7 统计频率实战
统计水果出现次数,演示 [] 运算符的隐式插入功能。
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"};
map<string, int> countMap;
for(const auto& str : arr) {
auto ret = countMap.find(str);
if(ret == countMap.end()) {
countMap.insert({str, 1});
} else {
ret->second++;
}
}
for(const auto& e : countMap) {
cout << e.first << ":" << e.second << endl;
}
return 0;
}
3.8 multimap 和 map 的差异
multimap 支持 Key 冗余,因此不支持 [] 运算符(无法确定修改哪一个),仅支持 insert 等基础操作。
3.9 力扣实战示例
随机链表的复制
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;
}
nodeMap[cur] = copytail;
cur = cur->next;
}
cur = head;
Node* copy = copyhead;
while(cur) {
if(cur->random == nullptr) {
copy->random = nullptr;
} else {
copy->random = nodeMap[cur->random];
}
cur = cur->next;
copy = copy->next;
}
return copyhead;
}
};
前 K 个高频单词
结合 map 统计词频,再用 vector 配合自定义排序获取 Top K。
class Solution {
public:
struct Compare {
bool operator()(const pair<string,int>& kv1, const pair<string,int>& kv2) {
return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);
}
};
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());
sort(v.begin(), v.end(), Compare());
vector<string> retv;
for(size_t i = 0; i < k; ++i) {
retv.push_back(v[i].first);
}
return retv;
}
};
也可使用优先队列(大堆)优化空间复杂度,原理类似,注意堆顶元素的比较规则。
相关免费在线工具
- 加密/解密文本
使用加密算法(如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