# C++ 一维与二维数组：内存模型、初始化、高效遍历与算法技巧

数组（Array）是 C++ 中最基础的**线性数据结构**。深入理解数组在内存中的物理排布、初始化机制与缓存特性，是写出高性能代码与攻克复杂算法题的前提。

---

## 目录
1. [一、一维数组核心详解](#一一一维数组核心详解)
   - [1. 内存模型与底层特性](#1-内存模型与底层特性)
   - [2. 初始化方式与常见误区](#2-初始化方式与常见误区)
   - [3. 三种主流遍历姿势](#3-三种主流遍历姿势)
   - [4. 高频处理技巧（逆序、极值、前缀和）](#4-高频处理技巧)
2. [二、二维数组核心详解](#二二二维数组核心详解)
   - [1. 内存模型：行优先存储与一维映射](#1-内存模型行优先存储与一维映射)
   - [2. 初始化方式与省略规则](#2-初始化方式与省略规则)
   - [3. 遍历机制与 CPU 缓存行命中优化](#3-遍历机制与-cpu-缓存行命中优化)
   - [4. 矩阵核心处理技巧（对角线、方向数组）](#4-矩阵核心处理技巧)
3. [三、工程与竞赛级避坑指南](#三三工程与竞赛级避坑指南)
   - [1. 栈溢出（Stack Overflow）与开大数组姿势](#1-栈溢出-stack-overflow-与开大数组姿势)
   - [2. 数组传参退化机制（Decay）](#2-数组传参退化机制decay)
   - [3. `memset` 的底层字节级原理与陷阱](#3-memset-的底层字节级原理与陷阱)
4. [四、总结速查表](#四四总结速查表)

---

## 一、一维数组核心详解

### 1. 内存模型与底层特性
一维数组在内存中占据一段**连续的内存空间**，数组名即代表该连续空间的首地址。

```text
地址增长方向 ---> 
[ arr[0] ] [ arr[1] ] [ arr[2] ] [ arr[3] ] [ arr[4] ]
0x1000     0x1004     0x1008     0x100C     0x1010   (以 sizeof(int) = 4 字节为例)
```
- **寻址公式**：$\text{Address}(arr[i]) = \text{BaseAddress} + i \times \text{sizeof(Type)}$
- **时间复杂度**：依靠寻址公式，通过下标访问元素的时间复杂度为 **$O(1)$**。

---

### 2. 初始化方式与常见误区

```cpp
#include <iostream>
#include <algorithm> // for std::fill

int globalArr[5]; // 全局数组：未显式初始化时，默认全清为 0

int main() {
    // 1. 局部未初始化：内部是随机垃圾值（危险！）
    int a[5];

// 2. 列表初始化：完全显式赋值
    int b[5] = {1, 2, 3, 4, 5};

// 3. 部分初始化：剩余未指定的元素自动补 0（最常用的清零方式）
    int c[5] = {0}; // 全部为 0
    int d[5] = {1}; // d[0]=1, d[1]~d[4] 全是 0（注意：不是全部为 1！）

// 4. C++11 统一列表初始化（可省略等号）
    int e[]{10, 20, 30}; // 自动根据元素个数推导长度为 3

// 5. 将整个数组填充为任意特定值（非 0）
    int f[5];
    std::fill(f, f + 5, -1); // f 变为 {-1, -1, -1, -1, -1}

return 0;
}
```

---

### 3. 三种主流遍历姿势

```cpp
#include <iostream>

int main() {
    int arr[5] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]); // 获取数组长度

// 姿势 1: 下标索引遍历（最直观，支持读写与位置感知）
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }

// 姿势 2: 指针迭代遍历
    for (int *p = arr; p < arr + n; ++p) {
        std::cout << *p << " ";
    }

// 姿势 3: C++11 基于范围的 for 循环（Range-based for）
    for (const auto &val : arr) { // 加 const & 避免拷贝开销并防止误修改
        std::cout << val << " ";
    }

return 0;
}
```

---

### 4. 高频处理技巧

#### ① 双指针原地逆序（Reverse）
```cpp
void reverseArray(int arr[], int n) {
    int left = 0, right = n - 1;
    while (left < right) {
        std::swap(arr[left], arr[right]);
        left++;
        right--;
    }
}
```

#### ② 一维前缀和（Prefix Sum，将区间求和降至 $O(1)$）
```cpp
// 原数组 a 下标从 1 开始，构建前缀和数组 prefix
// prefix[i] = a[1] + a[2] + ... + a[i]
// 快速求区间 [L, R] 之和：prefix[R] - prefix[L - 1]
const int N = 1005;
int a[N], prefix[N];

void buildPrefixSum(int n) {
    for (int i = 1; i <= n; ++i) {
        prefix[i] = prefix[i - 1] + a[i];
    }
}
```

---

## 二、二维数组核心详解

### 1. 内存模型：行优先存储与一维映射
在 C++ 中，**二维数组在物理内存上本质上仍然是一维连续空间**。采用 **行优先（Row-Major）** 排布：存完第一行，紧跟着存第二行。

```text
声明：int grid[2][3]; (2 行 3 列)
逻辑结构:
[ (0,0), (0,1), (0,2) ]
[ (1,0), (1,1), (1,2) ]

> 📌 **二维降一维核心映射公式**（设总列数为 $M$）：
> $$\text{二维坐标 } (i, j) \iff \text{一维索引 } i \times M + j$$

---

### 2. 初始化方式与省略规则

```cpp
// 1. 分行显式初始化（推荐，代码可读性极高）
int mat1[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};

// 2. 扁平连续初始化（根据列数自动按行填满）
int mat2[2][3] = {1, 2, 3, 4, 5, 6};

// 3. 全清零
int mat3[2][3] = {{0}};

// 4. 省略第一维大小（行数可根据初始值自动推导，但【列数绝对不能省】）
int mat4[][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
}; // 编译器自动推导出为 3 行
```

---

### 3. 遍历机制与 CPU 缓存行命中优化

在遍历二维数组时，**外层循环遍历行、内层循环遍历列（行优先）** 与 **外层列、内层行（列优先）** 在性能上有数倍的差距。

```cpp
const int ROWS = 2000, COLS = 2000;
int grid[ROWS][COLS];

// ✅ 【极致性能】行优先遍历（顺应内存连续地址，命中 CPU Cache Line）
for (int i = 0; i < ROWS; ++i) {
    for (int j = 0; j < COLS; ++j) {
        grid[i][j] = 1;
    }
}

// ❌ 【性能极差】列优先遍历（跳跃式跨步长访问，产生大量 Cache Miss）
for (int j = 0; j < COLS; ++j) {
    for (int i = 0; i < ROWS; ++i) {
        grid[i][j] = 1;
    }
}
```

---

### 4. 矩阵核心处理技巧

#### ① 主副对角线遍历（$N \times N$ 方阵）
*   **主对角线**（左上到右下）：行索引与列索引相等 $\rightarrow i == j$。
*   **副对角线**（右上到左下）：行索引与列索引之和恒定 $\rightarrow i + j == N - 1$。

#### ② 坐标偏移量与“方向数组”（网格图遍历必备）
在走迷宫、BFS/DFS、棋盘类搜索中，使用方向数组替代冗长的 `if-else`。

```cpp
#include <iostream>

// 上、右、下、左 四个方向的偏移量 (dx: 行变化, dy: 列变化)
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

void explore(int x, int y, int n, int m) {
    for (int dir = 0; dir < 4; ++dir) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

// 边界检查：防止数组越界引发段错误 (Segmentation Fault)
        if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
            std::cout << "合法邻居坐标: (" << nx << ", " << ny << ")\n";
        }
    }
}
```

---

## 三、工程与竞赛级避坑指南

### 1. 栈溢出（Stack Overflow）与开大数组姿势

*   **问题**：函数内部声明的局部变量分配在**栈区（Stack）**，默认栈大小通常只有几 MB（Linux 默认约 8MB，Windows MSVC 默认约 1MB）。
    ```cpp
    int main() {
        int a[1000000]; // ❌ 10^6 * 4B ≈ 4MB，直接栈溢出崩溃！
    }
    ```
*   **正确开大数组姿势**：
    1.  **开在全局变量区（BSS 段，推荐算法竞赛使用）**：
        ```cpp
        const int MAXN = 1000005;
        int a[MAXN]; // ✅ 全局空间可达几百 MB，且自动初始化为 0
        int main() { ... }
        ```
    2.  **使用 `std::vector`（动态在堆区 Heap 分配）**：
        ```cpp
        std::vector<int> a(1000000, 0); // ✅ 堆空间充裕
        ```

---

### 2. 数组传参退化机制（Decay）

当把数组作为参数传递给函数时，数组名会**退化为指针**。因此：
1. 在函数内部使用 `sizeof(arr)` 将得到指针的大小（4 或 8 字节），**无法再获取数组真实长度**！必须额外传递数组长度 $N$。
2. 二维数组传参时，**第二维（列宽）必须写明**，否则编译器无法计算寻址偏移。

```cpp
// 一维数组传参（以下三种写法完全等价）
void print1D(int arr[], int n) { /* ... */ }
void print1D(int *arr, int n)  { /* ... */ }

// 二维数组传参：必须指定列数 COLS
const int COLS = 100;
void print2D(int grid[][COLS], int rows) {
    // 编译器依靠 COLS 进行寻址：grid[i][j] = *(grid + i * COLS + j)
}
```

---

### 3. `memset` 的底层字节级原理与陷阱

`memset(arr, val, sizeof(arr))` 来自 `<cstring>`，是按**单字节（Byte）**填充内存的。

*   **有效填充值**：
    - `0`：每个字节都是 `0x00` $\rightarrow$ 整数结果为 **`0`**（安全）。
    - `-1`：每个字节都是 `0xFF` $\rightarrow$ 补码结果为 **`-1`**（安全）。
    - `0x3f`：每个字节填充 `0x3F` $\rightarrow$ `int` 变为 `0x3f3f3f3f`（约 $1.06 \times 10^9$，常作为图论算法中无穷大 `INF`，相加不会溢出 `int`）。
*   ❌ **经典错误**：
    ```cpp
    int a[5];
    memset(a, 1, sizeof(a)); 
    // 每个字节变成 0x01，拼成 4 字节 int 为 0x01010101 = 16843009，而不是 1！
    ```
    > 若需将数组全部赋值为 `1` 或其他非 0/-1 数值，请使用 **`std::fill`**。

---

## 四、总结速查表

| 操作需求 | 推荐实现方式 | 核心注意事项 |
| :--- | :--- | :--- |
| **数组全清零** | 声明时 `int a[N] = {0};` 或 `memset(a, 0, sizeof(a));` | 局部变量必须显式清零，全局变量默认已为 0 |
| **填充特定非零值** | `std::fill(a, a + n, target_val);` | 切勿用 `memset` 填 `1`，会产生字节拼凑错误 |
| **申请超大数组** | 声明为全局变量，或使用 `std::vector<int>` | 局部数组严禁超过 $10^5$ 量级，否则引发栈溢出 |
| **二维矩阵遍历** | 恒定采用 **外层行、内层列** 顺次访问 | 保持空间局部性，极大提高 CPU 缓存命中率 |
| **网格图多向移动** | 定义 `dx[] = {-1,0,1,0}; dy[] = {0,1,0,-1};` | 移动后必须做 `nx >= 0 && nx < N` 边界检查 |
| **函数传递数组** | `void func(int arr[], int n)` 显式带上长度 | 数组传参会退化为首地址指针，丢失大小信息 |

C++ 一维与二维数组：内存模型、初始化、高效遍历与算法技巧

数组（Array）是 C++ 中最基础的线性数据结构。深入理解数组在内存中的物理排布、初始化机制与缓存特性，是写出高性能代码与攻克复杂算法题的前提。

一、一维数组核心详解
1. 内存模型与底层特性
2. 初始化方式与常见误区
3. 三种主流遍历姿势
4. 高频处理技巧（逆序、极值、前缀和）
二、二维数组核心详解
1. 内存模型：行优先存储与一维映射
2. 初始化方式与省略规则
3. 遍历机制与 CPU 缓存行命中优化
4. 矩阵核心处理技巧（对角线、方向数组）
三、工程与竞赛级避坑指南
1. 栈溢出（Stack Overflow）与开大数组姿势
2. 数组传参退化机制（Decay）
3. memset 的底层字节级原理与陷阱
四、总结速查表

一、一维数组核心详解

1. 内存模型与底层特性

一维数组在内存中占据一段连续的内存空间，数组名即代表该连续空间的首地址。

地址增长方向 ---> 
[ arr[0] ] [ arr[1] ] [ arr[2] ] [ arr[3] ] [ arr[4] ]
0x1000     0x1004     0x1008     0x100C     0x1010   (以 sizeof(int) = 4 字节为例)

寻址公式：$\text{Address}(arr[i]) = \text{BaseAddress} + i \times \text{sizeof(Type)}$
时间复杂度：依靠寻址公式，通过下标访问元素的时间复杂度为 $O(1)$。

2. 初始化方式与常见误区

#include <iostream>
#include <algorithm> // for std::fill

int globalArr[5]; // 全局数组：未显式初始化时，默认全清为 0

int main() {
    // 1. 局部未初始化：内部是随机垃圾值（危险！）
    int a[5]; 

    // 2. 列表初始化：完全显式赋值
    int b[5] = {1, 2, 3, 4, 5};

    // 3. 部分初始化：剩余未指定的元素自动补 0（最常用的清零方式）
    int c[5] = {0}; // 全部为 0
    int d[5] = {1}; // d[0]=1, d[1]~d[4] 全是 0（注意：不是全部为 1！）

    // 4. C++11 统一列表初始化（可省略等号）
    int e[]{10, 20, 30}; // 自动根据元素个数推导长度为 3

    // 5. 将整个数组填充为任意特定值（非 0）
    int f[5];
    std::fill(f, f + 5, -1); // f 变为 {-1, -1, -1, -1, -1}

    return 0;
}

3. 三种主流遍历姿势

#include <iostream>

int main() {
    int arr[5] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]); // 获取数组长度

    // 姿势 1: 下标索引遍历（最直观，支持读写与位置感知）
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }

    // 姿势 2: 指针迭代遍历
    for (int *p = arr; p < arr + n; ++p) {
        std::cout << *p << " ";
    }

    // 姿势 3: C++11 基于范围的 for 循环（Range-based for）
    for (const auto &val : arr) { // 加 const & 避免拷贝开销并防止误修改
        std::cout << val << " ";
    }

    return 0;
}

4. 高频处理技巧

① 双指针原地逆序（Reverse）

void reverseArray(int arr[], int n) {
    int left = 0, right = n - 1;
    while (left < right) {
        std::swap(arr[left], arr[right]);
        left++;
        right--;
    }
}

② 一维前缀和（Prefix Sum，将区间求和降至 $O(1)$）

// 原数组 a 下标从 1 开始，构建前缀和数组 prefix
// prefix[i] = a[1] + a[2] + ... + a[i]
// 快速求区间 [L, R] 之和：prefix[R] - prefix[L - 1]
const int N = 1005;
int a[N], prefix[N];

void buildPrefixSum(int n) {
    for (int i = 1; i <= n; ++i) {
        prefix[i] = prefix[i - 1] + a[i];
    }
}

二、二维数组核心详解

1. 内存模型：行优先存储与一维映射

在 C++ 中，二维数组在物理内存上本质上仍然是一维连续空间。采用 行优先（Row-Major） 排布：存完第一行，紧跟着存第二行。

声明：int grid[2][3]; (2 行 3 列)
逻辑结构:
[ (0,0), (0,1), (0,2) ]
[ (1,0), (1,1), (1,2) ]

物理内存排布:
| grid[0][0] | grid[0][1] | grid[0][2] | grid[1][0] | grid[1][1] | grid[1][2] |

📌 二维降一维核心映射公式（设总列数为 $M$）： $$\text{二维坐标 } (i, j) \iff \text{一维索引 } i \times M + j$$

2. 初始化方式与省略规则

// 1. 分行显式初始化（推荐，代码可读性极高）
int mat1[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};

// 2. 扁平连续初始化（根据列数自动按行填满）
int mat2[2][3] = {1, 2, 3, 4, 5, 6};

// 3. 全清零
int mat3[2][3] = {{0}};

// 4. 省略第一维大小（行数可根据初始值自动推导，但【列数绝对不能省】）
int mat4[][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
}; // 编译器自动推导出为 3 行

3. 遍历机制与 CPU 缓存行命中优化

在遍历二维数组时，外层循环遍历行、内层循环遍历列（行优先） 与 外层列、内层行（列优先） 在性能上有数倍的差距。

const int ROWS = 2000, COLS = 2000;
int grid[ROWS][COLS];

// ✅ 【极致性能】行优先遍历（顺应内存连续地址，命中 CPU Cache Line）
for (int i = 0; i < ROWS; ++i) {
    for (int j = 0; j < COLS; ++j) {
        grid[i][j] = 1;
    }
}

// ❌ 【性能极差】列优先遍历（跳跃式跨步长访问，产生大量 Cache Miss）
for (int j = 0; j < COLS; ++j) {
    for (int i = 0; i < ROWS; ++i) {
        grid[i][j] = 1;
    }
}

4. 矩阵核心处理技巧

① 主副对角线遍历（$N \times N$ 方阵）

主对角线（左上到右下）：行索引与列索引相等 $\rightarrow i == j$。
副对角线（右上到左下）：行索引与列索引之和恒定 $\rightarrow i + j == N - 1$。

② 坐标偏移量与“方向数组”（网格图遍历必备）

在走迷宫、BFS/DFS、棋盘类搜索中，使用方向数组替代冗长的 if-else。

#include <iostream>

// 上、右、下、左 四个方向的偏移量 (dx: 行变化, dy: 列变化)
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

void explore(int x, int y, int n, int m) {
    for (int dir = 0; dir < 4; ++dir) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        // 边界检查：防止数组越界引发段错误 (Segmentation Fault)
        if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
            std::cout << "合法邻居坐标: (" << nx << ", " << ny << ")\n";
        }
    }
}

三、工程与竞赛级避坑指南

1. 栈溢出（Stack Overflow）与开大数组姿势

问题：函数内部声明的局部变量分配在栈区（Stack），默认栈大小通常只有几 MB（Linux 默认约 8MB，Windows MSVC 默认约 1MB）。 cpp int main() { int a[1000000]; // ❌ 10^6 * 4B ≈ 4MB，直接栈溢出崩溃！ }
正确开大数组姿势：
1. 开在全局变量区（BSS 段，推荐算法竞赛使用）： cpp const int MAXN = 1000005; int a[MAXN]; // ✅ 全局空间可达几百 MB，且自动初始化为 0 int main() { ... }
2. 使用 std::vector（动态在堆区 Heap 分配）： cpp std::vector<int> a(1000000, 0); // ✅ 堆空间充裕

2. 数组传参退化机制（Decay）

当把数组作为参数传递给函数时，数组名会退化为指针。因此： 1. 在函数内部使用 sizeof(arr) 将得到指针的大小（4 或 8 字节），无法再获取数组真实长度！必须额外传递数组长度 $N$。 2. 二维数组传参时，第二维（列宽）必须写明，否则编译器无法计算寻址偏移。

// 一维数组传参（以下三种写法完全等价）
void print1D(int arr[], int n) { /* ... */ }
void print1D(int *arr, int n)  { /* ... */ }

// 二维数组传参：必须指定列数 COLS
const int COLS = 100;
void print2D(int grid[][COLS], int rows) {
    // 编译器依靠 COLS 进行寻址：grid[i][j] = *(grid + i * COLS + j)
}

3. `memset` 的底层字节级原理与陷阱

memset(arr, val, sizeof(arr)) 来自 <cstring>，是按单字节（Byte）填充内存的。

有效填充值：
- 0：每个字节都是 0x00 $\rightarrow$ 整数结果为 0（安全）。
- -1：每个字节都是 0xFF $\rightarrow$ 补码结果为 -1（安全）。
- 0x3f：每个字节填充 0x3F $\rightarrow$ int 变为 0x3f3f3f3f（约 $1.06 \times 10^9$，常作为图论算法中无穷大 INF，相加不会溢出 int）。
❌ 经典错误： cpp int a[5]; memset(a, 1, sizeof(a)); // 每个字节变成 0x01，拼成 4 字节 int 为 0x01010101 = 16843009，而不是 1！ > 若需将数组全部赋值为 1 或其他非 0/-1 数值，请使用 std::fill。

四、总结速查表

操作需求	推荐实现方式	核心注意事项
数组全清零	声明时 `int a[N] = {0};` 或 `memset(a, 0, sizeof(a));`	局部变量必须显式清零，全局变量默认已为 0
填充特定非零值	`std::fill(a, a + n, target_val);`	切勿用 `memset` 填 `1`，会产生字节拼凑错误
申请超大数组	声明为全局变量，或使用 `std::vector<int>`	局部数组严禁超过 $10^5$ 量级，否则引发栈溢出
二维矩阵遍历	恒定采用外层行、内层列顺次访问	保持空间局部性，极大提高 CPU 缓存命中率
网格图多向移动	定义 `dx[] = {-1,0,1,0}; dy[] = {0,1,0,-1};`	移动后必须做 `nx >= 0 && nx < N` 边界检查
函数传递数组	`void func(int arr[], int n)` 显式带上长度	数组传参会退化为首地址指针，丢失大小信息

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com