# C++ 数据结构 集合 等 数据容器 汇总！
*C++ 技术栏*
在这里我们描述了在 C++ 中常见的数据容器，您可以在这里获取到他们的特性以及使用方式！
## 目录
[TOC]
# Vector
## 迭代器访问
Vector的迭代器其实就是数组中的元素指针，不过更方便我们使用，访问元素的步骤为：先获取到起始与结束位置的迭代器，然后不断移动起始迭代器的位置，直到其实迭代器的位置与结束迭代器的位置相同的时候，则代表迭代结束。
值得注意的是 在这里的终止指针其实就是一个哨兵！！！因此it2 的前一个才是元素！
### begin end 指针 - 手动操作指针
下面是一个基础的语法演示
```
// 获取到起始位置
auto vb = vector1.begin();
// 获取到终止位置
auto ve = vector1.end();
// 判断是否为同一个位置
vb == ve
```
根据上面的语法，我们可以像下面这样使用它！
```
#include <vector>
#include <iostream>
int main() {
std::vector<int> vector{2, 4, 6, 8, 10, 1024, 1000};
// 获取到起始和终止指针
auto it1 = vector.begin(), it2 = vector.end();
// 循环移动指针 直到 it1 到达 it2 的位置
while (it1 != it2) {
// 在这里使用 ++ 让 it1 自增！就相当于是在向后移动了
std::cout << *it1++ << std::endl;
}
}
```
### begin end 指针 - foreach + fun对象 自动操作指针
下面的操作将会自动的帮助我们迭代指针，更加的简洁！
```
// 导入STL函数库
#include "algorithm"
// 直接迭代
std::for_each(起始指针, 终止指针, 操作函数(函数的形参类型是被迭代的元素类型));
```
在下面就是一个举例！
```
#include <vector>
#include <iostream>
#include <algorithm>
void fun(int number){
std::cout << number << std::endl;
}
int main() {
std::vector<int> vector{2, 4, 6, 8, 10, 1024, 1000};
// 获取到起始和终止指针
auto it1 = vector.begin(), it2 = vector.end();
// 循环移动指针 并将每个元素传递给 fun 函数
std::for_each(it1, it2, fun);
}
```
## 泛型支持
下面的演示中，我们可以通过修改尖括号来实现自定义数据容器中的类型！
```
std::vector<泛型类型> myVector1;
```
### 准备一个自定义类型
```
#include <vector>
#include <iostream>
class User {
std::string name;
int age;
public:
User(std::string name, int age) : name(std::move(name)), age(age) {}
std::string getName() {
return this->name;
}
int getAge() const {
return this->age;
}
};
// 使用这个函数来封装打印逻辑
std::ostream &operator<<(std::ostream &ostream, User &user) {
return ostream << user.getName() << ' ' << user.getAge();
}
```
### 准备一个自定义类型的容器并使用
```
#include <vector>
#include <iostream>
class User {
std::string name;
int age;
public:
User(std::string name, int age) : name(std::move(name)), age(age) {}
std::string getName() {
return this->name;
}
int getAge() const {
return this->age;
}
};
// 使用这个函数来封装打印逻辑
std::ostream &operator<<(std::ostream &ostream, User &user) {
return ostream << user.getName() << ' ' << user.getAge();
}
// TODO 从这里开始就是自定义类型的代码了
#include <utility>
#include <algorithm>
void fun(User user) {
std::cout << user << std::endl;
}
int main() {
std::vector<User> vector{
User{"zhao", 21},
User{"yang", 20}
};
// 获取到起始和终止指针
auto it1 = vector.begin(), it2 = vector.end();
// 循环移动指针 并将每个元素传递给 fun 函数
std::for_each(it1, it2, fun);
}
```
## 构造与创建
```
// 创建一些向量 具有固定数值的
vector<int> vector1{1, 2, 3, 4};
// 指针拷贝构造 通常用来进行复制元素操作
vector<int> vector2{vector1.begin(), vector1.end()};
// n 个数值填充构造 快捷的指定元素和长度
vector<int> vector3(4, 7);
// 拷贝构造函数 （深拷贝）
vector<int> vector4(vector1);
```
## 修改与赋值
### 修改 - 修改一个容器中指定部分的元素为某个新元素
```
#include <vector>
#include <iostream>
// 这个函数是用来将 vector 快速迭代的一个函数
std::ostream &operator<<(std::ostream &ostream, std::vector<int> v) {
auto it1 = v.begin(), it2 = v.end();
while (it1 != it2)
ostream << *it1++ << ' ';
return ostream;
}
int main() {
std::vector<int> v{1, 2, 3, 4, 5};
// 通过索引修改元素
v[2] = 1024;
// 直接打印 vector 的所有元素
std::cout << v << std::endl;
}
```
### 赋值 - 修改一个容器中所有的元素为某个容器的元素
在下面是一个基础的使用示例
```
std::vector<int> v1{1, 2, 3, 4, };
std::vector<int> v2{10, 20, 300, 4, 5};
// 将 v1 中的元素 替换为 v2 中的元素
// 不论 v1 中的元素长度如何，在这里都会进行替换
// 最终长度和 v2 一致 数据和 v2 一致 这就是覆盖！
v1.assign(v2.begin(), v2.end());
```
我们可以像下面一样使用它！
```
#include <vector>
#include <iostream>
std::ostream &operator<<(std::ostream &ostream, std::vector<int> v) {
auto it1 = v.begin(), it2 = v.end();
while (it1 != it2)
ostream << *it1++ << ' ';
return ostream;
}
int main() {
std::vector<int> v1{1, 2, 3, 4, };
std::vector<int> v2{10, 20, 300, 4, 5};
// 将 v1 中的元素 替换为 v2 中的元素
// 不论 v1 中的元素长度如何，在这里都会进行替换
// 最终长度和 v2 一致 数据和 v2 一致 这就是覆盖！
v1.assign(v2.begin(), v2.end());
// 打印结果
std::cout << v1 << std::endl;
}
```
## 容量和大小
### 判断是否为空 - empty
```
#include <vector>
#include <iostream>
int main() {
std::vector<int> v1{};
// 判断容器是否为空 这打印出来的是 1 代表 true
std::cout << v1.empty() << std::endl;
// 添加一个元素之后再次判断容器是否为空 这里打印出来的是 0 代表 false
v1.push_back(1024);
std::cout << v1.empty() << std::endl;
}
```
### 获取到容器的容量 - capacity
capacity 能够有效的将一个容器的实际长度获取到，容器的容量一般都是会有些冗余的，在这可以看到实际占用多少个元素的空间！
> 值得注意的是，每次追加元素都可能导致容器容量发生变化，因为他们需要进行扩充！
```
#include <vector>
#include <iostream>
int main() {
std::vector<int> v1{};
// 这个时候 元素里面是空的，容量也是 0
std::cout << v1.capacity() << std::endl;
// 添加一些元素之后再次判断容器容器的长度 这个时候是 4 容器被扩充了
v1.push_back(1024);
v1.push_back(1024);
v1.push_back(1024);
std::cout << v1.capacity() << std::endl;
}
```
### 获取到容器中元素的个数 - size
与 capacity 不同的是，size 只返回元素的长度，对于实际长度并不关心，一般情况下，size 可能会更加常用。
```
#include <vector>
#include <iostream>
int main() {
std::vector<int> v1{};
// 判断容器元素数量 这里是 0 没有元素！
std::cout << v1.size() << std::endl;
// 添加一些元素之后再次判断容器元素数量 这里是 3
v1.push_back(1024);
v1.push_back(1024);
v1.push_back(1024);
std::cout << v1.size() << std::endl;
}
```
### 重新设定容器中元素的个数 - resize
#### 不设置填充数值
```
#include <vector>
#include <iostream>
std::ostream &operator<<(std::ostream &ostream1, std::vector<int> &v) {
for (const auto &item: v) {
ostream1 << item << '\t';
}
return ostream1;
}
int main() {
std::vector<int> v1{1, 2, 3, 4, 5, 6};
// 将容器的长度重新设置为 10
// 这个时候会比原先多出来 3 个元素，我们这里没有指定填充的数值 C++ 会默认填充 0
v1.resize(10);
// 打印出来看下
std::cout << v1 << std::endl;
// 如果缩小，则超出部分将会删除 优先删除右边的数据！
v1.resize(4);
// 打印出来看下
std::cout << v1 << std::endl;
}
```
#### 设置填充数值
```
#include <vector>
#include <iostream>
std::ostream &operator<<(std::ostream &ostream1, std::vector<int> &v) {
for (const auto &item: v) {
ostream1 << item << '\t';
}
return ostream1;
}
int main() {
std::vector<int> v1{1, 2, 3, 4, 5, 6};
// 将容器的长度重新设置为 10
// 这个时候会比原先多出来 3 个元素，我们这里没有指定填充的数值 C++ 会默认填充 0
v1.resize(10, 1024);
// 打印出来看下
std::cout << v1 << std::endl;
// 如果缩小，则超出部分将会删除 优先删除右边的数据！
v1.resize(4, 1024);
// 打印出来看下
std::cout << v1 << std::endl;
}
```
## 插入和删除
### 在容器的尾部插入 - push_back
```
#include <iostream>
#include <vector>
using namespace std;
ostream &operator<<(ostream &ostream1, vector<int> &vector) {
for (const auto &item: vector) {
cout << item << '\t';
}
return ostream1;
}
int main() {
// 创建一些向量
vector<int> vector1{1, 2, 3, 4};
cout << vector1 << endl;
// 在尾部插入一个元素
vector1.push_back(1024);
cout << vector1 << endl;
}
```
### 删除最后一个元素 - pop_back
```
#include <iostream>
#include <vector>
using namespace std;
ostream &operator<<(ostream &ostream1, vector<int> &vector) {
for (const auto &item: vector) {
cout << item << '\t';
}
return ostream1;
}
int main() {
// 创建一些向量
vector<int> vector1{1, 2, 3, 4};
cout << vector1 << endl;
// 将最后一个元素删掉
vector1.pop_back();
// 再一次打印
cout << vector1 << endl;
}
```
### 在迭代器指定位置插入 - insert
> 值得注意的是，插入成功之后，所有的元素会向后移动！
```
#include <iostream>
#include <vector>
using namespace std;
ostream &operator<<(ostream &ostream1, vector<int> &vector) {
for (const auto &item: vector) {
cout << item << '\t';
}
return ostream1;
}
int main() {
// 创建一些向量
vector<int> vector1{1, 2, 3, 4};
cout << vector1 << endl;
// 获取到第 2 索引元素对应的迭代器指针
auto it = vector1.begin() + 2;
// 在这个位置插入一个元素 1024
vector1.insert(it, 1024);
cout << vector1 << endl;
// 重新获取到第 2 索引迭代器指针
it = vector1.begin() + 2;
// 在第 2 索引位置插入 3 个 2048
vector1.insert(it, 3, 2048);
cout << vector1 << endl;
}
```
### 删除迭代器指定位置的元素 - erase
#### 删除指定位置的元素
```
#include <iostream>
#include <vector>
using namespace std;
ostream &operator<<(ostream &ostream1, vector<int> &vector) {
for (const auto &item: vector) {
cout << item << '\t';
}
return ostream1;
}
int main() {
// 创建一些向量
vector<int> vector1{1, 2, 3, 4, 5, 6, 7, 8, 9};
cout << vector1 << endl;
// 获取到第 2 索引元素对应的迭代器指针
auto it = vector1.begin() + 2;
// 将第 2 索引元素删除
vector1.erase(it);
// 最后查看结果
cout << vector1 << endl;
}
```
#### 删除指定范围的元素
```
#include <iostream>
#include <vector>
using namespace std;
ostream &operator<<(ostream &ostream1, vector<int> &vector) {
for (const auto &item: vector) {
cout << item << '\t';
}
return ostream1;
}
int main() {
// 创建一些向量
vector<int> vector1{1, 2, 3, 4, 5, 6, 7, 8, 9};
cout << vector1 << endl;
// 获取到第 2 索引元素对应的迭代器指针
auto it2 = vector1.begin() + 2;
// 获取到第 5 索引元素对应的迭代器指针
auto it5 = vector1.begin() + 5;
// 将第 2 ~5 索引元素删除 值得注意的是，因为数据结构中哨兵模式的存在 最后一个指针往往不一定有数值
// 因此为了避免一些不便的情况，这里的区间是左闭右开区间，因此我们需要对 it5 + 1 才能删掉 5 索引
vector1.erase(it2, it5 + 1);
// 最后查看结果
cout << vector1 << endl;
}
```
### 删除容器中所有的元素 - clear
```
#include <iostream>
#include <vector>
using namespace std;
ostream &operator<<(ostream &ostream1, vector<int> &vector) {
for (const auto &item: vector) {
cout << item << '\t';
}
return ostream1;
}
int main() {
// 创建一些向量
vector<int> vector1{1, 2, 3, 4, 5, 6, 7, 8, 9};
cout << vector1 << endl;
// 使用 clear 清理所有元素
vector1.clear();
cout << vector1 << endl;
}
```
## 数据存取
```
// 创建一些向量
vector<int> vector1{1, 2, 3, 4};
// 使用 at 函数获取到 2 索引处的数值
cout << vector1.at(2) << endl;
// 使用索引运算符获取到 2 索引处的数值
cout << vector1[2] << endl;
// 使用 front 函数获取到数组中的第一个元素
cout << vector1.front() << endl;
// 使用 back 函数获取到数组中的最后一个元素
cout << vector1.back() << endl;
```
## 容器互换
```
#include <iostream>
#include <vector>
using namespace std;
ostream &operator<<(ostream &ostream1, vector<int> &vector) {
for (const auto &item: vector) {
cout << item << '\t';
}
return ostream1;
}
int main() {
// 创建一些向量
vector<int> vector1{1, 2, 3, 4, 5, 6, 7, 8, 9}, vector2{20, 30, 40, 560};
cout << "vector1:" << vector1 << endl;
cout << "vector2:" << vector2 << endl;
cout << "交换之后" << endl;
// 将两个容器的元素进行交换
vector1.swap(vector2);
cout << "vector1:" << vector1 << endl;
cout << "vector2:" << vector2 << endl;
}
```
## 调整容器长度！
### 调整容器中 元素长度 的值 - resize
```
#include <iostream>
#include <vector>
using namespace std;
ostream &operator<<(ostream &ostream1, vector<int> &vector) {
for (const auto &item: vector) {
cout << item << '\t';
}
return ostream1;
}
int main() {
// 创建一些向量
vector<int> vector1{1, 2, 3, 4, 5, 6, 7, 8, 9};
// 打印向量的空间
cout << vector1 << endl;
// 调整预留空间 在这里我们设置为18 个元素 相当于是追加出 9 个int数据的空间
vector1.resize(18);
// 打印其中的元素 可以看见其中现在拓展为 18 个元素了
cout << vector1 << endl;
}
```
### 调整容器中 预留程度 的值 - reserve
```
#include <iostream>
#include <vector>
using namespace std;
ostream &operator<<(ostream &ostream1, vector<int> &vector) {
for (const auto &item: vector) {
cout << item << '\t';
}
return ostream1;
}
int main() {
// 创建一些向量
vector<int> vector1{1, 2, 3, 4, 5, 6, 7, 8, 9};
// 打印向量的空间
cout << vector1.capacity() << endl;
// 调整预留空间 在这里我们设置为预留 18 个空间 相当于是追加出 9 个int数据的空间
vector1.reserve(18);
// 打印其中的元素 可以看见其中现在拓展为 18 的空间了
cout << vector1.capacity() << endl;
// reserve 只能调整预留空间 不会影响到元素长度
cout << vector1 << endl;
}
```
# String
## 字符串的构造
```
// 导入String
#include "string"
// 导入 io 库
#include "iostream"
using namespace std;
int main() {
// 创建一个空字符串
std::string string1;
// 根据char* 创建字符串
std::string string2("zhao");
// 根据一个String 创建一个新字符串
std::string string3(string2 + "123");
// 使用n个字符构建字符串
std::string string4(4, 'a');
// 打印四个字符串
std::cout << string1 << std::endl;
std::cout << string2 << std::endl;
std::cout << string3 << std::endl;
std::cout << string4 << std::endl;
}
```
## 字符串的赋值
| 函数 | 说明 |
|------|------|
| `string()` | 默认构造空字符串 |
| `string(const char* s)` | 从 C 风格字符串构造 |
| `string(const string& str)` | 拷贝构造 |
| `string(size_t n, char c)` | 构造 n 个字符 c 的字符串 |
| `string& operator=(const string& str)` | 赋值 |
| `string& assign(...)` | 赋值（多种重载） |
### char 指针 赋值给字符串 - 等号运算符
char 指针 写法就是 `char* c`，很显然这是一个 C语言中使用到的字符串操作，我们可以像下面一样将这个转换为 C++ 中的一个 `string` 对象。
```
std::string string1 = cs;
```
```
// 导入String
#include "string"
// 导入 io 库
#include "iostream"
using namespace std;
int main() {
// 创建一个具有 10 个空间的 char* 指针
char* cs = new char[10]{
'z', 'h', 'a', 'o',
'z', 'h', 'a', 'o',
// 使用 \0 结尾 避免出现读取一些不属于 cs 范围的东西！
'x', '\0'
};
// 将 cs 中的数据传递给 string
// 最后的结果是 zhaozhaox
std::string string1 = cs;
cout << string1 << endl;
// 最后不要忘记释放
delete[] cs;
}
```
### string对象 赋值给字符串 - 等号运算符
```
string string1 = "zhao";
string string2 = string1;
```
下面是一个具体的示例！
```
// 导入String
#include "string"
// 导入 io 库
#include "iostream"
using namespace std;
int main() {
string string1 = "zhao";
string string2 = string1;
cout << string1 << endl;
cout << string2 << endl;
if (std::equal(string1.begin(), string1.end(), string2.begin())){
cout << "两个字符串相同！" << endl;
}
}
```
### char 对象 赋值给字符串 - 等号运算符
```
// 导入String
#include "string"
#include "iostream"
using namespace std;
int main() {
char c = 'z';
string string2 = &c;
cout << string2 << endl;
}
```
## 长度与容量
| 函数 | 说明 |
|------|------|
| `size()` / `length()` | 返回字符数（不包括 `\0`） |
| `empty()` | 判断是否为空 |
| `capacity()` | 返回当前分配的容量 |
| `reserve(n)` | 预留至少 n 个字符的空间 |
| `resize(n, c)` | 改变字符串长度，不足用 c 填充 |
| `clear()` | 清空字符串 |
### 读取字符串的长度和容量
```C++
#include "iostream"
using namespace std;
int main() {
system("chcp 65001");
string s;
getline(cin, s);
cout << "字符串是是否为空：" << (s.empty() ? "空的" : "不是空的") << endl;
cout << "字符串的长度：" << s.length() << endl;
cout << "字符串容器分配的长度：" << s.capacity() << endl;
}
```
### 修改字符串的长度和容量
```C++
#include "iostream"
using namespace std;
void fun(const string *s) {
cout << "=========" << endl;
cout << "字符串的内存地址：" << s << endl;
cout << "字符串的内容：" << *s << endl;
cout << "字符串的容量：" << s->capacity() << endl;
cout << "字符串的长度：" << s->length() << endl;
}
int main() {
system("chcp 65001");
string s;
fun(&s);
// 修改字符串的初始容量
s.reserve(30);
cout << "字符串容量被修改了" << endl;
fun(&s);
// 追加字符
s.push_back('z');
fun(&s);
// 批量追加字符串
string temp = "this is a data!";
// 使用拷贝的方式直接给 s
s = temp;
cout << "修改了字符串的内容" << endl;
fun(&s);
// 修改字符串的长度 缩短到 10 个字符
s.resize(10);
cout << "缩短字符串长度为 10" << endl;
fun(&s);
// 重新将字符串的长度拓展为 15 拓展的时候多出来的位置使用 - 填充
s.resize(15, '-');
cout << "拓展字符串长度为 10" << endl;
fun(&s);
}
```
## 访问字符
| 函数 | 说明 |
|------|------|
| `operator[](n)` | 获取第 n 个字符（不检查越界） |
| `at(n)` | 获取第 n 个字符（越界抛出 `out_of_range`） |
| `front()` | 第一个字符 |
| `back()` | 最后一个字符 |
| `data()` / `c_str()` | 返回 C 风格字符串指针 |
## 修改字符串
| 函数 | 说明 |
|------|------|
| `append(str)` / `+=` | 追加字符串 |
| `push_back(c)` | 在末尾添加一个字符 |
| `pop_back()` | 删除最后一个字符（C++11） |
| `insert(pos, str)` | 在位置 pos 插入字符串 |
| `erase(pos, len)` | 从 pos 开始删除 len 个字符 |
| `replace(pos, len, str)` | 替换从 pos 开始的 len 个字符为 str |
| `swap(str)` | 与另一个字符串交换内容 |
```
#include "iostream"
using namespace std;
void fun(const string *s) {
cout << "=========" << endl;
cout << "字符串的内存地址：" << s << endl;
cout << "字符串的内容：" << *s << endl;
cout << "字符串的容量：" << s->capacity() << endl;
cout << "字符串的长度：" << s->length() << endl;
}
int main() {
system("chcp 65001");
string s = "this is a data!";
fun(&s);
s.insert(10, "123");
fun(&s);
s.append(" this is new string!");
}
```
## 查找与搜索
| 函数 | 说明 |
|------|------|
| `find(str, pos)` | 从 pos 开始查找 str 第一次出现的位置 |
| `rfind(str, pos)` | 从 pos 开始反向查找最后一次出现 |
| `find_first_of(str, pos)` | 查找 str 中任意字符第一次出现 |
| `find_last_of(str, pos)` | 查找 str 中任意字符最后一次出现 |
| `find_first_not_of(str, pos)` | 查找不在 str 中的第一个字符 |
| `find_last_not_of(str, pos)` | 查找不在 str 中的最后一个字符 |
| 返回值：`size_t`，找不到返回 `string::npos` |
```
#include "iostream"
using namespace std;
int main() {
string s = "this is a data!";
// 从 10 索引开始寻找 t 出现的索引
const unsigned long index = s.find('t', 10);
cout << index << endl;
cout << s[index] << endl;
// 开始寻找 在 "this is zhao" 字符串中没出现过的字符(取第一个)，比如 d ! 都属于 因为 "this is zhao" 里面没出现过
const unsigned long index1 = s.find_first_not_of("this is zhao");
cout << index1 << endl;
cout << s[index1] << endl;
// 开始寻找 在 "is zhao" 字符串中出现过的字符(取第一个)
const unsigned long index2 = s.find_first_of("is zhao");
cout << index2 << endl;
cout << s[index2] << endl;
}
```
## 子字符串切分
| 函数 | 说明 |
|------|------|
| `substr(pos, len)` | 返回从 pos 开始长度为 len 的子串 |
```cpp
string s = "Hello World";
string sub = s.substr(6, 5); // "World"
```
### 比较
#### C++风格 - compare
| 函数 | 说明 |
|------|------|
| `compare(str)` | 比较字符串，返回 0（相等）、>0（大于）、<0（小于） |
| `==`, `!=`, `<`, `<=`, `>`, `>=` | 重载比较运算符 |
```cpp
string a = "apple", b = "banana";
if (a < b) cout << "apple comes first";
if (a == "apple") cout << "match";
```
## 其他实用函数
| 函数 | 说明 |
|------|------|
| `copy(buf, len, pos)` | 从 pos 复制 len 个字符到 buf（不加 `\0`） |
| `get_allocator()` | 获取分配器（较少用） |
## 📚 总结
| 类别 | 常用函数 |
|------|----------|
| 构造 | `string()`, `assign()` |
| 大小 | `size()`, `empty()`, `clear()` |
| 访问 | `[]`, `at()`, `front()`, `back()`, `c_str()` |
| 修改 | `+=`, `append()`, `insert()`, `erase()`, `replace()` |
| 查找 | `find()`, `rfind()`, `substr()` |
| 比较 | `==`, `<`, `compare()` |
# queue 队列
这是C++标准库中 `std::queue`（队列）所有常用成员函数的列表，包含函数名、解释和调用方法。
**注意**：`std::queue` 是一个容器适配器，默认基于 `std::deque` 实现，遵循先进先出（FIFO）原则。你只能访问队首和队尾元素。
| 函数名 | 解释 | 调用方法示例 |
| :--- | :--- | :--- |
| `queue<T> q;` | **构造函数**：创建一个空的队列，元素类型为 `T`。 | `std::queue<int> myQueue;` |
| `~queue()` | **析构函数**：销毁队列，释放所有元素。 | `// 通常在作用域结束时自动调用` |
| `push(const T& value)` | **入队**：在队列的**末尾**插入一个元素的副本。 | `myQueue.push(10);` |
| `push(T&& value)` | **入队 (移动)**：在队列的**末尾**插入一个右值引用的元素（移动语义，更高效）。 | `myQueue.push(std::move(someObject));` |
| `emplace(Args&&... args)` | **原地构造入队**：使用提供的参数在队列**末尾**直接构造一个新元素，避免了拷贝或移动。 | `myQueue.emplace(5, "hello"); // 假设T是pair<int, string>` |
| `pop()` | **出队**：移除队列**最前面**的元素。该函数不返回被移除的元素。 | `myQueue.pop();` |
| `front()` | **访问队首**：返回对队列**最前面**元素的引用。在调用前必须确保队列不为空。 | `int first = myQueue.front();` |
| `back()` | **访问队尾**：返回对队列**最后面**元素的引用。在调用前必须确保队列不为空。 | `int last = myQueue.back();` |
| `empty()` | **检查是否为空**：如果队列为空，则返回 `true`，否则返回 `false`。 | `if (myQueue.empty()) { /* 队列为空 */ }` |
| `size()` | **获取大小**：返回队列中当前元素的个数。 | `size_t count = myQueue.size();` |
**重要提示**：
1. **访问限制**：`std::queue` 只允许访问 `front()` 和 `back()`。你不能直接通过索引（如 `[]`）访问队列中间的元素。
2. **安全检查**：在调用 `front()`、`back()` 和 `pop()` 之前，**强烈建议**先使用 `empty()` 检查队列是否为空。对空队列调用这些函数会导致**未定义行为**（通常是程序崩溃）。
3. **性能**：
* `push`、`pop`、`front`、`back`、`empty`、`size` 通常都是常数时间复杂度 O(1)。
* `emplace` 通常比 `push` 更高效，因为它避免了临时对象的创建。
# stack - 栈
这是C++标准库中 `std::stack`（栈）所有常用成员函数的完整列表，包含函数名、清晰解释和调用方法。
**注意**：`std::stack` 是一个容器适配器，默认基于 `std::deque` 实现，遵循后进先出（LIFO）原则。你只能访问栈顶元素。
| 函数名 | 解释 | 调用方法示例 |
| :--- | :--- | :--- |
| `stack<T> s;` | **构造函数**：创建一个空的栈，元素类型为 `T`。 | `std::stack<int> myStack;` |
| `~stack()` | **析构函数**：销毁栈，释放所有元素。**无需手动调用**，对象离开作用域时自动执行。 | `// 通常在作用域结束时自动调用` |
| `push(const T& value)` | **入栈**：将一个元素的副本**压入**栈的**顶部**。 | `myStack.push(10);` |
| `push(T&& value)` | **入栈 (移动)**：将一个右值引用的元素（移动语义）**压入**栈的**顶部**，避免拷贝，更高效。 | `myStack.push(std::move(someObject));` |
| `emplace(Args&&... args)` | **原地构造入栈**：使用提供的参数在栈的**顶部**直接构造一个新元素。这通常比 `push` 更高效，因为它避免了创建临时对象。 | `myStack.emplace(5, "hello"); // 假设T是pair<int, string>` |
| `pop()` | **出栈**：移除栈**最顶部**的元素。该函数**不返回**被移除的元素。 | `myStack.pop();` |
| `top()` | **访问栈顶**：返回对栈**最顶部**元素的引用。**在调用前必须确保栈不为空！** 对空栈调用此函数会导致未定义行为（通常是程序崩溃）。 | `int topElement = myStack.top();` |
| `empty()` | **检查是否为空**：如果栈中没有任何元素，则返回 `true`，否则返回 `false`。 | `if (myStack.empty()) { /* 栈为空 */ }` |
| `size()` | **获取大小**：返回栈中当前元素的个数。 | `size_t count = myStack.size();` |
**重要提示与使用原则**：
1. **访问限制**：`std::stack` 是一个严格的后进先出（LIFO）容器适配器。你**只能**访问和操作栈顶的元素（通过 `top()` 和 `pop()`），以及在栈顶添加元素（通过 `push()`/`emplace()`）。你无法直接访问栈中的其他元素。
2. **安全检查**：在调用 `top()` 和 `pop()` 之前，**必须**先使用 `empty()` 检查栈是否为空。对一个空栈执行这些操作是未定义行为，程序极有可能崩溃。
3. **性能**：
* `push`、`pop`、`top`、`empty`、`size` 通常都是常数时间复杂度 O(1)。
* `emplace` 通常比 `push` 更高效，因为它直接在容器内部构造对象，避免了拷贝或移动的开销。
4. **自动内存管理**：和 `std::vector`、`std::queue` 一样，`std::stack` 遵循 RAII 原则。当 `std::stack` 对象离开其作用域时，其析构函数 `~stack()` 会**自动被调用**，释放所有内部资源。**您不需要也不应该手动调用 `~stack()`**。
# map - 字典/映射
好的，这是C++标准库中 `std::map`（映射）所有常用成员函数的完整列表，包含函数名、清晰解释和调用方法。
**注意**：`std::map` 是一个关联容器，存储键值对 `(key, value)`，并根据**键 (key)** 进行自动排序（默认升序）。它保证键的唯一性（不允许重复的键）。
| 函数名 | 解释 | 调用方法示例 |
| :--- | :--- | :--- |
| `map<Key, T> m;` | **构造函数**：创建一个空的映射，键的类型为 `Key`，值的类型为 `T`。 | `std::map<std::string, int> myMap;` |
| `~map()` | **析构函数**：销毁映射，释放所有键值对占用的内存。**无需手动调用**，对象离开作用域时自动执行。 | `// 通常在作用域结束时自动调用` |
| `insert(const value_type& pair)` | **插入**：尝试插入一个 `std::pair<const Key, T>` 类型的键值对。如果键 `pair.first` 在映射中已存在，则插入**失败**，且映射内容不变。返回一个 `std::pair<iterator, bool>`，其中 `bool` 表示插入是否成功 (`true`/`false`)，`iterator` 指向插入的元素（或已存在的元素）。 | `auto result = myMap.insert(std::make_pair("apple", 5));<br>if (result.second) { /* 插入成功 */ }` |
| `insert(InputIt first, InputIt last)` | **范围插入**：将迭代器 `first` 到 `last` 范围内的所有元素（键值对）插入到映射中。 | `std::vector<std::pair<std::string, int>> vec = {{"a", 1}, {"b", 2}};<br>myMap.insert(vec.begin(), vec.end());` |
| `insert(initializer_list_type ilist)` | **列表初始化插入**：将初始化列表 `ilist` 中的所有键值对插入到映射中。 | `myMap.insert({{"orange", 3}, {"banana", 7}});` |
| `insert_or_assign(const Key& key, T&& value)` | **插入或赋值**：如果键 `key` 不存在，则插入 `(key, value)`；如果键 `key` 已存在，则将其对应的值更新为 `value`。返回一个 `std::pair<iterator, bool>`，`bool` 为 `true` 表示插入，`false` 表示赋值。 | `myMap.insert_or_assign("apple", 10); // 如果"apple"存在则更新值为10，否则插入` |
| `emplace(Args&&... args)` | **原地构造插入**：使用提供的参数在映射中直接构造一个新元素（键值对）。如果构造出的键已存在，则插入失败。这通常比 `insert` 更高效。返回值同 `insert`。 | `myMap.emplace("grape", 8);` |
| `emplace_hint(const_iterator hint, Args&&... args)` | **带提示的原地构造插入**：类似于 `emplace`，但提供一个迭代器 `hint` 作为插入位置的提示，可能提高插入效率（尤其在已知大致位置时）。 | `auto hint = myMap.find("apple");<br>myMap.emplace_hint(hint, "cherry", 6);` |
| `erase(const Key& key)` | **按键删除**：删除键为 `key` 的元素。返回值为删除的元素个数（`std::map` 中只能是 0 或 1）。 | `size_t numErased = myMap.erase("apple"); // 删除键为"apple"的元素` |
| `erase(const_iterator pos)` | **按迭代器删除**：删除迭代器 `pos` 所指向的单个元素。返回指向被删除元素下一个元素的迭代器。 | `auto it = myMap.find("banana");<br>if (it != myMap.end()) {<br> myMap.erase(it); // 删除it指向的元素<br>}` |
| `erase(const_iterator first, const_iterator last)` | **按范围删除**：删除从迭代器 `first` 到 `last`（不包含 `last`）范围内的所有元素。返回值为 `void`。 | `myMap.erase(myMap.begin(), myMap.find("m")); // 删除从开始到键"m"之前的所有元素` |
| `clear()` | **清空**：删除映射中的所有元素，使其变为空。 | `myMap.clear(); // 移除所有键值对` |
| `find(const Key& key)` | **查找**：查找键为 `key` 的元素。如果找到，返回指向该元素的 `iterator`；如果未找到，返回 `end()` 迭代器。 | `auto it = myMap.find("apple");<br>if (it != myMap.end()) {<br> int value = it->second; // 获取值<br>}` |
| `count(const Key& key)` | **计数**：返回键为 `key` 的元素个数。在 `std::map` 中，结果只能是 0（不存在）或 1（存在）。 | `if (myMap.count("apple") > 0) { /* "apple" 存在 */ }` |
| `at(const Key& key)` | **访问（带边界检查）**：返回键为 `key` 的元素的引用。如果键 `key` 不存在，则抛出 `std::out_of_range` 异常。 | `try {<br> int& value = myMap.at("apple");<br>} catch (const std::out_of_range& e) {<br> // 处理键不存在的情况<br>}` |
| `operator[](const Key& key)` | **下标访问**：返回键为 `key` 的元素的引用。**如果键 `key` 不存在，它会自动创建一个以 `key` 为键、值为 `T()`（`T`类型的默认值，如0、空字符串等）的新元素并返回其引用**。这是与 `at()` 的关键区别。 | `myMap["apple"] = 5; // 如果"apple"不存在，会先创建一个值为0的元素，再赋值为5<br>int value = myMap["orange"]; // 如果"orange"不存在，会创建并返回0` |
| `empty()` | **检查是否为空**：如果映射中没有任何键值对，则返回 `true`，否则返回 `false`。 | `if (myMap.empty()) { /* 映射为空 */ }` |
| `size()` | **获取大小**：返回映射中当前键值对的个数。 | `size_t count = myMap.size();` |
| `max_size()` | **最大可能大小**：返回映射理论上能容纳的最大元素个数（受系统或库实现限制）。 | `size_t maxNum = myMap.max_size();` |
| `begin()` / `cbegin()` | **开始迭代器**：返回指向映射中第一个（最小键）元素的 `iterator` / `const_iterator`。 | `for (auto it = myMap.begin(); it != myMap.end(); ++it) { ... }` |
| `end()` / `cend()` | **结束迭代器**：返回指向映射中最后一个元素**之后**位置的 `iterator` / `const_iterator`。 | `// 常用于循环终止条件` |
| `rbegin()` / `crbegin()` | **反向开始迭代器**：返回指向映射中最后一个（最大键）元素的 `reverse_iterator` / `const_reverse_iterator`。 | `for (auto rit = myMap.rbegin(); rit != myMap.rend(); ++rit) { ... }` |
| `rend()` / `crend()` | **反向结束迭代器**：返回指向映射中第一个元素**之前**位置的 `reverse_iterator` / `const_reverse_iterator`。 | `// 常用于反向循环终止条件` |
**重要提示**：
1. **自动排序**：`std::map` 内部始终按键的升序（或自定义比较函数定义的顺序）排序。
2. **键的唯一性**：`std::map` 不允许有重复的键。尝试插入已存在的键会失败（`insert`）或更新值（`insert_or_assign`, `operator[]`）。
3. **`operator[]` 的副作用**：使用 `operator[]` 访问一个不存在的键会**自动创建**该键，这可能导致意外的内存分配和性能开销。如果只是想检查存在性或避免创建，应使用 `find()` 或 `at()`。
4. **性能**：`insert`, `erase`, `find`, `count`, `at`, `operator[]` 的平均时间复杂度为 O(log n)，因为 `std::map` 通常是基于红黑树实现的。
5. **自动内存管理**：和 `std::vector`, `std::queue`, `std::stack` 一样，`std::map` 遵循 RAII 原则。当 `std::map` 对象离开其作用域时，其析构函数 `~map()` 会**自动被调用**，释放所有内部资源。**您不需要也不应该手动调用 `~map()`**。
------
***操作记录***
作者：[zhao](https://www.lingyuzhao.top//index.html?search=4 "zhao")
操作时间：2025-08-01 22:59:10 星期五 【时区：UTC 8】
事件描述备注：保存/发布
中国 天津市 天津
[](如果不需要此记录可以手动删除，每次保存都会自动的追加记录)
