# STL 常用容器

> [!info] 学习导航
> 返回：[[C++ 学习指南]]
> 前置知识：[[计算机系/C++/14 STL 基础、容器与迭代器|STL 基础、容器与迭代器]]

## `std::array` 容器

std::array 是 C++ 标准库中的一个模板类，它定义在 \<array> 头文件中。std::array 模板类提供了一个固定大小的数组，其大小在编译时确定，并且不允许动态改变。

**语法**

std::array 的基本语法如下：

```cpp
#include <array>
std::array<T, N> array_name;
```

- T 是数组中元素的类型。
- N 是数组的大小，必须是一个非负整数。

以下是 \<array> 中的一些常用成员函数：

| **函数**              | **说明**                         |
| --------------------- | -------------------------------- |
| at(size_t  pos)       | 返回指定位置的元素，带边界检查   |
| operator[]            | 返回指定位置的元素，不带边界检查 |
| front()               | 返回数组的第一个元素             |
| back()                | 返回数组的最后一个元素           |
| data()                | 返回指向数组数据的指针           |
| size()                | 返回数组大小（固定不变）         |
| fill(const  T& value) | 将数组所有元素设置为指定值       |
| swap(array&  other)   | 交换两个数组的内容               |
| begin() / end()       | 返回数组的起始/结束迭代器        |


## `std::vector` 容器

**基本特性:**

- **动态大小**：vector 的大小可以根据需要自动增长和缩小。
- **连续存储**：vector 中的元素在内存中是连续存储的，这使得访问元素非常快速。
- **可迭代**：vector 可以被迭代，你可以使用循环（如 for 循环）来访问它的元素。
- **元素类型**：vector 可以存储任何类型的元素，包括内置类型、对象、指针等。


**创建 Vector**

创建一个 vector 可以像创建其他变量一样简单：

```cpp
std::vector<int> myVector; // 创建一个存储整数的空 vector
```

这将创建一个空的整数向量,也可以在创建时指定初始大小和初始值：

```cpp
std::vector<int> myVector(5); // 创建一个包含 5 个整数的 vector，每个值都为默认值（0）
std::vector<int> myVector(5, 10); // 创建一个包含 5 个整数的 vector，每个值都为 10
```

或：

```cpp
std::vector<int> vec; // 默认初始化一个空的 vector
std::vector<int> vec2 = {1, 2, 3, 4}; // 初始化一个包含元素的 vector
```

**添加元素**

可以使用 push_back 方法向 vector 中添加元素：

```cpp
myVector.push_back(7); // 将整数 7 添加到 vector 的末尾
```

**访问元素**

可以使用下标操作符 [] 或 at() 方法访问 vector 中的元素：

```cpp
int x = myVector[0]; // 获取第一个元素
int y = myVector.at(1); // 获取第二个元素
```

**获取大小**

可以使用 size() 方法获取 vector 中元素的数量：

```cpp
int size = myVector.size(); // 获取 vector 中的元素数量
```

**迭代访问**

可以使用迭代器遍历 vector 中的元素：

```cpp
for (auto it = myVector.begin(); it != myVector.end(); ++it) {
  std::cout << *it << " ";
}
```

或者使用范围循环：

```cpp
for (int element : myVector) {
  std::cout << element << " ";
}
```

**删除元素**

可以使用 erase() 方法删除 vector 中的元素：

```cpp
myVector.erase(myVector.begin() + 2); // 删除第三个元素
```

**清空 Vector**

可以使用 clear() 方法清空 vector 中的所有元素：

```cpp
myVector.clear(); // 清空 vector
```

嵌套vector

```cpp
// 打印乘法表
  for (vector<vector<int>>::iterator iter = outer.begin(); iter != outer.end(); ++iter) {
// 获取当前行的向量
    vector<int> inner = *iter;
    for (vector<int>::iterator it = inner.begin(); it != inner.end(); ++it)
// 打印当前元素，设置宽度为 4 个字符，确保对齐
      cout << setw(4) << *it;
// 打印换行符，开始新的一行
    cout << endl;
  }
```

| **函数**                   | **说明**                         |
| -------------------------- | -------------------------------- |
| push_back(const  T& val)   | 在末尾添加元素                   |
| pop_back()                 | 删除末尾元素                     |
| at(size_t  pos)            | 返回指定位置的元素，带边界检查   |
| operator[]                 | 返回指定位置的元素，不带边界检查 |
| front()                    | 返回第一个元素                   |
| back()                     | 返回最后一个元素                 |
| data()                     | 返回指向底层数组的指针           |
| size()                     | 返回当前元素数量                 |
| capacity()                 | 返回当前分配的容量               |
| reserve(size_t  n)         | 预留至少 n 个元素的存储空间      |
| resize(size_t  n)          | 将元素数量调整为 n               |
| clear()                    | 清空所有元素                     |
| insert(iterator  pos, val) | 在指定位置插入元素               |
| erase(iterator  pos)       | 删除指定位置的元素               |
| begin() / end()            | 返回起始/结束迭代器              |

