概述
C++ 标准模板库（STL）提供了丰富的容器类型，主要分为序列式容器和关联式容器。
序列容器和关联容器
序列式容器
C++算法
C++ STL 容器 set 与 map 使用详解
本文介绍了 C++ STL 中 set、multiset、map、multimap 及 pair 容器的核心特性与常用操作。涵盖容器构造、元素增删改查、迭代器遍历、比较规则自定义等内容。通过代码示例演示了去重排序、键值对映射、区间查找等应用场景，并结合 LeetCode 题目展示了在实际算法问题中的使用方法。
本文介绍了 C++ STL 中 set、multiset、map、multimap 及 pair 容器的核心特性与常用操作。涵盖容器构造、元素增删改查、迭代器遍历、比较规则自定义等内容。通过代码示例演示了去重排序、键值对映射、区间查找等应用场景，并结合 LeetCode 题目展示了在实际算法问题中的使用方法。
C++ 标准模板库（STL）提供了丰富的容器类型，主要分为序列式容器和关联式容器。
序列式容器
vector、list、deque关联式容器
set、map、unordered_set、unordered_mapstd::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;
模板参数说明：
#include <iostream>
#include <set>
int main() {
// 1. 默认构造函数
std::set<int> s1;
// 2. 迭代器范围构造函数
int myints[] = {10, 20, 30, 40, 50};
std::set<int> s2(myints, myints + 5);
// 3. 拷贝构造函数
std::set<int> s3(s2);
// 4. 自定义比较器
struct classcomp {
bool operator()(const int& lhs, const int& rhs) const {
return lhs < rhs;
}
};
std::set<int, classcomp> s5;
return 0;
}
size()：返回元素个数。empty()：判断是否为空。std::set<int> myset;
myset.insert(10);
std::cout << "Size: " << myset.size() << '\n';
if (myset.empty()) {
std::cout << "Empty" << '\n';
} else {
std::cout << "Not Empty" << '\n';
}
clear()：清空容器。swap()：交换两个容器的内容。insert()：插入元素。erase()：删除元素。// 插入
myset.insert(20);
auto ret = myset.insert(30); // 返回 pair<iterator, bool>
// 删除
myset.erase(20); // 按值删除
myset.erase(it); // 按迭代器删除
myset.erase(it1, it2); // 按范围删除
find()：查找元素。count()：统计元素出现次数（set 中为 0 或 1）。lower_bound() / upper_bound()：二分查找边界。equal_range()：返回指定元素的上下界范围。auto it = myset.find(20);
if (it != myset.end()) {
std::cout << *it << '\n';
}
auto range = myset.equal_range(20);
// range.first -> lower_bound
// range.second -> upper_bound
#include <iostream>
#include <set>
using namespace std;
int main() {
// 去重 + 排序
set<int> s = {5, 2, 7, 2, 8};
// 输出：2 5 7 8
// 降序排序
set<int, greater<int>> s_desc;
s_desc.insert(10);
s_desc.insert(5);
// 输出：10 5
// 遍历
for (auto e : s) {
cout << e << " ";
}
return 0;
}
std::multiset 与 set 类似，但允许重复元素。
| 特性 | set | multiset |
|---|---|---|
| 元素唯一性 | 唯一 | 可重复 |
| count 返回值 | 0 或 1 | 实际数量 |
| erase(key) | 删除一个 | 删除所有匹配 |
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> ms = {4, 2, 4, 8, 4};
// 输出：2 4 4 4 8
cout << ms.count(4) << endl; // 输出 3
ms.erase(4); // 删除所有 4
return 0;
}
std::pair 将两个不同类型的数据组合成一个逻辑单元。
#include <utility>
std::pair<int, string> p(1, "hello");
// 访问
p.first = 2;
p.second = "world";
常用于 map 的键值对存储。
typedef pair<const Key, T> value_type;
// 辅助函数 make_pair
auto p = make_pair(1, "test");
std::map 存储键值对（Key-Value），按键排序，键唯一。
template<class Key,
class T,
class Compare = less<Key>,
class Alloc = allocator<pair<const Key, T>>
>
class map;
operator[]：访问或插入键值对。find()：查找键。insert()：插入键值对。erase()：删除元素。#include <iostream>
#include <map>
using namespace std;
int main() {
map<string, int> m;
m["apple"] = 5; // 插入/修改
m["banana"] = 3; // 插入
if (m.count("apple")) {
cout << "Found apple" << endl;
}
auto it = m.find("banana");
if (it != m.end()) {
it->second = 10; // 修改值
}
return 0;
}
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
// 统计词频
string arr[] = {"apple", "banana", "apple"};
map<string, int> countMap;
for (const auto& str : arr) {
countMap[str]++; // 自动处理存在与否
}
for (const auto& e : countMap) {
cout << e.first << ": " << e.second << endl;
}
return 0;
}
std::multimap 允许键重复，适用于一对多映射关系。
map：键唯一，不支持 operator[] 的多值场景。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*> visited;
ListNode* cur = head;
while (cur) {
if (!visited.insert(cur).second) {
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) {
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) {
copy->random = m[curr->random];
}
curr = curr->next;
copy = copy->next;
}
return copyHead;
}
};
题目描述：找出出现频率最高的前 K 个单词。
思路：利用 map 统计频率，结合 sort 或 priority_queue 排序。
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> m;
for (const auto& w : words) {
m[w]++;
}
vector<pair<string, int>> v(m.begin(), m.end());
sort(v.begin(), v.end(), [](const pair<string, int>& a, const pair<string, int>& b) {
if (a.second != b.second) return a.second > b.second;
return a.first < b.first;
});
vector<string> ret;
for (int i = 0; i < k; ++i) {
ret.push_back(v[i].first);
}
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