%%
# 纲要
> 主干纲要、Hint/线索/路标
# Q&A
#### 已明确
#### 待明确
> 当下仍存有的疑惑
**❓<font color="#c0504d"> 有什么问题？</font>**
# Buffer
## 闪念
> sudden idea
## 候选资料
> Read it later
%%
# C++中的数组
C++中的数组分为两种：
- **静态数组**：
- **静态数组**本身是一种**对象**，其**类型**为 C++类型系统中的 **"==数组类型=="（array type）**。
- 因此，也允许定义 **==指向数组的指针==以及==数组的引用==**。
- **静态数组的大小（及内存分配）==在编译时==确定**，存储在**程序的栈上（局部静态数组）** 或者**在全局/静态存储区（全局静态数组）**
- **动态数组**：
- **动态数组==通过指针实现==，其大小==在运行时==确定，通过 `new` 关键字为其动态分配内存**。
- 动态数组 **通过"指针"** 来进行指代，**没有数组名**。
> [!caution] 数组不支持直接拷贝和赋值。
>
> **(静态) 数组不支持拷贝和赋值**。**不能用一个数组直接对另一个数组初始化或赋值**，只能：
>
> - **通过循环逐个元素复制**；
> - 或者**使用标准库提供的 `std::copy` 函数**。
>
> 当数组作为**函数形参**时，发生的不是**数组的拷贝**，而是**数组名被隐式转换为 "==指向其首元素的指针==**"，这个**指针被传递给函数**。
> 因此，实际上**传递的是==数组首元素的地址==**，而非整个数组的拷贝。
> [!tip] 理解 "**数组**" 声明的含义，最好是从 "**数组名字**" 开始**由内到外的顺序阅读**。[^1]（P103）
>
> ```cpp
> T *pd[3] // an array of 3 pointers. 类型为`T*[3]`.
> T (*pd)[3] // a pointer to an array of 3 `T` elements. 类型为`T (*)[3]`.
> T *(*pd)[3] // a pointer to an array of 3 `T*` pointers. 类型为`T *(*)[3]`.
> ```
<br><br>
# 静态数组
## 静态数组的类型
**静态数组**的类型 (type) 为 C++类型系统中的 **"==数组类型=="（array type）**，属于复合类型。
> [!important] 静态数组的大小属于 "==数组类型==" 的一部分，因此必须在编译时已知，即数组大小必须是一个 "==常量表达式=="。
- 对于静态数组 `int arr[5];`，其类型为 `int [5]`;
- 对于二维静态数组 `int arr[3][7];`，其类型为 `int [3][7]`。
```cpp title:array_type.cpp
int arr[5];
assert(typeid(arr) == typeid(int[5]));
int arr_2d[3][7];
assert(typeid(arr_2d) == typeid(int[][7]));
```
因此，可以定义 "**指向数组类型的指针**" 或 "**数组的引用**"。
<br>
## 静态数组的大小
C++标准中**不支持 "变长静态数组"**，最早于 C++98、C++03 标准中规定 **==静态数组的大小==** 必须是一个 **==编译时常量==**。
> [!caution] **==gcc/g++ 编译器==**支持在 **C++中使用变长静态数组**，但这**==仅属于编译器自身的扩展==**，而非 C++标准的一部分。
> [!NOTE]
>
> C99 标准中引入了**变长数组**（Variable Length Arrays, VLAs），但其并不是 C++标准的一部分，**标准 C++ 不支持变长静态数组**。
>
> 为支持变长静态数组，编译器需要在函数栈上产生 "**==变长栈帧==**"（从而实现**在栈上存储变长静态数组**）。
> 变长栈帧依赖于使用 **`%rbp` 寄存器**作为**帧指针**。
>
<br>
## 静态数组的数组名
> 动态数组在动态时创建，只能由指针所指代，没有数组名。
**静态数组的数组名**实际上是 **==数组首元素的地址==的一个常量表示**。
静态数组的数组名用在==**绝大多数==表达式中**会被**隐式转换**为 **"==指向数组首元素的指针=="**：
- 其 "**值**" 为 **==数组中首项元素的地址==** ；
- **指针类型**为 "**==指向静态数组内元素类型的指针==**" 。
该指针**存储了==数组首元素的地址==**，通过**指针算术操作**，**可以访问数组中的不同元素**。
**下标访问符 `array[idx]`** 即是基于 **"静态数组名" 所对应的==首项元素的地址**== 及其**指针类型**（**==指向数组元素的指针类型==**）来**计算地址偏移量**，从而进行访问。
```cpp title:array_name_as_pointer.cpp
int arr[5] = {1, 2, 3, 4, 5};
int* p = arr;
for (int i = 0; i < 5; ++i) {
cout << *(p + i) << ' '; // 等价于下标访问符`arr[i]` 以及`p[i]`.
}
// 使用方括号"数组表示法"等同于"间址运算符": p[i] 被解释为 *(p+i)
int *pt = new int[10];
*pt = 5;
pt[0] = 6; // 等同于*pt
pt[9] = 44; // 等同于*(pt + 9)
int coast[10];
*(coast + 4) = 12; // 等同于coast[4]
```
> [!caution] 数组名使用的例外情况
>
> - 用于 `sizeof` 时，将返回整个数组的长度（**单位为字节，而非元素数量**）；
> - 用于 `decltype`、`typeid` 时，取得 "**数组类型**"，例如 `int [3]`。（而数组名用于 `auto` 时，得到的仍是**指向数组元素的指针类型**）
> - 用于取址运算符 `&` 时，取得 "**指向==数组类型==的指针**"，虽然**指针所指的地址仍然是数组内首个元素的地址**。
> - 用作字符串字面量，初始化字符数组时。
#### 数组名的隐式类型转换
```cpp title:array_name_use_example.cpp
const int N = 3, M = 4;
int A[N];
int B[N][M];
// 数组名是"指向数组元素类型的指针", 该指针指向数组内首个元素.
int* Aptr = A; // 数组A中的元素类型是int.
int (*Bptr) [M] = B; // 二维数组B本质是嵌套数组, B中元素是`int [M]`类型
// 对数组取地址得到 "指向数组类型的"指针
int (*Aptr2) [N] = &A;
int (*Bptr2) [N][M] = &B;
// 对比
int (*Bptr3) [M] = B; // `B`是二维数组, 数组名隐式转为"指向数组首元素(大小为M的一维数组)的指针"
int* Bptr4 = B[0]; // `B[0]`是一维数组, 数组名隐式转为"指向数组首元素(int)的指针"
int* Bptr5 = &B[0][0]; // `&B[0][0]`是指向数组元素的指针
cout << A << ' ' << A + 1 << endl; // `A`隐式转为"指向数组首元素的指针", 算术运算时步长为数组元素大小
cout << &A << ' ' << (&A) + 1 << endl; // `&A`为"指向数组类型的指针", 算术运算时步长为整个数组大小
static_assert(std::is_same<decltype(A), int [3]>::value);
// 上面的一个可能的输出:
// 0x2f21bffde4 0x2f21bffde8
// 0x2f21bffde4 0x2f21bffdf0~
```
<br>
## 静态数组的别名
注意 **`typedef` 声明** 静态数组别名时，**数组大小放在最后**：
```cpp
typedef int int_array[4]; // `int_array` 是 `int[4]`类型的别名
int_array a; // a是一个含有4个int元素的数组类型
// 等价声明:
using int_array = int[4];
```
<br>
## 静态数组的初始化
```cpp
int array[10]{}; // 值初始化, 全0.
int array[10] = {}; // 值初始化, 全0.
int array[10] = {1, 2, 3}; // 除指定值外, 剩余元素值初始化, 全0;
int array[] = { 1, 2, 3, 4}; // 数组大小自动推断为4.
```
**静态数组大小可以省略**，由编译器根据 "**初始化列表**" 中元素数量进行推断。
```cpp
struct Foo {
static int Array[]; // 静态成员变量, 类中仅是声明而未定义, 故可省略数组大小.
};
// 类外对静态数据成员进行定义, 此处由编译器根据初始化列表推断数组大小.
int Foo::Array[] = { 1, 2, 3, 4, 5};
```
<br>
## 指向静态数组的指针
通常 "**指向==数组==的指针**" 实际指的是 "**指向==数组内首项元素==的指针**" ，**通过该指针能够访问数组中元素**。
（数组名即是被隐式转换为这一类型的指针）
而 "**指向==整个数组==的指针**" 也即 "**指向==静态数组类型==的指针** "，所指向的是 "**==数组类型==**"，
例如， `int (*p)[5]`：指向 "**包含 5 个 `int` 元素的数组类型**"的指针
区别说明：
```cpp title:pointer_to_array_type.cpp
// 一维数组
int arr[5];
int* p1 = arr; // `arr`隐式转为"指向数组首元素的指针"
int (*pt_arr)[5] = &arr; // `&arr`为"指向数组类型的指针".
// 对二维数组
int arr_2d[3][4];
int (*p2)[4] = arr_2d; // `arr_2d`为二维数组名, 隐式转为"指向数组首元素(大小为4的一维数组)的指针"
int* p3 = arr_2d[0]; // `arr_2d[0]`为一维数组名, 隐式转为"指向数组首元素(int)的指针"
int (*pt_arr_2d)[3][4] = &arr_2d; // `&arr_2d`为"指向数组类型的指针".
```
## 静态数组的引用
```cpp title:reference_of_array
// 对一维数组类型的引用
int arr[5] = {1, 2, 3, 4, 5};
int (&ref)[5] = arr; // 对"包含5个int元素的数组类型"的引用
// 对二维数组类型的引用
int arr_2d[3][4];
int (&ref_2d)[3][4] = arr_2d; // 对"包含3个含有4个int元素的数组类型"的引用
```
<br>
## 静态数组作为函数形参
C++中不允许拷贝数组。当**数组名**被用作**形参**时，会自动发生从"**数组**"到"**指向数组首元素的指针**"的 **==隐式类型转换==**。
因此，当函数需要接收一个数组时，需要以 "**指向==数组内元素类型==的指针**" 作为形参。
在函数形参中，可以**用 `[]` 来代替 `*` 标识指针**，例如 `int []` 等价于 `int*`，可更清晰地**标识该形参为 "==数组形参=="**。
示例：
- `void fun(int []);` 等价于 `void func(int*);`
- 形参类型为"**指向 int 型元素的指针**"，可接受**一维静态数组名作为实参**。
- `void func(int [][4]);` 等价于 `void func(int (*)[4]);`
- 形参类型为 "**指向包含 4 个 int 型元素的数组的指针**"，可接受**二维数组名作为实参**。
> [!caution] 函数形参中使用 `[]` 代替 `*` 时，其形参类型是 "**指向元素类型的指针**"，故与"**数组大小**"无关，**不声明数组大小（==声明了也没有任何实际作用==）**
>
> 但是，对于**多维数组**来说，**==数组第二维及其后所有维度的大小==** 都是 **内层的==数组类型的一部分==**，因而不能省略。
> 例如 `void func(int arr[][4]);` ，其中 `int arr[][4]` 即可接受一个二维数组，**第二维是 size 为 4 的数组**。
示例：下列三种形式的形参等价，可接受数组实参：
```cpp
// 下面三种形参等价, 形参都是`const int*`类型
void func(const int*);
void func(const int []); // `[]`在函数形参中即表示指针类型
void func(const int [10]); // 这里的`10`并不限定实际数组元素, 只是表达形参的期望值, 因此完全可省略, 同上一句.
```
示例：下列三种形式的形参等价，可接受二维数组实参，其中第二维 size 固定。
```cpp
// 对于二维数组, 下面三种形参等价, 形参都是`int (*)[4]`类型
void func21(int (*arr)[4]) {} //
void func22(int arr[][4]) {} //
void func23(int arr[10][4]) {} // 第一维度10可省略, 没有任何实际作用.
```
使用示例：
```cpp
template<typename T, int dim>
class Point {
public:
Point();
Point(T coords[]) {
for (int i = 0; i < dim; ++i) {
_coords[i] = coords[i];
}
}
Point(T (*coords)[dim]) { // 形参是"指向具有dim个T类型元素的数组的指针"
for (int i = 0; i < dim; ++i) {
_coords[i] = (*coords)[i]; // 先对指针解引用, 然后再取下标, 否则下标偏移是dim*sizeof(T)字节.
}
}
Point(std::initializer_list<T> list) {
assert(list.size() >= dim);
for (int i = 0; i < dim; ++i) {
_coords[i] = *(list.begin() + i);
}
}
T& operator[](int idx) {
return const_cast<T&>(static_cast<const Point&>(*this)[idx]);
}
const T& operator[](int idx) const {
assert(idx >= 0 && idx < dim);
return _coords[idx];
}
private:
T _coords[dim];
};
template<typename T, int dim>
inline std::ostream& operator<<(std::ostream& os, Point<T, dim>& pt) {
os << "(";
for (int i = 0; i < dim - 1; ++i) {
os << pt[i] << ", ";
}
os << pt[dim - 1] << ")";
return os;
}
int main() {
double array[3] { 0.15, 3.42, 1.27 };
Point<double, 1> pt1(array);
Point<double, 2> pt2({2.14, 1.72});
Point<double, 3> pt3(&array);
cout << pt1 << endl;
cout << pt2 << endl;
cout << pt3 << endl;
}
```
<br>
### 静态数组引用形参
C++允许将变量定义为**数组的引用**，因此**形参也可以是数组的引用**，但必须 **==明确地指定数组大小==**，且 **==要求实参数组大小匹配==**。
```cpp
void func(int (&arr)[10]); // arr是对一个"含有10个int元素的数组"的引用
int arr[5] = {1, 2, 3, 4, 5};
int (&ref)[5] = arr;
int *(&arr2)[5]; // `arr2`是对一个"含有10个int*元素的指针数组"的引用
```
<br><br>
## 指向静态数组的指针或引用作为函数返回类型
函数形式：
- **返回指向静态数组的指针**的函数：`Type (*function(param_list)) [dimension]`
- **返回静态数组引用**的函数：`Type (&function(param_list)) [dimension]`
其中，`(*function(param_list))` 两端括号必须有存在，`[dimension]` 指定数组维度。
必须在 **==被定义的函数名==** 及其 ==**形参列==表之后**声明**数组的维度**。
推进改写为**尾置返回类型**，会更清晰明了，例如：
```cpp
int (*func(int i)) [10]; // 函数返回一个指向包含10个int元素的静态数组的指针
int (&func(int i)) [10]; // 函数返回一个指向包含10个int元素的静态数组的引用
//
auto func(int i) -> int(*)[10];
auto func(int i) -> int(&)[10];
```
<br><br>
## 静态数组遍历
对于静态数组，可以由以下几种方式进行遍历。
其中，"方式三" 和 "方式四" 即**基于两个指针进行遍历**，而方式二和方式四则 **==无需明确知道数组大小==**。
```cpp title:traverse_array.cpp
// 遍历一维数组
void traverse_array() {
int arr[5] = {1, 2, 3, 4, 5};
// 方式一: 根据数组大小明确指定循环访问的次数
for (int i = 0; i < 5; ++i) {
cout << arr[i] << ' ';
}
cout << endl;
// 方式二: 使用范围for循环
for (int& elem : arr) {
cout << elem << ' ';
}
cout << endl;
// 方式三: 使用指针遍历
int* p_begin = arr; // 指向数组首元素的指针
int* p_end = &arr[5]; // 或 = arr + 5; 尾后指针, 指向数组尾元素之后的内存地址
for (; p_begin != p_end; ++p_begin) {
cout << *p_begin << ' ';
}
cout << endl;
// 方式四: 使用标准库函数begin()和end()
// 定义于头文件<iterator>中, 用于返回指向数组首元素和尾元素之后的指针
for (int* p = begin(arr); p != end(arr); ++p) {
cout << *p << ' ';
}
cout << endl;
}
```
```cpp title:traverse_multi_dim_array.cpp
// 遍历多维数组
void traverse_multi_dim_array() {
constexpr size_t rowCnt = 3, colCnt = 4;
int array[rowCnt][colCnt] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
// 方式一: 下标访问
for (int i = 0; i < rowCnt; ++i) {
for (int j = 0; j < colCnt; ++j) {
cout << array[i][j] << " ";
}
cout << endl;
}
cout << endl;
// 方式二: 使用范围for循环
for (auto& row : array) { // 外层循环变量必须要声明为引用类型, 从而推导为int(&)[4]; 否则row会被解释为指针int*, 内层col会报错.
for (auto col : row) {
cout << col << " ";
}
cout << endl;
}
cout << endl;
// 方式三: 使用指针遍历(利用begin和end()获取指针
for (auto p = begin(array); p != end(array); ++p) { // p是int(*)[colCnt] 类型的指针.
for (auto q = begin(*p); q != end(*p); ++q) { // q是int*类型的指针.
cout << *q << " ";
}
cout << endl;
}
cout << endl;
}
```
> [!NOTE] 使用范围 `for` 循环处理多维数组时，除了最内层的循环外，其他所有循环的控制变量都应声明为引用类型
>
> > 参见 [^1] （P114）
> ```cpp
> constexpr size_t rowCnt = 3, colCnt = 4;
> int array[rowCnt][colCnt];
> for (auto& row: array) { // 外层的循环变量row必须声明为引用, 否则内层循环被自动转换为指针类型, 而无法遍历
> for (auto col : row) {
> cout << col << " ";
> }
> cout << endl;
> }
> ```
>
> [!NOTE] C++11 标准库提供了 `begin` 和 `end` 两个函数
>
> 类似于 STL 容器的成员函数，为静态数组提供了获取 **==指向首项元素的指针==** 以及 **==尾后指针==** 的功能。
> 其中，**==尾后指针==指向静态数组的==尾元素的后一内存地址==（而不是尾元素）**。
>
> [!example] 示例：利用指针遍历二维静态数组，修改对角线元素的值
>
> ```cpp
> const int N = 16;
> void fix_set_diag(int A[N][N], int val) {
> int* Aptr = A[0]; // 等价于&A[0][0].
> int* Aend = &A[N][N]; // 作为边界的地址, 无效但实际不会访问, 因此不用担心越界访问错误.
> while (Aptr != Aend) {
> *Aptr = val;
> Aptr += N + 1;
> }
> }
> ```
>
#### 在函数中遍历形参数组的几种方式
![[_attachment/02-开发笔记/01-cpp/类型相关/cpp-数组相关.assets/IMG-cpp-数组相关-3F314B557802F87EE1ACD69F3B6209F2.png|550]]
![[_attachment/02-开发笔记/01-cpp/类型相关/cpp-数组相关.assets/IMG-cpp-数组相关-94800FA5374644E9A3072E6E094FCD37.png|550]]
![[_attachment/02-开发笔记/01-cpp/类型相关/cpp-数组相关.assets/IMG-cpp-数组相关-9226D6DD32908683B6671D983281F57D.png|550]]
<br><br><br>
## 多维静态数组
C++中并没有真正的多维数组，所谓多维数组其实是**嵌套数组**——**数组的数组**。
对于多维数组，**一个维度表示数组本身大小**，**后一个维度表示其==元素（也是数组）的大小==**，以此类推，**从紧跟数组名的第一维度开始逐步解析**。
以 `int arr[3][4][5]` 为例：`arr` 是一个大小为 3 的数组，其每个元素都是大小为 4 的数组，这些数组的元素又是含有 5个 `int` 元素的数组。
```cpp
// 示例一: 二维嵌套数组
int A[5][3];
// 等价于下述声明:
typedef int row3_t [3];
row3_t A[5];
// 示例二: 三维嵌套数组
int A[3][4][5];
// 等价于下述声明
typedef int row3_t [3];
typedef row3_t row4_3_t [4];
row4_3_t A[5];
```
<br><br>
#### 多维静态数组的内存空间布局
在这种**嵌套声明**方式下，**数组元素**在**内存**中将按照 "**行优先的顺序排列**"：
![[_attachment/02-开发笔记/01-cpp/类型相关/cpp-数组相关.assets/IMG-cpp-数组相关-9A9ADF6818FFABF6E4B9B123840FE63C.png|399]]
> [!example]
> ![[Excalidraw/Excalidraw-Solution/数组相关.excalidraw#^group=ti13Fcwj|402]]
<br><br><br>
# 动态数组
> [!NOTE] **动态数组是通过指针动态创建的，因此其类型并非 C++类型系统中的 "arrary type"，==而就是指针类型==**。
对于动态数组，其每一个维度下的数组都由**一个指针**来表示。因此：
```cpp title:dynamic_array.cpp
// 申请一维动态数组
int *p = new int[10];
// 释放一维动态数组
delete[] p;
// 申请二维动态数组: 一个[5][3]的二维动态数组.
// p2是指向指针的指针, 即"指向int*类型的指针", 用其指向一个指针数组.
int **p2 = new int*[5]; // 申请行指针: 创建一个长度为5的指针数组.
for (int i = 0; i < 5; ++i) {
p2[i] = new int[3]; // 申请每一行的空间: 对指针数组里的每个指针, 都动态申请一个长度为10的一维数组.
}
// 释放二维动态数组
for (int i = 0; i < 5; ++i) {
delete[] p2[i]; // 释放每一行的空间
}
delete[] p2; // 释放行指针
```
<br><br><br>
# 字符数组
字符数组相较于其他数组具有一些特殊性质[^1]（P102）。
> [!NOTE] 任何可使用 "字符串字面量" 的地方，均可由使用 "以 `\0` 结尾的字符数组"。
>
> 例如： 可用于 `cout <<` 中； 可用字符数组初始化 `std::string` 对象或为其赋值。
> [!caution] 字符数组中必须存在空字符 `\0` 作为结尾字符
>
> 对于一个合法的**字符数组**，在其**数组范围内==必须==要确保有一个==空字符== `\0` 作为==结尾字符==**，标志着 **==字符串的结束==**。
>
> 对于 `std::cout`、`strlen()`、`strcpy()` 等字符串操作而言，**空字符 `\0` 是必须的**，这些操作**根据该空字符来确定字符串的结束位置**。
<br>
## 字符数组初始化
几种初始化方式：
- 直接使用 "**==字符串字面量==**" 对字符数组进行**初始化**，**编译器会==自动在末尾加上空字符== `\0`**。
- 使用**花括号初始化列表**包裹一个 "**字符串字面量**"，效果同上；
- 使用**花括号初始化列表**包裹一个 "**字符列表**"时，**==必须手动添加空字符== `\0` 作为终止字符**。
```cpp title:init_char_array.cpp
// 直接使用"字符串字面量" 对字符数组进行初始化，编译器会自动在末尾加上空字符`\0`。
char str[] = "Hello"; // 实际分配了6个字符的空间，包括末尾的'\0'
char str2[] = {"Hello"}; // 同上
// 以"字符"列表的形式初始化字符数组时, 必须手动添加'\0'结束符
char str3[] = {'H', 'e', 'l', 'l', 'o', '\0'};
```
对字符数组初始化之后，==**不允许==直接将另一个字符串字面量**赋值给字符数组，**需要使用字符串拷贝函数 `strcpy`**。
> [!NOTE]
> - **可以**用 "**字符串字面量**" **==初始化==** 字符数组
> - **不能**将 "**字符串字面量**" **==赋值==** 给字符数组
<br>
## 字符数组的数组名
在大多数 C++表达式中, **`char` 数组名、`char` 指针、字符串字面量** 都被解释为 **==字符串中第一个字符的地址==**。
但是，在 `std::cout` 中，上述三者都会被输出为 "**==字符串内容==**"。
如果要输出 **`char` 数组 / `char` 指针所指的地址**（即第一个字符的地址），需要：
- **将==数组名/指针==进行==显式类型转换==**，可转换为 `void*` 指针类型，从而实现。
- 或者，对于**字符数组**，可用 **`&` 直接取其地址**。
```cpp title:cout_the_address_of_char.cpp
char char_arr[] = "Hello";
const char* p = "World";
cout << char_arr << '\t' <<(void*)char_arr<< endl;
cout << char_arr << '\t' << &char_arr<< endl; // 与上等效
cout << p << '\t' << (void*)p <<endl;
```
<br>
## 字符数组操作
**字符数组**、**指向字符串的 `char` 指针**支持一系列相同的字符串相关操作。
参见 [[02-开发笔记/02-c/c-字符串处理|c-字符串处理]]
![[_attachment/02-开发笔记/01-cpp/类型相关/cpp-数组相关.assets/IMG-cpp-数组相关-EA0CEE44FD7755F64DE5317C44BEECEE.png|650]]
![[_attachment/02-开发笔记/01-cpp/类型相关/cpp-数组相关.assets/IMG-cpp-数组相关-29A990EF72CB4C5A8E3A1C2547D98F70.png|660]]
<br><br>
# 参考资料
# Footnotes
[^1]: 《C++ Primer》