Reserve成员函数内部用于保证向量内部空间，在程序可预测所需向量时可一步到位建立内部空间，reserve不影响向量内部实际元素个数，不会导致成员函数size返回的向量内元素个数

**关键特性：**

1. **不影响元素个数**：
   - **reserve(n)** 只是预分配内存空间，不会改变向量中实际存储的元素数量。
   - **size()** 返回的是当前向量中实际存在的元素个数，**reserve** 不会影响这个值。
   - **capacity()** 返回的是当前向量已分配的内存空间能容纳的元素数量（≥ **size()**）。

```cpp
#include <iostream>
#include <vector>
int main() {
  std::vector<int> vec;
// 预分配空间（不影响 size）
  vec.reserve(100);
  std::cout << "After reserve(100):" << std::endl;
  std::cout << " size() = " << vec.size() << std::endl; // 输出 0
  std::cout << " capacity() = " << vec.capacity() << std::endl; // 输出 100
// 添加元素
  vec.push_back(42);
  std::cout << "After push_back:" << std::endl;
  std::cout << " size() = " << vec.size() << std::endl; // 输出 1
  std::cout << " capacity() = " << vec.capacity() << std::endl; // 输出 100
}
```

## `std::deque` 容器


在 C++中，\<deque> 是标准模板库（STL）的一部分，它提供了双端队列（double-ended queue）的实现。

双端队列是一种允许在两端进行插入和删除操作的线性数据结构。

\<deque> 的全称是 "double-ended queue"，它在C++中以模板类的形式存在，允许存储任意类型的数据。

\<deque> 是一个动态数组，它提供了快速的随机访问能力，同时允许在两端进行高效的插入和删除操作。这使得 \<deque> 成为处理需要频繁插入和删除元素的场景的理想选择。

多个分段的内存块中，段内连续，段间不需要连续

**语法**

在 C++ 中，使用 \<deque> 需要包含头文件 #include \<deque>。以下是 \<deque> 的基本语法：

```cpp
#include <iostream>
#include <deque>
int main() {
  std::deque<int> myDeque; // 创建一个整数类型的双端队列
// 接下来可以进行插入、删除等操作
  return 0;
}
```

**常用操作**

下面是 std::deque 容器的一些常用成员函数：

| **函数名称**                          | **功能描述**                                 |
| ------------------------------------- | -------------------------------------------- |
| deque()                               | 默认构造函数，创建一个空的 deque 容器。      |
| deque(size_type  n)                   | 创建一个包含 n 个默认值元素的 deque 容器。   |
| deque(size_type  n, const T& value)   | 创建一个包含 n 个值为 value 的 deque 容器。  |
| deque(initializer_list\<T>  il)        | 使用初始化列表 il 构造 deque 容器。          |
| operator=                             | 赋值操作符，赋值给 deque 容器。              |
| assign()                              | 用新值替换 deque 容器中的所有元素。          |
| at(size_type  pos)                    | 返回 pos 位置的元素，并进行范围检查。        |
| operator[](size_type  pos)            | 返回 pos 位置的元素，不进行范围检查。        |
| front()                               | 返回第一个元素的引用。                       |
| back()                                | 返回最后一个元素的引用。                     |
| begin()                               | 返回指向第一个元素的迭代器。                 |
| end()                                 | 返回指向末尾元素后一位置的迭代器。           |
| rbegin()                              | 返回指向最后一个元素的逆向迭代器。           |
| rend()                                | 返回指向第一个元素之前位置的逆向迭代器。     |
| empty()                               | 检查容器是否为空。                           |
| size()                                | 返回容器中的元素个数。                       |
| max_size()                            | 返回容器可容纳的最大元素个数。               |
| clear()                               | 清除容器中的所有元素。                       |
| insert(iterator  pos, const T& value) | 在 pos 位置插入 value 元素。                 |
| erase(iterator  pos)                  | 移除 pos 位置的元素。                        |
| push_back(const  T& value)            | 在容器末尾添加 value 元素。                  |
| pop_back()                            | 移除容器末尾的元素。                         |
| push_front(const  T& value)           | 在容器前端添加 value 元素。                  |
| pop_front()                           | 移除容器前端的元素。                         |
| resize(size_type  count)              | 调整容器大小为 count，多出部分用默认值填充。 |
| swap(deque&  other)                   | 交换两个 deque 容器的内容。                  |
| get_allocator()                       | 返回一个用于构造双端队列的分配器对象的副本。 |


