本文详细介绍 C++ STL 中 set、multiset、map、multimap 容器的构造、常用操作及底层原理。涵盖元素插入删除、查找迭代、比较操作等接口，并通过 pair 类说明键值对存储机制。结合 LeetCode 经典例题（如数组交集、环形链表、随机链表复制、前 K 个高频单词），演示容器在实际算法场景中的应用，帮助读者掌握关联式容器的核心用法。
本文介绍 C++ STL 中 set、multiset、map、multimap 等关联式容器的使用。
STL 容器主要分为序列式容器和关联式容器。
序列式容器核心特征：
vector[i]）或迭代器顺序访问，不依赖元素值的大小或关系。关联式容器核心特征：
map 容器通过键值对 (key, value) 存储数据，查找时直接通过 key 定位。| 维度 | 序列式容器 | 关联式容器 |
|---|---|---|
| 逻辑结构 | 线性序列（数组、链表等） | 非线性结构（树、哈希表等） |
| 元素关联 | 仅通过位置的顺序关联 | 通过键值的有序或哈希的映射关联 |
| 访问依据 | 存储位置（索引或迭代器） | 关键字（Key） |
| 典型实现 | vector、list、deque | set、map、unordered_set、unordered_map |
std::set 是关联式容器，底层通常由红黑树实现，元素自动排序且唯一。
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;
如需优化内存使用，可自定义分配器；若 T 不支持默认比较，可通过仿函数重载比较规则。
#include<iostream>
#include<set>
// 1. 定义一个普通函数作为比较函数
bool fncomp(int lhs, int rhs) {
return lhs < rhs;
}
// 2. 定义一个函数对象（仿函数）类
struct classcomp {
bool operator()(const int& lhs, const int& rhs) const {
return lhs < rhs;
}
};
int main() {
/*------------------使用不同的构造函数创建 set 容器------------------*/
// 1. 使用'默认构造函数'创建一个空的 set，元素类型为 int
std::set<int> s1;
// 2. 使用'迭代器范围构造函数'创建包含 5 个元素的 set
int myints[] = {10, 20, 30, 40, 50};
std::set<int> s2(myints, myints + 5);
// 3. 使用'拷贝构造函数'创建 set 容器
std::set<int> s3(s2);
// 4. 使用'迭代器构造函数'创建 set
std::set<int> s4(s2.begin(), s2.end());
/*------------------使用不同的方式作为 set 容器的比较器------------------*/
// 5. 使用'自定义的函数对象'作为比较器
std::set<int, classcomp> s5;
// 6. 使用'函数指针'作为比较器
bool (*fn_pt)(int, int) = fncomp;
std::set<int, bool(*)(int, int)> s6(fn_pt);
return 0;
}
返回容器中元素的数量。
#include<iostream>
#include<set>
int main() {
std::set<int> myints;
std::cout << "初始状态下的 set 大小的 size 为：" << myints.size() << '\n';
for (int i = 0; i < 10; ++i) myints.insert(i);
std::cout << "插入 10 个元素后 set 大小的 size 为：" << myints.size() << '\n';
myints.insert(100);
std::cout << "插入元素 100 后 set 大小的 size 为：" << myints.size() << '\n';
myints.erase(5);
std::cout << "删除 5 个元素后 set 大小的 size 为：" << myints.size() << '\n';
return 0;
}
判断容器是否为空。
#include<iostream>
#include<set>
int main() {
std::set<int> myset;
myset.insert(20);
myset.insert(30);
myset.insert(10);
std::cout << "myset 容器中的内容为:";
while (!myset.empty()) {
std::cout << ' ' << *myset.begin();
myset.erase(myset.begin());
}
std::cout << '\n';
return 0;
}
清空容器内容。
交换两个 set 的内容。
插入元素，返回 pair<iterator, bool>，表示是否插入成功及迭代器位置。
#include<iostream>
#include<set>
int main() {
std::set<int> myset;
std::set<int>::iterator it;
std::pair<std::set<int>::iterator, bool> ret;
/*--------------------插入形式一：单个元素的插入--------------------*/
for (int i = 1; i <= 5; ++i) {
myset.insert(i * 10);
}
// 尝试插入已存在的元素 20
ret = myset.insert(20);
if (ret.second == false) it = ret.first;
/*--------------------插入形式二：带提示位置的插入--------------------*/
myset.insert(it, 25);
myset.insert(it, 24);
myset.insert(it, 26);
/*--------------------插入形式三：范围插入--------------------*/
int myints[] = {5, 10, 15};
myset.insert(myints, myints + 3);
return 0;
}
删除元素，支持按迭代器、按值、按范围删除。
#include<iostream>
#include<set>
int main() {
std::set<int> myset;
std::set<int>::iterator it;
// 插入元素
for (int i = 1; i < 10; i++) {
myset.insert(i * 10);
}
// 让迭代器 it 指向第二个元素 20
it = myset.begin(); ++it;
/*--------------------删除形式一：迭代器位置删除--------------------*/
myset.erase(it);
/*--------------------删除形式二：按值删除--------------------*/
myset.erase(40);
/*--------------------删除形式三：迭代器范围删除--------------------*/
it = myset.find(60);
myset.erase(it, myset.end());
return 0;
}
获取键比较函数对象。
获取值比较函数对象。
查找元素，返回迭代器，未找到返回 end()。
统计元素出现次数（set 中为 0 或 1）。
二分查找相关接口，用于定位区间。
#include<iostream>
#include<set>
int main() {
std::set<int> myset;
std::set<int>::iterator itlow, itup;
for (int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 ... 90
itlow = myset.lower_bound(30); // ^
itup = myset.upper_bound(60); // ^
myset.erase(itlow, itup); // 10 20 70 80 90
return 0;
}
代码示例 1：基础特性与遍历
#include<iostream>
#include<set>
using namespace std;
int main() {
set<int> s;
// 插入元素：重复元素会被自动过滤
s.insert(5); s.insert(2); s.insert(7); s.insert(5);
// 迭代器遍历：set 的迭代器是常量迭代器
auto it = s.begin();
while (it != s.end()) {
cout << *it << " ";
++it;
}
cout << endl;
// 批量插入
s.insert({2, 8, 3, 9});
for (auto e : s) {
cout << e << " ";
}
cout << endl;
// 字符串 set：按字典序排序
set<string> strset = {"sort", "insert", "add"};
for (auto& e : strset) {
cout << e << " ";
}
return 0;
}
代码示例 2：查找与删除
#include<iostream>
#include<set>
using namespace std;
int main() {
set<int> s = {4, 2, 7, 2, 8, 5, 9}; // 去重后升序：{2, 4, 5, 7, 8, 9}
// 迭代器位置删除
s.erase(s.begin());
// 按值删除
int x; cin >> x;
int num = s.erase(x);
if (num == 0) cout << x << " 不存在！" << endl;
else cout << x << " 存在！" << endl;
// 先查找再删除
cin >> x;
auto pos = s.find(x);
if (pos != s.end()) s.erase(pos);
// 利用 count 间接判断
cin >> x;
if (s.count(x)) cout << x << " 在！" << endl;
else cout << x << " 不存在！" << endl;
return 0;
}
std::multiset 允许元素重复，底层同样由红黑树实现，元素自动排序。
set：自动去重，元素唯一。multiset：允许元素重复，侧重按序存储重复数据。#include<iostream>
#include<set>
using namespace std;
int main() {
// 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;
// find 特性：仅返回第一个匹配的元素迭代器
int x; cin >> x;
auto pos = s.find(x);
while (pos != s.end() && *pos == x) {
cout << *pos << " ";
++pos;
}
cout << endl;
// count 特性：返回元素的实际重复次数
cout << "数量为：" << s.count(x) << endl;
// erase 特性：按值删除时，删除所有匹配的元素
cin >> x;
s.erase(x);
return 0;
}
std::pair 用于将两个不同类型的数据组合成一个逻辑单元，位于 <utility> 头文件。
语法：std::pair<Type1, Type2> pairName(value1, value2);
first 和 second 成员变量访问。在 map 中，键值对的类型是 pair<const Key, T>。
#include<utility>
// 辅助函数 make_pair
template<class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y) {
return pair<T1, T2>(x, y);
}
std::map 是关联式容器，存储键值对 (Key, Value)，按键排序，键唯一。
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;
#include<iostream>
#include<map>
int main() {
// 1. 默认构造函数
std::map<char, int> m1;
m1['a'] = 10; m1['b'] = 30;
// 2. 范围构造函数
std::map<char, int> m2(m1.begin(), m1.end());
// 3. 拷贝构造函数
std::map<char, int> m3(m2);
return 0;
}
std::map::size：返回元素数量。std::map::empty：判断是否为空。多功能接口，支持修改已存在的键值对、插入新数据或查找数据（键不存在时自动插入默认值）。
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main() {
map<string, string> dict;
// 插入功能
dict["insert"];
// 插入 + 修改
dict["left"] = "左边";
// 修改功能
dict["left"] = "左边、剩余";
// 查找功能
cout << dict["left"] << endl;
return 0;
}
std::map::clear：清空容器。std::map::swap：交换内容。std::map::insert：插入键值对。std::map::erase：删除元素。std::map::find：查找键。std::map::count：统计键出现次数（map 中为 0 或 1）。std::map::lower_bound / upper_bound / equal_range：区间查找。代码示例 1：构造与遍历
#include<iostream>
#include<map>
using namespace std;
int main() {
map<string, string> dict = {{"left", "左边"}, {"right", "右边"}};
// 迭代器遍历
auto it = dict.begin();
while (it != dict.end()) {
cout << it->first << ":" << it->second << endl;
++it;
}
// insert 插入
dict.insert(make_pair("sort", "排序"));
// find 查找
string str;
while (cin >> str) {
auto ret = dict.find(str);
if (ret != dict.end()) {
cout << "=> " << ret->second << endl;
} else {
cout << "无此单词" << endl;
}
}
return 0;
}
代码示例 2：统计频率
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main() {
string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果"};
map<string, int> countMap;
// 用 operator[] 简化统计逻辑
for (const auto& str : arr) {
countMap[str]++;
}
for (const auto& e : countMap) {
cout << e.first << ":" << e.second << endl;
}
return 0;
}
std::multimap 允许键冗余，适合存'一对多'的映射关系。
map：键唯一，每个键对应唯一的映射关系。multimap：键可重复，同一个键能记多个解释。注意：multimap 不支持 operator[]，因为键可冗余的场景下无法明确指定修改哪一个键对应的值。
思路：利用 set 去重特性，遍历对比。
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;
}
};
思路：使用 set 存储访问过的节点，若插入失败则说明有环。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
set<ListNode*> s;
ListNode* cur = head;
while (cur) {
auto ret = s.insert(cur);
if (ret.second == false)
return cur;
cur = cur->next;
}
return nullptr;
}
};
思路：使用 map 存储原节点与拷贝节点的映射关系。
class Solution {
public:
Node* copyRandomList(Node* head) {
map<Node*, Node*> m;
Node* copyHead = nullptr;
Node* copyTail = nullptr;
Node* curr = head;
// next 指针拷贝
while (curr) {
if (copyTail == nullptr) {
copyHead = copyTail = new Node(curr->val);
} else {
copyTail->next = new Node(curr->val);
copyTail = copyTail->next;
}
m[curr] = copyTail;
curr = curr->next;
}
// random 指针处理
curr = head;
Node* copy = copyHead;
while (curr) {
if (curr->random == nullptr) {
copy->random = nullptr;
} else {
copy->random = m[curr->random];
}
curr = curr->next;
copy = copy->next;
}
return copyHead;
}
};
方法一：基于 stable_sort 排序
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> m;
for (auto& e : words) {
m[e]++;
}
vector<pair<string, int>> v(m.begin(), m.end());
stable_sort(v.begin(), v.end(), Compare());
vector<string> ret;
for (int i = 0; i < k; i++) {
ret.push_back(v[i].first);
}
return ret;
}
};
方法二：基于 sort 排序
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> m;
for (auto& e : words) {
m[e]++;
}
vector<pair<string, int>> v(m.begin(), m.end());
sort(v.begin(), v.end(), Compare());
vector<string> ret;
for (int i = 0; i < k; i++) {
ret.push_back(v[i].first);
}
return ret;
}
};
方法三：基于 priority_queue 大顶堆
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> m;
for (auto& e : words) {
m[e]++;
}
priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> p(m.begin(), m.end());
vector<string> ret;
for (int i = 0; i < k; i++) {
ret.push_back(p.top().first);
p.pop();
}
return ret;
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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