目录
vector
动态数组：支持随机访问，O(1)时间复杂度完成；尾部插入/删除快 O(1)，中间/头部插入/删除慢 O(n)
- 构造以及初始化：
#include <vector>
using namespace std;
// 默认构造
vector<int> v1; // 空vector
// 指定大小
vector<int> v2(5); // [0,0,0,0,0]
// 指定大小和初始值
vector<int> v3(5, 10); // [10,10,10,10,10]
// 列表初始化（C++11）
vector<int> v4 = {1, 2, 3, 4, 5}; // [1,2,3,4,5]
vector<int> v5{1, 2, 3, 4, 5}; // 同上
// 拷贝构造
vector<int> v6(v4); // 复制v4
// 迭代器范围构造
vector<int> v7(v4.begin(), v4.begin() + 3); // [1,2,3]
- 容量相关
vector<int> v = { 1, 2, 3, 4, 5 };
v.size(); // 5，元素个数
v.capacity(); // 5或更大，当前分配的内存能容纳的元素数
v.empty(); // false，是否为空
v.max_size(); // 最大元素个数
v.reserve(10); // 预分配容量为10（不改变size）
v.resize(8); // 改变size为8，新元素值初始化为0 -> [1,2,3,4,5,0,0,0]
v.resize(10, 99);// 改变size为10，新元素填充99 -> [1,2,3,4,5,0,0,0,99,99]
v.shrink_to_fit(); // 释放多余容量，让capacity == size
- 元素访问：
vector<int> v = { 10, 20, 30, 40, 50 };
v[0]; // 10，下标访问（不检查边界，快）
v.at(0); // 10，边界检查访问（越界抛异常）
v.front(); // 10，第一个元素
v.back(); // 50，最后一个元素
- 修改操作:
vector<int> v = { 1, 2, 3 };
// 尾部操作
v.push_back(4); // [1,2,3,4]
v.emplace_back(5); // [1,2,3,4,5]（C++11，原地构造，更高效）
v.pop_back(); // [1,2,3,4]
// 插入（慢 O(n)）
v.insert(v.begin(), 0); // [0,1,2,3,4]
v.insert(v.begin() + 2, 99); // [0,1,99,2,3,4]
v.insert(v.end(), { 5, 6 }); // [0,1,99,2,3,4,5,6]
// 删除
v.erase(v.begin()); // 删除第一个元素 -> [1,99,2,3,4,5,6]
v.erase(v.begin() + 1, v.begin() + 3); // 删除索引1~2 -> [1,3,4,5,6]
v.clear(); // 清空所有元素，size=0
- 遍历：
vector<int> v = { 1, 2, 3, 4, 5 };
// 正向遍历：正向迭代器
for (auto it = v.begin(); it != v.end(); ++it) {
cout << *it << " "; // 1 2 3 4 5
}
// 反向遍历：反向迭代器
for (auto it = v.rbegin(); it != v.rend(); ++it) {
cout << *it << " "; // 5 4 3 2 1
}
// 正向遍历：常量迭代器（不能修改）
for (auto it = v.cbegin(); it != v.cend(); ++it) {
// *it = 10; // 错误！不能修改
}
// 正向遍历
for (auto i : v) {
cout << i << " ";
}
- 赋值与交换
vector<int> v1 = { 1, 2, 3 };
vector<int> v2 = { 4, 5, 6 };
v1.assign(5, 100); // [100,100,100,100,100]
v1.assign({ 7, 8, 9 }); // [7,8,9]
v1.assign(v2.begin(), v2.end()); // [4,5,6]
v1.swap(v2); // 交换内容，高效（只交换指针）
swap(v1, v2); // 同上
deque
两端插入/删除O(1)，支持随机访问，O(1)完成。注意这个容器底层由多段等长连续的内存组成，使用数组存储着各个连续空间的首地址（即指针）。
- 构造与初始化
// 默认构造
deque<int> dq1;
// 指定大小
deque<int> dq2(5); // [0,0,0,0,0]
// 指定大小和初始值
deque<int> dq3(5, 10); // [10,10,10,10,10]
// 列表初始化
deque<int> dq4 = { 1, 2, 3, 4, 5 };
deque<int> dq5{ 1, 2, 3, 4, 5 };
// 拷贝构造
deque<int> dq6(dq4);
// 迭代器范围构造
vector<int> v = { 1, 2, 3, 4, 5 };
deque<int> dq7(v.begin(), v.end());
// 移动构造（C++11）
deque<int> dq8(move(dq4)); // dq4 被清空
- 赋值操作
deque<int> dq1 = { 1, 2, 3 };
deque<int> dq2;
// 赋值运算符
dq2 = dq1; // dq2 = [1,2,3]
// assign 方法
dq2.assign(5, 100); // [100,100,100,100,100]
dq2.assign({ 10, 20, 30 }); // [10,20,30]
dq2.assign(dq1.begin(), dq1.end()); // [1,2,3]
// 交换
dq1.swap(dq2); // 交换内容
swap(dq1, dq2); // 同上
- 元素访问
deque<int> dq = { 10, 20, 30, 40, 50 };
// 下标访问（不检查边界）
int x = dq[0]; // 10
int y = dq[4]; // 50
// at 方法（检查边界）
x = dq.at(0); // 10
// dq.at(5) 抛出 out_of_range 异常
// 首尾元素
int front = dq.front(); // 10
int back = dq.back(); // 50
- 大小与容量
deque<int> dq = { 1, 2, 3, 4, 5 };
dq.size(); // 5，元素个数
dq.empty(); // false，是否为空
dq.max_size(); // 最大可能元素个数
// 注意：deque 没有 capacity() 和 reserve()
// 因为内存不连续，不需要预留空间
dq.shrink_to_fit(); // C++11，释放多余内存
- 修改操作
deque<int> dq = { 10, 20, 30 };
// ========== 头部操作 ==========
dq.push_front(5); // [5,10,20,30]
dq.emplace_front(1); // [1,5,10,20,30]（原地构造）
dq.pop_front(); // [5,10,20,30]
// ========== 尾部操作 ==========
dq.push_back(40); // [5,10,20,30,40]
dq.emplace_back(50); // [5,10,20,30,40,50]
dq.pop_back(); // [5,10,20,30,40]
// ========== 中间操作（慢 O(n)）==========
// 插入
dq.insert(dq.begin() + 2, 99); // [5,10,99,20,30,40]
dq.insert(dq.begin(), 3, 88); // 插入3个88 [88,88,88,5,10,99,20,30,40]
dq.insert(dq.end(), { 100, 101 }); // 尾部插入100,101
// 删除
dq.erase(dq.begin() + 2); // 删除索引2
dq.erase(dq.begin(), dq.begin() + 3); // 删除前3个
// 清空
dq.clear(); // 清空所有元素
- 容器遍历：
deque<int> dq = { 1, 2, 3, 4, 5 };
// 正向遍历：正向迭代器
for (auto it = dq.begin(); it != dq.end(); ++it) {
cout << *it << " ";
}
// 正向遍历：常量迭代器
for (auto it = dq.cbegin(); it != dq.cend(); ++it) {
// *it = 10; // 错误！不能修改
}
// 反向遍历：反向迭代器
for (auto it = dq.rbegin(); it != dq.rend(); ++it) {
cout << *it << " "; // 5 4 3 2 1
}
// 随机访问迭代器特性
auto it = dq.begin();
it += 2; // 可以
it -= 1; // 可以
cout << it[2]; // 可以
// 正向遍历
for (auto i : dq) {
cout << i << " ";
}
list
双链表：插入删除操作O(1)，访问O(n)
- 构造与初始化：
// 默认构造
list<int> lst1;
// 指定大小
list<int> lst2(5); // [0,0,0,0,0]
// 指定大小和初始值
list<int> lst3(5, 10); // [10,10,10,10,10]
// 列表初始化
list<int> lst4 = { 1, 2, 3, 4, 5 };
list<int> lst5{ 1, 2, 3, 4, 5 };
// 拷贝构造
list<int> lst6(lst4);
// 迭代器范围构造
vector<int> v = { 1, 2, 3 };
list<int> lst7(v.begin(), v.end());
// 移动构造（C++11）
list<int> lst8(move(lst4)); // lst4 被清空
- 赋值操作
list<int> lst1 = { 1, 2, 3 };
list<int> lst2;
// 赋值运算符
lst2 = lst1; // lst2 = [1,2,3]
// assign 方法
lst2.assign(5, 100); // [100,100,100,100,100]
lst2.assign({ 10, 20, 30 }); // [10,20,30]
lst2.assign(lst1.begin(), lst1.end()); // [1,2,3]
// 交换
lst1.swap(lst2); // 交换内容（只交换头指针，O(1)）
swap(lst1, lst2); // 同上
- 元素访问:
list<int> lst = { 10, 20, 30, 40, 50 };
// 只能访问首尾元素
int front = lst.front(); // 10
int back = lst.back(); // 50
// ❌ 不支持随机访问
// lst[0]; // 编译错误
// 要访问中间元素必须遍历
auto it = lst.begin();
advance(it, 2); // 移动到第2个位置（0-indexed）
cout << *it; // 30
- 大小操作
list<int> lst = { 1, 2, 3, 4, 5 };
lst.size(); // 5
lst.empty(); // false
lst.max_size(); // 最大可能元素个数
lst.resize(8); // [1,2,3,4,5,0,0,0]
lst.resize(10, 99); // [1,2,3,4,5,0,0,0,99,99]
lst.resize(3); // [1,2,3]
// list 没有 capacity() 和 reserve()
- 修改操作
list<int> lst = { 10, 20, 30 };
// ========== 头部操作 ==========
lst.push_front(5); // [5,10,20,30]
lst.emplace_front(1); // [1,5,10,20,30]
lst.pop_front(); // [5,10,20,30]
// ========== 尾部操作 ==========
lst.push_back(40); // [5,10,20,30,40]
lst.emplace_back(50); // [5,10,20,30,40,50]
lst.pop_back(); // [5,10,20,30,40]
// ========== 插入（任意位置，O(1)）==========
auto it = lst.begin();
advance(it, 2); // 指向第2个元素（20）
lst.insert(it, 99); // 在 it 之前插入 99 -> [5,10,99,20,30,40]
lst.insert(it, 3, 88); // 插入3个88 -> [5,10,99,88,88,88,20,30,40]
lst.insert(it, { 77, 78 }); // 插入77, 78
// emplace（原地构造）
lst.emplace(it, 66); // 在 it 之前构造
// ========== 删除 ==========
it = lst.begin();
advance(it, 2);
lst.erase(it); // 删除迭代器指向的元素
// 删除范围
auto first = lst.begin();
auto last = lst.begin();
advance(first, 1);
advance(last, 4);
lst.erase(first, last); // 删除 [first, last)
// 清空
lst.clear();
- 特殊操作：
list<int> lst1 = { 1, 2, 3, 4, 5 };
list<int> lst2 = { 6, 7, 8, 9, 10 };
// splice：转移元素（O(1)！）
auto it = lst1.begin();
advance(it, 2);
lst1.splice(it, lst2); // 将 lst2 所有元素移到 lst1 的 it 位置
// lst1: [1,2,6,7,8,9,10,3,4,5]
// lst2: []（空）
// splice 单个元素
list<int> lst3 = { 100, 200 };
auto it3 = lst3.begin();
lst1.splice(lst1.end(), lst3, it3); // 移动单个元素
// lst1: [...,200] lst3: [100]
// remove：删除所有等于某值的元素
list<int> lst = { 1, 2, 3, 2, 4, 2, 5 };
lst.remove(2); // [1,3,4,5]（所有2被删除）
// remove_if：按条件删除
lst.remove_if([](int x) { return x % 2 == 0; }); // 删除偶数
// unique：删除连续重复元素（只保留一个）
list<int> lst4 = { 1, 1, 2, 2, 2, 3, 1, 1 };
lst4.unique(); // [1,2,3,1]（注意最后的1保留了）
// merge：合并两个有序链表
list<int> a = { 1, 3, 5 };
list<int> b = { 2, 4, 6 };
a.merge(b); // a: [1,2,3,4,5,6], b: []（清空）
// sort：排序（list 有自己的 sort）
list<int> lst5 = { 5, 2, 8, 1, 9 };
lst5.sort(); // [1,2,5,8,9]
lst5.sort(greater<int>()); // [9,8,5,2,1]
// reverse：反转
lst5.reverse(); // [1,2,5,8,9] 反转
// 注意：不能用全局的 std::sort
//sort(lst5.begin(), lst5.end()); // ❌ 编译错误！要求随机访问迭代器
- 容器的遍历：
list<int> lst = { 1, 2, 3, 4, 5 };
// 正向迭代器（双向，不是随机访问）
for (auto it = lst.begin(); it != lst.end(); ++it) {
cout << *it << " ";
}
// 常量迭代器
for (auto it = lst.cbegin(); it != lst.cend(); ++it) {
// *it = 10; // 错误！不能修改
}
// 反向迭代器
for (auto it = lst.rbegin(); it != lst.rend(); ++it) {
cout << *it << " "; // 5 4 3 2 1
}
// 迭代器限制
auto it = lst.begin();
it++; // ✓ 可以
it--; // ✓ 可以
// it += 2; // ✗ 错误！不支持随机访问
// it - 1; // ✗ 错误！
// it[2]; // ✗ 错误！
for (auto i : lst) {
cout << i << " ";
}
forward_list
单链表。注意这个容器和list的区别是没有提供push_back，back，pop_back方法，因为这些方法的实现需要O(n)时间复杂度完成，也没有提供size方法
array
静态数组。
unordered_set
底层哈希表实现，元素唯一且无序。平均 O(1) 完成插入、删除、查找，最差O(n)
- 构造与初始化:
// 默认构造
unordered_set<int> s1;
// 列表初始化
unordered_set<int> s2 = { 1, 2, 3, 4, 5 };
unordered_set<int> s3{ 1, 2, 3, 4, 5 };
// 迭代器范围构造
vector<int> v = { 1, 2, 3, 4, 5 };
unordered_set<int> s4(v.begin(), v.end());
// 拷贝构造
unordered_set<int> s5(s2);
// 移动构造
unordered_set<int> s6(move(s2));
// 自定义哈希和相等函数（高级）
auto hash = [](const int& x) { return x % 10; };
auto equal = [](const int& a, const int& b) { return a == b; };
// 10为初始桶数
unordered_set<int, decltype(hash), decltype(equal)> s7(10, hash, equal);
- 插入操作
unordered_set<int> s = { 1, 2, 3 };
// 插入单个元素
auto result = s.insert(4); // 返回 pair<iterator, bool>
// result.first: 指向插入元素（或已存在元素）的迭代器
// result.second: true=插入成功, false=已存在
if (result.second) {
cout << "插入成功，值: " << *result.first << endl;
}
else {
cout << "元素已存在" << endl;
}
// emplace（原地构造，避免拷贝）
s.emplace(5); // 更高效
// 插入多个
s.insert({ 6, 7, 8 });
// 插入范围
vector<int> v = { 9, 10, 11 };
s.insert(v.begin(), v.end());
// 插入迭代器指向的位置（提示位置，不保证精确，这个容器不保证有序）
auto it = s.begin();
s.insert(it, 99); // 提示在 it 前插入
- 删除操作
unordered_set<int> s = { 1, 2, 3, 4, 5 };
// 删除指定值
size_t n = s.erase(3); // 返回删除的元素个数（0或1）
cout << "删除了 " << n << " 个元素" << endl;
// 删除迭代器位置
auto it = s.find(2);
if (it != s.end()) {
it = s.erase(it); // 返回下一个元素的迭代器
}
// 删除范围
auto first = s.find(1);
auto last = s.find(4);
if (first != s.end() && last != s.end()) {
s.erase(first, last); // 删除 [first, last)
}
// 清空
s.clear();
- 查找操作：
unordered_set<int> s = { 1, 2, 3, 4, 5 };
// find（最常用）
auto it = s.find(3);
if (it != s.end()) {
cout << "找到: " << *it << endl;
}
else {
cout << "未找到" << endl;
}
// count（计数，返回0或1）
if (s.count(3)) {
cout << "存在" << endl;
}
// contains（C++20）
if (s.contains(3)) { // 更直观
cout << "存在" << endl;
}
// equal_range（返回一对迭代器，表示等于该值的范围）
auto range = s.equal_range(3);
// range.first 指向 3，range.second 指向下一个元素
- 容量操作：
unordered_set<int> s = { 1, 2, 3, 4, 5 };
// 基本容量
s.size(); // 5
s.empty(); // false
s.max_size(); // 最大可能元素数（很大）
// 预留空间（避免多次 rehash）
s.reserve(100); // 预留至少100个位置
s.rehash(200); // 设置桶数为200
// 桶接口（高级）
s.bucket_count(); // 桶的数量
s.bucket_size(0); // 第0个桶的元素数
s.bucket(3); // 元素3所在的桶索引
s.load_factor(); // 负载因子 = size / bucket_count
s.max_load_factor(); // 最大负载因子（默认1.0）
s.rehash(100); // 重新哈希，设置桶数
s.reserve(100); // 预留空间（等同于 rehash(ceil(100/max_load_factor))）
- 容器的遍历：
unordered_set<int> s = { 1, 2, 3, 4, 5 };
// 正向迭代器（注意：顺序不确定！）
for (auto it = s.begin(); it != s.end(); ++it) {
cout << *it << " ";
}
// 可能输出: 3 1 4 2 5（任意顺序）
// 常量迭代器
for (auto it = s.cbegin(); it != s.cend(); ++it) {
// *it = 10; // 错误！不能修改
}
// 范围 for 循环
for (int x : s) {
cout << x << " ";
}
unordered_multiset
底层哈希表实现，元素唯一且无序。平均O(1)完成插入、删除、查找，最差O(n)。与unordered_set的区别是这个容器允许元素重复
unordered_map
底层哈希表实现，存储唯一的键到值的映射，无序。平均O(1)完成插入、删除、查找，最差O(n)。
- 构造与初始化：
// 默认构造
unordered_map<string, int> m1;
// 列表初始化
unordered_map<string, int> m2 = {
{"apple", 5},
{"banana", 3},
{"orange", 8}
};
// 迭代器范围构造
vector<pair<string, int>> v = { {"a",1}, {"b",2} };
unordered_map<string, int> m3(v.begin(), v.end());
// 拷贝构造
unordered_map<string, int> m4(m2);
// 移动构造
unordered_map<string, int> m5(move(m2));
// 指定初始桶数
unordered_map<string, int> m6(100); // 100个桶
// 自定义哈希和相等函数
auto hash = [](const string& s) {
return s.length();
};
auto equal = [](const string& a, const string& b) {
return a == b;
};
unordered_map<string, int, decltype(hash), decltype(equal)>
m7(10, hash, equal);
- 插入操作
unordered_map<string, int> m;
// 方式1：使用 [] 操作符（最常用）
m["apple"] = 5; // 插入或修改
m["banana"] = 3;
m["apple"] = 10; // 修改已存在的键
// 方式2：insert 方法
auto result = m.insert({ "orange", 8 });
// result.first: 指向插入元素（或已存在元素）的迭代器
// result.second: true=插入成功, false=键已存在
// 方式3：insert 带提示
auto it = m.begin();
m.insert(it, { "pear", 4 }); // 提示位置（通常被忽略）
// 方式4：emplace（原地构造，避免拷贝）
m.emplace("grape", 6);
// 方式5：尝试插入，不覆盖
m.try_emplace("kiwi", 7); // C++17，键不存在才插入
// 方式6：插入或赋值
m.insert_or_assign("apple", 15); // C++17，总是成功
// 批量插入
m.insert({ {"mango", 9}, {"peach", 2} });
- 访问元素
unordered_map<string, int> m = {
{"apple", 5},
{"banana", 3},
{"orange", 8}
};
// 方式1：[] 操作符（不安全！键不存在会创建）
int val1 = m["apple"]; // 5
int val2 = m["grape"]; // 0！键不存在，创建并返回0
// 方式2：at() 方法（安全，键不存在抛异常）
int val3 = m.at("apple"); // 5
// int val4 = m.at("test"); // 抛出 out_of_range 异常
// 方式3：find + 解引用（最安全）
auto it = m.find("banana");
if (it != m.end()) {
cout << it->first << ": " << it->second << endl;
}
- 删除操作
unordered_map<string, int> m = {
{"apple", 5},
{"banana", 3},
{"orange", 8},
{"grape", 6}
};
// 删除指定键
size_t n = m.erase("banana"); // 返回删除个数（0或1）
cout << "删除了 " << n << " 个元素" << endl;
// 删除迭代器位置
auto it = m.find("orange");
if (it != m.end()) {
it = m.erase(it); // 返回下一个元素的迭代器
}
// 删除范围
auto first = m.begin();
auto last = m.begin();
advance(last, 2);
m.erase(first, last); // 删除前2个
// 清空
m.clear();
- 查找操作
unordered_map<string, int> m = {
{"apple", 5},
{"banana", 3},
{"orange", 8}
};
// find（最常用）
auto it = m.find("banana");
if (it != m.end()) {
cout << "找到: " << it->first << " -> " << it->second << endl;
}
else {
cout << "未找到" << endl;
}
// count（计数，返回0或1）
if (m.count("apple")) {
cout << "存在" << endl;
}
// contains（C++20）
if (m.contains("orange")) {
cout << "存在" << endl;
}
// equal_range（返回一对迭代器）
auto range = m.equal_range("apple");
// range.first 指向 apple，range.second 指向下一个元素
- 容器遍历
unordered_map<string, int> m = {
{"apple", 5},
{"banana", 3},
{"orange", 8}
};
// 正向迭代器（顺序不确定！）
for (auto it = m.begin(); it != m.end(); ++it) {
cout << it->first << ": " << it->second << endl;
}
// 常量迭代器
for (auto it = m.cbegin(); it != m.cend(); ++it) {
// it->second = 10; // 错误！不能修改
}
// 范围 for 循环（C++11）
for (const auto& p : m) {
cout << p.first << ": " << p.second << endl;
}
// 结构化绑定（C++17）
for (const auto& [key, value] : m) {
cout << key << ": " << value << endl;
}
- 修改操作
unordered_map<string, int> m = {
{"apple", 5},
{"banana", 3}
};
// 修改值（通过 [] 或迭代器）
m["apple"] = 10; // 修改
auto it = m.find("banana");
if (it != m.end()) {
it->second = 20; // 修改
}
// 交换
unordered_map<string, int> m2 = { {"pear", 4} };
m.swap(m2);
swap(m, m2);
// 提取节点（C++17）
auto node = m.extract("apple"); // 提取节点，不复制
node.key() = "apple2"; // 修改键
m.insert(move(node)); // 插入
// 合并（C++17）
m.merge(m2); // 将 m2 的元素移动到 m
unordered_multimap
底层哈希表实现，允许存储重复的键到值的映射，无序。平均O(1)完成插入、删除、查找，最差O(n)。与unordered_map的区别是：
- 允许键重复
- 没有[]操作符，at方法等
set
底层红黑树实现，存储唯一且有序的元素，默认升序。对于增删改查，时间复杂度O(logn)
- 构造与初始化
// 默认构造（升序）
set<int> s1;
// 指定比较器（降序）
set<int, greater<int>> s2;
// 列表初始化
set<int> s3 = { 5, 2, 8, 1, 9, 2, 5 }; // {1, 2, 5, 8, 9}（自动去重排序）
// 迭代器范围构造
vector<int> v = { 3, 1, 4, 1, 5 };
set<int> s4(v.begin(), v.end()); // {1, 3, 4, 5}
// 拷贝构造
set<int> s5(s3);
// 移动构造
set<int> s6(move(s3));
// 自定义比较器
auto cmp = [](int a, int b) { return a > b; };
set<int, decltype(cmp)> s7(cmp); // 降序
- 插入操作
set<int> s = { 1, 2, 3 };
// 插入单个元素
auto result = s.insert(4);
// result.first: 指向插入元素（或已存在元素）的迭代器
// result.second: true=插入成功, false=已存在
if (result.second) {
cout << "插入成功: " << *result.first << endl;
}
else {
cout << "元素已存在" << endl;
}
// 插入带提示（如果提示正确，插入更快）
auto it = s.find(2);
s.insert(it, 5); // 提示在2附近
// emplace（原地构造）
s.emplace(6);
// 插入多个
s.insert({ 7, 8, 9 });
// 插入范围
vector<int> v = { 10, 11, 12 };
s.insert(v.begin(), v.end());
- 删除操作
set<int> s = { 1, 2, 3, 4, 5 };
// 删除指定值
size_t n = s.erase(3); // 返回删除个数（0或1）
cout << "删除了 " << n << " 个元素" << endl;
// 删除迭代器位置
auto it = s.find(2);
if (it != s.end()) {
it = s.erase(it); // 返回下一个元素的迭代器
}
// 删除范围
auto first = s.find(1);
auto last = s.find(4);
if (first != s.end() && last != s.end()) {
s.erase(first, last); // 删除 [first, last)
}
// 清空
s.clear();
- 查找操作
set<int> s = { 10, 20, 30, 40, 50 };
// find（最常用）
auto it = s.find(30);
if (it != s.end()) {
cout << "找到: " << *it << endl;
}
else {
cout << "未找到" << endl;
}
// count（计数，返回0或1）
if (s.count(30)) {
cout << "存在" << endl;
}
// contains（C++20）
if (s.contains(30)) {
cout << "存在" << endl;
}
// lower_bound：第一个 >= 给定值的元素
auto it_low = s.lower_bound(25);
cout << "第一个 >= 25: " << *it_low << endl; // 30
// upper_bound：第一个 > 给定值的元素
auto it_up = s.upper_bound(30);
cout << "第一个 > 30: " << *it_up << endl; // 40
// equal_range：返回 [lower_bound, upper_bound)
auto range = s.equal_range(30);
// range.first 指向 30
// range.second 指向 40
- 容器的遍历：
set<int> s = { 1, 2, 3, 4, 5 };
// 正向迭代器（升序遍历）
for (auto it = s.begin(); it != s.end(); ++it) {
cout << *it << " "; // 1 2 3 4 5
}
// 常量迭代器
for (auto it = s.cbegin(); it != s.cend(); ++it) {
// *it = 10; // 错误！不能修改
}
// 反向迭代器（降序遍历）
for (auto it = s.rbegin(); it != s.rend(); ++it) {
cout << *it << " "; // 5 4 3 2 1
}
// 范围 for 循环
for (int x : s) {
cout << x << " ";
}
multiset
底层红黑树实现，允许存储重复且有序的元素，默认升序。对于增删改查，时间复杂度O(logn)
map
基于红黑树的键值对容器，存储唯一且有序的键到值的映射。默认按照键升序。对于增删查改 O(log n)
- 构造与初始化：
// 默认构造（升序）
map<string, int> m1;
// 指定比较器（降序）
map<string, int, greater<string>> m2;
// 列表初始化
map<string, int> m3 = {
{"banana", 3},
{"apple", 5},
{"orange", 8}
};
// 迭代器范围构造
vector<pair<string, int>> v = { {"a",1}, {"b",2} };
map<string, int> m4(v.begin(), v.end());
// 拷贝构造
map<string, int> m5(m3);
// 移动构造
map<string, int> m6(move(m3));
// 自定义比较器
auto cmp = [](const string& a, const string& b) {
return a.length() < b.length(); // 按长度排序，升序
};
map<string, int, decltype(cmp)> m7(cmp);
- 插入操作
map<string, int> m;
// 方式1：使用 [] 操作符（最常用）
m["apple"] = 5; // 插入或修改
m["banana"] = 3;
m["apple"] = 10; // 修改已存在的键
// 方式2：insert 方法
auto result = m.insert({ "orange", 8 });
// result.first: 指向插入元素（或已存在元素）的迭代器
// result.second: true=插入成功, false=键已存在
if (result.second) {
cout << "插入成功: " << result.first->first << endl;
}
else {
cout << "键已存在: " << result.first->second << endl;
}
// 方式3：insert 带提示（如果提示正确，插入更快）
auto it = m.find("apple");
m.insert(it, { "grape", 6 });
// 方式4：emplace（原地构造）
m.emplace("pear", 4);
// 方式5：try_emplace（C++17，键不存在才插入）
m.try_emplace("kiwi", 7);
// 方式6：insert_or_assign（C++17，插入或赋值）
m.insert_or_assign("apple", 15); // 总是成功
// 批量插入
m.insert({ {"mango", 9}, {"peach", 2} });
- 访问元素
map<string, int> m = {
{"apple", 5},
{"banana", 3},
{"orange", 8}
};
// 方式1：[] 操作符（不安全！键不存在会创建）
int val1 = m["apple"]; // 5
int val2 = m["grape"]; // 0！键不存在，创建并返回0
// 方式2：at() 方法（安全，键不存在抛异常）
int val3 = m.at("apple"); // 5
// int val4 = m.at("grape"); // 抛出 out_of_range 异常
// 方式3：find + 解引用（最安全）
auto it = m.find("banana");
if (it != m.end()) {
cout << it->first << ": " << it->second << endl;
}
- 删除操作
map<string, int> m = {
{"apple", 5},
{"banana", 3},
{"orange", 8},
{"grape", 6}
};
// 删除指定键
size_t n = m.erase("banana"); // 返回删除个数（0或1）
cout << "删除了 " << n << " 个元素" << endl;
// 删除迭代器位置
auto it = m.find("orange");
if (it != m.end()) {
it = m.erase(it); // 返回下一个元素的迭代器
}
// 删除范围
auto first = m.find("apple");
auto last = m.find("grape");
if (first != m.end() && last != m.end()) {
m.erase(first, last); // 删除 [first, last)
}
// 清空
m.clear();
- 查找操作
map<string, int> m = {
{"apple", 5},
{"banana", 3},
{"orange", 8},
{"pear", 4}
};
// find（最常用）
auto it = m.find("banana");
if (it != m.end()) {
cout << "找到: " << it->first << " -> " << it->second << endl;
}
else {
cout << "未找到" << endl;
}
// count（计数，返回0或1）
if (m.count("apple")) {
cout << "存在" << endl;
}
// contains（C++20）
if (m.contains("orange")) {
cout << "存在" << endl;
}
// lower_bound：第一个键 >= 给定值的元素
auto it_low = m.lower_bound("c");
cout << "第一个 >= c: " << it_low->first << endl; // "orange"（假设）
// upper_bound：第一个键 > 给定值的元素
auto it_up = m.upper_bound("banana");
cout << "第一个 > banana: " << it_up->first << endl;
// equal_range：返回 [lower_bound, upper_bound)
auto range = m.equal_range("banana");
// range.first 指向 banana
// range.second 指向下一个元素
- 容器遍历
map<string, int> m = {
{"apple", 5},
{"banana", 3},
{"orange", 8}
};
// 正向迭代器（按 key 升序遍历）
for (auto it = m.begin(); it != m.end(); ++it) {
cout << it->first << ": " << it->second << endl;
}
// 常量迭代器
for (auto it = m.cbegin(); it != m.cend(); ++it) {
// it->second = 10; // 错误！不能修改
}
// 反向迭代器（按 key 降序遍历）
for (auto it = m.rbegin(); it != m.rend(); ++it) {
cout << it->first << ": " << it->second << endl;
}
// 范围 for 循环
for (const auto& p : m) {
cout << p.first << ": " << p.second << endl;
}
// 结构化绑定（C++17）
for (const auto& [key, value] : m) {
cout << key << ": " << value << endl;
}
multimap
基于红黑树的键值对容器，允许存储重复且有序的键到值的映射。默认按照键升序。对于增删查改 O(log n)。与map的区别：
- multimap允许键值对重复
- 另外这个容器没有[]操作符以及at方法
stack
容器适配器： 这个不是独立的容器，而是对其他容器的封装，只提供栈特有的接口。底层容器默认选择dequeue，当然也可以选择list，vector
- 构造与初始化：
// 默认构造（底层用 deque）
stack<int> s1;
// 指定底层容器为 vector
stack<int, vector<int>> s2;
// 指定底层容器为 list
stack<int, list<int>> s3;
// 从已有容器构造
vector<int> v = { 1, 2, 3, 4, 5 };
stack<int, vector<int>> s4(v); // 用 vector 的内容初始化
// 拷贝构造
stack<int> s5(s1);
// 移动构造（C++11）
stack<int> s6(move(s1));
- 核心操作：
stack<int> s;
// 1. push：压栈
s.push(1); // 栈: [1]
s.push(2); // 栈: [1, 2]
s.push(3); // 栈: [1, 2, 3]
// 2. emplace：原地构造压栈（C++11）
s.emplace(4); // 栈: [1, 2, 3, 4]
// 3. top：访问栈顶元素（不弹出）
cout << "栈顶: " << s.top() << endl; // 4
// 4. pop：弹出栈顶元素（无返回值）
s.pop(); // 栈: [1, 2, 3]
// 5. 辅助操作
s.size(); // 3
s.empty(); // false
// 注意：没有 clear() 方法！
// 清空栈的方法：
while (!s.empty()) {
s.pop();
}
queue
queue 不是独立的容器，而是对其他容器的封装，只提供队列特有的接口。底层容器默认选择dequeue，当然也可以选择list。由于vector支持push_back和pop_back，但不支持pop_front，因此底层容器不能使用vector。
- 构造与初始化：
// 默认构造（底层用 deque）
queue<int> q1;
// 指定底层容器为 list
queue<int, list<int>> q2;
// 从已有容器构造
deque<int> d = { 1, 2, 3, 4, 5 };
queue<int> q3(d); // 用 deque 的内容初始化
list<int> l = { 1, 2, 3, 4, 5 };
queue<int, list<int>> q4(l); // 用 list 的内容初始化
// 拷贝构造
queue<int> q5(q1);
// 移动构造（C++11）
queue<int> q6(move(q1));
- 核心操作：
queue<int> q;
// 1. push：入队（尾部添加）
q.push(1); // 队列: [1]
q.push(2); // 队列: [1, 2]
q.push(3); // 队列: [1, 2, 3]
// 2. emplace：原地构造入队（C++11）
q.emplace(4); // 队列: [1, 2, 3, 4]
// 3. front：访问队首元素（不弹出）
cout << "队首: " << q.front() << endl; // 1
// 4. back：访问队尾元素（不弹出）
cout << "队尾: " << q.back() << endl; // 4
// 5. pop：弹出队首元素（无返回值）
q.pop(); // 队列: [2, 3, 4]
// 6. 辅助操作
q.size(); // 3
q.empty(); // false
// 注意：没有 clear() 方法！
// 清空队列的方法：
while (!q.empty()) {
q.pop();
}
priority_queue
C++ STL中的容器适配器，提供优先级队列的数据结构，最大元素始终在队首。底层容器默认是vector，也可以是deque。对于插入删除操作，使用底层容器的方法来完成，时间复杂度为O(logn)，因为涉及堆（堆是一个完全二叉树）算法重新调整元素。内部比较器默认使用less，因此默认是大顶堆（最大值在堆顶）。
- 构造与初始化：
// 默认构造（大顶堆）
priority_queue<int> pq1;
// 指定底层容器
priority_queue<int, vector<int>> pq2;
// 小顶堆
priority_queue<int, vector<int>, greater<int>> pq3;
// 从已有容器构造
vector<int> v = { 3, 1, 4, 1, 5 };
priority_queue<int> pq4(v.begin(), v.end()); // 用 v 的内容构建堆
// 自定义比较器
auto cmp = [](int a, int b) { return a > b; };
priority_queue<int, vector<int>, decltype(cmp)> pq5(cmp);
// 拷贝构造
priority_queue<int> pq6(pq1);
// 移动构造（C++11）
priority_queue<int> pq7(move(pq1));
- 核心操作：
priority_queue<int> pq;
// 1. push：插入元素 O(log n)
pq.push(5); // 堆: [5]
pq.push(2); // 堆: [5, 2]
pq.push(8); // 堆: [8, 2, 5]
pq.push(1); // 堆: [8, 2, 5, 1] （涉及堆的调整）
// 2. emplace：原地构造插入（C++11）
pq.emplace(3); // 堆: [8, 3, 5, 1, 2]
// 3. top：访问堆顶元素（不弹出）
cout << "堆顶: " << pq.top() << endl; // 8
// 4. pop：弹出堆顶元素 O(log n)
pq.pop(); // 堆: [5, 3, 2, 1]
// 5. 辅助操作
pq.size(); // 4
pq.empty(); // false
// 注意：没有 clear() 方法
// 清空优先队列的方法：
while (!pq.empty()) {
pq.pop();
}
string
string 是 C++ 标准库中的字符串类，是 basic_string
- 构造与初始化：
// 默认构造
string s1; // ""
// 从 C 风格字符串构造
string s2 = "hello"; // "hello"
string s3("world"); // "world"
// 拷贝构造
string s4(s2); // "hello"
// 移动构造（C++11）
string s5(move(s2)); // s5 = "hello", s2 为空
// 重复字符
string s6(5, 'a'); // "aaaaa"
// 从子串构造
string s7("hello world", 6, 5); // "world"（从索引6开始取5个）
// 从迭代器范围构造
string s8(s4.begin(), s4.end()); // "hello"
// 初始化列表（C++11）
string s9 = { 'a', 'b', 'c' }; // "abc"
// 原始字符串字面量（C++11）
string s10 = R"(raw\string\n)"; // "raw\\string\\n"（不转义）
函数对象（仿函数）
STL中预定义了一些函数对象（仿函数即为重载了函数调用运算符的类，这样的类定义的对象就是仿函数对象），如less，greater。当然也可以自定义仿函数。
1.less
- 其源码如下：
template<typename _Arg1, typename _Arg2, typename _Result>
struct binary_function
{
typedef _Arg1 first_argument_type;
typedef _Arg2 second_argument_type;
typedef _Result result_type;
};
template<typename _Tp>
struct less : public binary_function<_Tp, _Tp, bool>
{
// 升序
bool
operator()(const _Tp& __x, const _Tp& __y) const
{ return __x < __y; }
};
- 仿函数通常和STL实现的算法结合使用。例如：
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
class Student {
public:
Student() {}
Student(const std::string& name, double grade) : _name(name), _grade(grade) {
}
/**
* 按照姓名从小到大排序，姓名相同则按照分数从小到大排序
* 由于使用的less，因此需要重载比较运算符<以支持其内部的比较操作
*/
friend bool operator< (const Student& left, const Student& right) {
return left._name != right._name ? left._name < right._name : left._grade < right._grade;
}
void show()const {
cout << this->_name << ":" << this->_grade << endl;
}
private:
std::string _name;
double _grade = 0.0f;
};
int main() {
Student stus[] = { {"nrv", 24}, {"nrv", 31}, {"nrv", 26},{"xcer", 24} };
sort(stus, stus + 4, std::less<Student>());
for (int i = 0; i < 4; ++i) {
stus[i].show();
}
return 0;
}
2.greater
- 其源码如下所示：
template<typename _Arg1, typename _Arg2, typename _Result>
struct binary_function
{
typedef _Arg1 first_argument_type;
typedef _Arg2 second_argument_type;
typedef _Result result_type;
};
template<typename _Tp>
struct greater : public binary_function<_Tp, _Tp, bool>
{
// 降序
bool
operator()(const _Tp& __x, const _Tp& __y) const
{ return __x > __y; }
};
3.自定义仿函数
- 在自定义类中重载
()这个函数调用运算符， - 示例如下：
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
class Student {
public:
Student() {}
Student(const std::string& name, double grade) : _name(name), _grade(grade) {
}
void show()const {
cout << this->_name << ":" << this->_grade << endl;
}
const string& getName()const { return _name; }
double getGrade()const { return _grade; }
private:
std::string _name;
double _grade = 0.0;
};
struct cmp {
/**
* 按照姓名从小到大排序，姓名相同则按照分数从小到大排序
*/
bool operator()(const Student& left, const Student& right) {
return left.getName() == right.getName() ?
left.getGrade() < right.getGrade() : left.getName() < right.getName();
}
};
int main() {
Student stus[] = { {"nrv", 24}, {"zrv", 31}, {"nrv", 26},{"xcer", 24} };
sort(stus, stus + 4, cmp());
for (int i = 0; i < 4; ++i) {
stus[i].show();
}
return 0;
}
泛型算法
泛型算法是一种函数模板。
1.initializer_list
- initializer_list内部通过数组来维护。其实现如下所示：
namespace std
{
/// initializer_list
template<class _E>
class initializer_list
{
public:
typedef _E value_type;
typedef const _E& reference;
typedef const _E& const_reference;
typedef size_t size_type;
typedef const _E* iterator;
typedef const _E* const_iterator;
private:
iterator _M_array; // 底层实现是数组
size_type _M_len; // 数组长度
// The compiler can call a private constructor.
constexpr initializer_list(const_iterator __a, size_type __l)
: _M_array(__a), _M_len(__l) { }
public:
constexpr initializer_list() noexcept
: _M_array(0), _M_len(0) { }
// Number of elements.
constexpr size_type
size() const noexcept { return _M_len; }
// First element.
constexpr const_iterator
begin() const noexcept { return _M_array; }
// One past the last element.
constexpr const_iterator
end() const noexcept { return begin() + size(); }
};
/**
* @brief Return an iterator pointing to the first element of
* the initializer_list.
* @param __ils Initializer list.
* @relates initializer_list
*/
template<class _Tp>
constexpr const _Tp*
begin(initializer_list<_Tp> __ils) noexcept
{ return __ils.begin(); }
/**
* @brief Return an iterator pointing to one past the last element
* of the initializer_list.
* @param __ils Initializer list.
* @relates initializer_list
*/
template<class _Tp>
constexpr const _Tp*
end(initializer_list<_Tp> __ils) noexcept
{ return __ils.end(); }
}
2.max_element和max
- 这两个泛型函数可以用于获取顺序序列中的最大值
- 示例如下：
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
cout << max({1,3,4,0,33,21,11}) << endl;
vector<int> vec = {1,3,4,0,33,21,11};
cout << *max_element(vec.begin(), vec.end()) << endl;
return 0;
}
浙公网安备 33010602011771号