## `std::list` 容器

C++ 标准库提供了丰富的功能，其中 \<list> 是一个非常重要的容器类，用于存储元素集合，支持双向迭代器。

\<list> 是 C++ 标准模板库（STL）中的一个序列容器，它允许在容器的任意位置快速插入和删除元素。与数组或向量（\<vector>）不同，\<list> 不需要在创建时指定大小，并且可以在任何位置添加或删除元素，而不需要重新分配内存。

| **函数**                   | **说明**                  |
| -------------------------- | ------------------------- |
| push_back(const  T& val)   | 在链表末尾添加元素        |
| push_front(const  T& val)  | 在链表头部添加元素        |
| pop_back()                 | 删除链表末尾的元素        |
| pop_front()                | 删除链表头部的元素        |
| insert(iterator  pos, val) | 在指定位置插入元素        |
| erase(iterator  pos)       | 删除指定位置的元素        |
| clear()                    | 清空所有元素              |
| size()                     | 返回链表中的元素数量      |
| empty()                    | 检查链表是否为空          |
| front()                    | 返回链表第一个元素        |
| back()                     | 返回链表最后一个元素      |
| remove(const  T& val)      | 删除所有等于指定值的元素  |
| sort()                     | 对链表中的元素进行排序    |
| merge(list&  other)        | 合并另一个已排序的链表    |
| reverse()                  | 反转链表                  |
| begin() / end()            | 返回链表的起始/结束迭代器 |


| **特性**          | **std::list**                | **std::vector**              | **std::deque**               |
| ----------------- | ---------------------------- | ---------------------------- | ---------------------------- |
| **内存结构**      | 非连续内存，双向链表         | 连续内存                     | 分段连续内存                 |
| **访问性能**      | 顺序访问较快，随机访问慢     | 随机访问快                   | 末尾和头部访问都快           |
| **插入/删除性能** | 任意位置插入、删除快         | 末尾插入快，中间位置慢       | 头尾插入、删除快             |
| **适用场景**      | 频繁在中间插入/删除          | 需要高效随机访问             | 需要在头尾快速插入/删除      |
| **迭代器稳定性**  | 稳定，元素插入或删除不会失效 | 插入、删除可能导致迭代器失效 | 插入、删除可能导致迭代器失效 |

**注意事项**

- \<list> 的元素是按插入顺序存储的，而不是按元素值排序。
- 由于 \<list> 的元素存储在不同的内存位置，所以它不适合需要随机访问的场景。
- 与向量相比，\<list> 的内存使用效率较低，因为每个元素都需要额外的空间来存储指向前后元素的指针。

## `std::stack` 容器适配器

\<stack> 是 C++ 标准模板库（STL）的一部分，它实现了一个后进先出（LIFO，Last In First Out）的数据结构。这种数据结构非常适合于需要"最后添加的元素最先被移除"的场景。

\<stack> 容器适配器提供了一个栈的接口，它基于其他容器（如 deque 或 vector）来实现。栈的元素是线性排列的，但只允许在一端（栈顶）进行添加和移除操作。

**基本操作**

- push(): 在栈顶添加一个元素。
- pop(): 移除栈顶元素。
- top(): 返回栈顶元素的引用，但不移除它。
- empty(): 检查栈是否为空。
- size(): 返回栈中元素的数量。

- \<stack> 不提供直接访问栈中元素的方法，只能通过 top() 访问栈顶元素。
- 尝试在空栈上调用 top() 或 pop() 将导致未定义行为。
- \<stack> 的底层容器可以是任何支持随机访问迭代器的序列容器，如 vector 或 deque。


## `std::queue` 容器适配器

C++ 标准库中的 \<queue> 头文件提供了队列（Queue）数据结构的实现。队列是一种先进先出（FIFO, First In First Out）的数据结构，它允许在一端添加元素（称为队尾），并在另一端移除元素（称为队首）。

队列是一种线性数据结构，它遵循以下规则：

- 元素只能从队尾添加。
- 元素只能从队首移除。

**语法**

在 C++ 中，队列的语法如下：

```cpp
#include <queue>
// 声明队列
std::queue<Type> q;
```

这里 Type 是队列中存储元素的数据类型。

**常用操作**

队列提供了以下常用操作：

- empty(): 检查队列是否为空。
- size(): 返回队列中的元素数量。
- front(): 返回队首元素的引用。
- back(): 返回队尾元素的引用。
- push(): 在队尾添加一个元素。
- pop(): 移除队首元素。

**注意事项**

- 队列不允许随机访问元素，即不能直接通过索引访问队列中的元素。
- 队列的实现通常使用链表或动态数组，这取决于具体的实现。


## `std::string`

C++ 标准库（Standard Template Library, STL）是 C++ 的核心组成部分之一，提供了丰富的数据结构和算法。

\<string> 是 C++ 标准库中用于处理字符串的头文件。

在 C++ 中，字符串是由字符组成的序列。\<string> 头文件提供了 std::string 类，它是对 C 风格字符串的封装，提供了更安全、更易用的字符串操作功能。

| **函数名**          | **描述**                                       | **示例代码**                                  |
| ------------------- | ---------------------------------------------- | --------------------------------------------- |
| size()              | 返回字符串的长度（字符数）。                   | std::cout  << str.size();                     |
| length()            | 与 size() 相同，返回字符串的长度。             | std::cout  << str.length();                   |
| empty()             | 判断字符串是否为空。                           | std::cout  << (str.empty() ? "Yes" : "No");   |
| operator[]          | 访问字符串中指定位置的字符。                   | std::cout  << str[0];                         |
| at()                | 访问字符串中指定位置的字符（带边界检查）。     | std::cout  << str.at(0);                      |
| substr()            | 返回从指定位置开始的子字符串。                 | std::string  sub = str.substr(0, 5);          |
| find()              | 查找子字符串在字符串中的位置。                 | std::cout  << str.find("sub") << std::endl;   |
| rfind()             | 从字符串末尾开始查找子字符串的位置。           | std::cout  << str.rfind("sub") << std::endl;  |
| replace()           | 替换字符串中的部分内容。                       | str.replace(pos,  length, "new_substring");   |
| append()            | 在字符串末尾添加内容。                         | str.append("  more");                         |
| insert()            | 在指定位置插入内容。                           | str.insert(pos,  "inserted");                 |
| erase()             | 删除指定位置的字符或子字符串。                 | str.erase(pos,  length);                      |
| clear()             | 清空字符串。                                   | str.clear();                                  |
| c_str()             | 返回 C 风格的字符串（以 null 结尾）。          | const  char\* cstr = str.c_str();              |
| data()              | 返回指向字符数据的指针（C++11 及之后的版本）。 | const  char\* data = str.data();               |
| compare()           | 比较两个字符串。                               | int  result = str.compare("other");           |
| find_first_of()     | 查找第一个匹配任意字符的位置。                 | size_t  pos = str.find_first_of("aeiou");     |
| find_last_of()      | 查找最后一个匹配任意字符的位置。               | size_t  pos = str.find_last_of("aeiou");      |
| find_first_not_of() | 查找第一个不匹配任意字符的位置。               | size_t  pos = str.find_first_not_of("aeiou"); |
| find_last_not_of()  | 查找最后一个不匹配任意字符的位置。             | size_t  pos = str.find_last_not_of("aeiou");  |


## `std::forward_list`（待补充）

## `std::map` 容器


在 C++ 中，\<map> 是标准模板库（STL）的一部分，它提供了一种关联容器，用于存储键值对（key-value pairs）。

map 容器中的元素是按照键的顺序自动排序的，这使得它非常适合需要快速查找和有序数据的场景。

基于平衡二叉树（红黑树）

**定义和特性**

- **键值对**：map 存储的是键值对，其中每个键都是唯一的。
- **排序**：map 中的元素按照键的顺序自动排序，通常是升序。
- **唯一性**：每个键在 map 中只能出现一次。
- **双向迭代器**：map 提供了双向迭代器，可以向前和向后遍历元素。

**基本语法**

包含头文件:

```cpp
#include <map>
```

声明 map 容器:

```cpp
std::map<key_type, value_type> myMap;
```

- key_type 是键的类型。
- value_type 是值的类型。

插入元素:

```cpp
myMap[key] = value;
```

访问元素:

```cpp
value = myMap[key];
```

遍历 map:

```cpp
for (std::map<key_type, value_type>::iterator it = myMap.begin(); it != myMap.end(); ++it) {
  std::cout << it->first << " => " << it->second << std::endl;
}
```

## 相关内容
- [[计算机系/C++/16 STL 算法、函数对象与 Lambda|STL 算法、函数对象与 Lambda]]

---

## 学习导航
- 上一篇：[[计算机系/C++/14 STL 基础、容器与迭代器|STL 基础、容器与迭代器]]
- 返回目录：[[C++ 学习指南]]
- 下一篇：[[计算机系/C++/16 STL 算法、函数对象与 Lambda|STL 算法、函数对象与 Lambda]]