在C++编程中，当我们需要处理二维数据结构，例如矩阵、表格或网格时，std::vector 是一个非常灵活且强大的工具。而对于二维场景，我们常常会用到“二维vector”的概念。它并非一个独立的C++标准库类型，而是通过 std::vector 嵌套 std::vector 来实现的，即 std::vector<std::vector<T>>，其中 T 可以是任何数据类型（如 int, double, string 等）。
是什么：二维Vector的本质
从概念上讲，二维vector可以被视为一个由行和列组成的表格或矩阵。每一“行”本身是一个vector，而整个二维vector则是一个包含这些“行”vector的vector。
**在C++中，std::vector<std::vector<T>> 实际上是：**
-
一个外层
std::vector，它的每个元素都是一个内层std::vector<T>。 - 外层vector的大小代表“行”的数量。
- 内层vector的大小代表对应行的“列”的数量。
需要注意的是，这种结构与传统的C风格二维数组（如 int arr[3][4];）在内存布局上有所不同。C风格二维数组通常在内存中是连续存储的，而二维vector虽然每个内层vector的元素是连续存储的，但不同的内层vector（不同的行）在内存中不一定相互紧挨着。它们可能分散在堆内存的不同位置，外层vector只存储指向这些内层vector起始位置的指针或相关管理信息。
为什么使用二维Vector？
相比于传统的C风格二维数组或手动管理的动态二维数组（如使用 new T*[rows]），使用 std::vector<std::vector<T>> 有着显著的优势：
- 动态大小： 这是vector最大的优势。你无需在编译时确定二维vector的行数和列数。可以在程序运行时根据需要添加或删除行，甚至每行的列数都可以不同（创建“锯齿状”或“不规则”的二维结构）。
-
自动内存管理：
std::vector会自动处理内存的分配和释放。当你创建一个二维vector时，它会自动分配所需的内存；当它超出作用域或被销毁时，内存也会被自动回收，有效避免了内存泄漏的问题。这比手动使用new和delete来管理二维数组要安全得多。 -
方便的操作： vector提供了丰富的成员函数，如
push_back()（在末尾添加元素或行）、pop_back()（移除末尾元素或行）、size()（获取大小/行数或列数）、empty()（检查是否为空）、clear()（清空所有元素或行）等，使得对二维数据的操作更加直观和便捷。 - 与标准库算法兼容： 因为内层和外层都是vector，你可以方便地将它们与C++标准库中的算法（如排序、查找等）结合使用。
虽然二维vector在内存布局上可能不如连续的二维数组紧凑，这在某些高性能计算场景下可能略有开销，但对于大多数应用来说，其带来的动态性、安全性和便利性是更重要的考量。
如何创建和初始化二维Vector？
创建和初始化二维vector有多种方式，取决于你的需求。
创建空的二维Vector
这只会创建一个外层vector，其中不包含任何内层vector（即没有行）。
std::vector<std::vector<int>> empty_matrix;
此时 empty_matrix.size() 为 0。
创建指定行数但每行为空的二维Vector
创建外层vector，指定其大小（行数），但内层vector（列）是空的。
int num_rows = 5;
std::vector<std::vector<int>> matrix_with_rows(num_rows);
此时 matrix_with_rows.size() 为 5，但 matrix_with_rows[0].size() 为 0。
创建指定行数和列数，并用默认值初始化
创建一个 M 行 N 列的二维vector，所有元素会被初始化为对应类型的默认值（例如，int 和 double 默认为 0，bool 默认为 false，对象类型调用默认构造函数）。
int num_rows = 3;
int num_cols = 4;
std::vector<std::vector<int>> zero_matrix(num_rows, std::vector<int>(num_cols));
这里，外层vector被初始化为包含 num_rows 个元素，每个元素都是一个大小为 num_cols 的 std::vector<int>。
创建指定行数和列数，并用特定值初始化
创建一个 M 行 N 列的二维vector，所有元素都被初始化为指定的值。
int num_rows = 2;
int num_cols = 5;
int initial_value = 99;
std::vector<std::vector<int>> filled_matrix(num_rows, std::vector<int>(num_cols, initial_value));
此时，filled_matrix 是一个 2×5 的矩阵，所有元素都是 99。
使用初始化列表初始化
对于已知固定内容的二维数据，可以使用初始化列表。
std::vector<std::vector<int>> init_matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
注意，使用初始化列表可以很容易创建“锯齿状”vector：
std::vector<std::vector<int>> ragged_matrix = {
{1, 2},
{3, 4, 5, 6},
{7}
};
运行时构建二维Vector（逐行或逐元素添加）
可以先创建一个空的二维vector，然后动态地添加行。
std::vector<std::vector<int>> dynamic_matrix;
// 添加第一行
dynamic_matrix.push_back({10, 20, 30});
// 添加第二行，并逐个添加元素
std::vector<int> second_row;
second_row.push_back(40);
second_row.push_back(50);
dynamic_matrix.push_back(second_row);
// 或者直接在现有行中添加元素（如果行已存在且大小合适）
// dynamic_matrix[0].push_back(35); // 如果第一行不是用初始化列表创建的，可能需要确保它不是空的或者已经有足够的容量。如果第一行是空的，直接push_back可行。
如何访问和操作二维Vector？
访问和操作二维vector的元素类似于操作普通vector，但需要使用两个索引：一个用于选择行，一个用于选择列。
访问元素
使用下标运算符 [] 或成员函数 .at()。
std::vector<std::vector<int>> matrix = {{1, 2}, {3, 4}};
// 使用 [] 访问 (不执行边界检查)
int element1 = matrix[0][1]; // 获取第一行（索引0）的第二个元素（索引1），即 2
// 使用 .at() 访问 (执行边界检查，越界抛出 std::out_of_range 异常)
int element2 = matrix.at(1).at(0); // 获取第二行（索引1）的第一个元素（索引0），即 3
// 修改元素
matrix[0][1] = 99; // 现在 matrix 是 {{1, 99}, {3, 4}}
推荐在不确定索引是否有效时使用 .at() 以增加程序的健壮性。
获取维度（行数和列数）
std::vector<std::vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}};
size_t num_rows = matrix.size(); // 获取行数 (这里是 2)
// 获取列数。注意：对于非锯齿状vector，所有行的列数相同。
// 需要先确保 matrix 不为空，否则 matrix[0] 是无效的。
size_t num_cols = (num_rows > 0) ? matrix[0].size() : 0; // 获取第一行的列数 (这里是 3)
遍历二维Vector
通常使用嵌套循环来遍历所有元素。
使用索引遍历
std::vector<std::vector<int>> matrix = {{1, 2}, {3, 4}, {5, 6}};
for (size_t i = 0; i < matrix.size(); ++i) { // 外层循环遍历行
for (size_t j = 0; j < matrix[i].size(); ++j) { // 内层循环遍历列
// 访问 matrix[i][j]
// std::cout << matrix[i][j] << " ";
}
// std::cout << std::endl;
}
使用范围-based for 循环遍历
这是C++11及更高版本推荐的方式，代码更简洁。
std::vector<std::vector<int>> matrix = {{1, 2}, {3, 4}, {5, 6}};
for (const auto& row : matrix) { // 遍历每一行（row 是一个 vector<int>）
for (int element : row) { // 遍历当前行的每个元素
// 访问 element
// std::cout << element << " ";
}
// std::cout << std::endl;
}
使用 const auto& 可以避免不必要的拷贝，提高效率。
添加/删除行或元素
使用vector的成员函数进行操作：
-
**添加行：**
push_back()将一个vector添加到二维vector的末尾。std::vector<std::vector<int>> matrix = {{1, 2}};
std::vector<int> new_row = {3, 4, 5};
matrix.push_back(new_row); // matrix 现在是 {{1, 2}, {3, 4, 5}} -
**删除末尾行：**
pop_back()移除二维vector的最后一个元素（即最后一行）。std::vector<std::vector<int>> matrix = {{1, 2}, {3, 4}};
matrix.pop_back(); // matrix 现在是 {{1, 2}} -
**在特定行添加元素：** 在内层vector上使用
push_back()。std::vector<std::vector<int>> matrix = {{1, 2}};
matrix[0].push_back(3); // matrix 现在是 {{1, 2, 3}} -
**删除特定行：** 使用外层vector的
erase()函数，结合迭代器。std::vector<std::vector<int>> matrix = {{1, 2}, {3, 4}, {5, 6}};
// 删除索引为 1 的行 (第二行)
matrix.erase(matrix.begin() + 1); // matrix 现在是 {{1, 2}, {5, 6}} -
**删除特定行内的元素：** 使用内层vector的
erase()函数。std::vector<std::vector<int>> matrix = {{1, 2, 3}, {4, 5}};
// 删除第一行（索引 0）的第二个元素（索引 1）
matrix[0].erase(matrix[0].begin() + 1); // matrix 现在是 {{1, 3}, {4, 5}}
调整大小 (Resizing)
可以使用 resize() 成员函数来改变二维vector的行数。如果新指定的行数大于当前行数，新添加的行将是默认初始化的空vector。如果小于当前行数，多余的行会被删除。
std::vector<std::vector<int>> matrix = {{1, 2}, {3, 4}}; // 2x2
matrix.resize(3); // 现在 matrix 有 3 行，第三行是空的: {{1, 2}, {3, 4}, {}}
// 也可以 resize 并指定新添加的内层vector的大小和初始化值
matrix.resize(4, std::vector<int>(2, 10)); // 现在 matrix 有 4 行，最后一行是 {10, 10}
// matrix 现在是 {{1, 2}, {3, 4}, {}, {10, 10}}
要调整列数，需要遍历每一行并单独 resize。对于非锯齿状vector，可以这样做：
std::vector<std::vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}}; // 2x3
int new_cols = 2;
for (auto& row : matrix) {
row.resize(new_cols);
}
// matrix 现在是 {{1, 2}, {4, 5}}
内存开销有多少？
理解二维vector的内存布局有助于估算其开销。
一个 std::vector<std::vector<T>> 的总内存开销大致包括：
- **外层vector的开销：** 外层vector自身需要一定的内存来存储其大小、容量以及一个指向其元素（即内层vector）数组的指针。这个开销相对固定，取决于系统架构和库实现，通常是几十个字节。
-
**内层vector对象的开销：** 每一个内层
std::vector<T>对象也需要一定的内存来存储其大小、容量以及一个指向其实际数据（T类型元素）数组的指针。如果二维vector有 M 行，就会有 M 个内层vector对象，总开销约为M * sizeof(内层vector对象)。 -
**实际数据元素的开销：** 这是主要的内存消耗部分。所有内层vector中存储的
T类型元素的总大小。如果是一个 M 行 N 列的非锯齿状二维vector，元素总数为 M * N。总开销约为M * N * sizeof(T)。对于锯齿状vector，需要累加所有行的元素数量。
总内存开销 ≈ 外层vector开销 + M * 内层vector对象开销 + 所有元素总大小。
与同样大小的C风格二维数组 T arr[M][N] 相比，二维vector通常会有更多的内存开销，主要是因为每个内层vector都有自己的管理开销。但好处是提供了动态性和自动管理。
此外，如前所述，内层vector的数据是连续的，但不同行的数据块可能不连续。这可能影响缓存的局部性，对于需要高度优化内存访问的算法（如大型矩阵运算），C风格数组或特制的内存管理方案可能更优。但在大多数常见应用中，二维vector的性能是完全可以接受的。
典型应用场景在哪里？
二维vector因其灵活性和便利性，在多种编程场景中被广泛应用：
- 矩阵和线性代数： 表示和操作数学上的矩阵，进行加、减、乘等运算。
- 图像处理： 存储简单的灰度图像像素数据（每个元素代表一个像素的灰度值），或多通道图像（如果 T 是一个包含多个通道值的结构体或小vector）。
- 游戏开发： 表示游戏地图、棋盘状态、单元格属性等网格状数据。
- 动态规划： 构建二维DP表格，存储子问题的解。
-
图的表示： 使用邻接列表来表示图，其中外层vector的索引代表顶点，内层vector存储与该顶点相邻的所有顶点。例如
std::vector<std::vector<int>> adj_list;。 - 表格数据： 存储简单的二维表格数据，如从文件读取的CSV数据（每行是一个vector<string>）。
- 迷宫或路径查找算法： 表示迷宫的布局，每个元素代表一个单元格的状态（可通过/不可通过）。
总而言之，任何需要以行和列的形式组织和访问数据的场景，二维vector都是一个自然且强大的选择，尤其是在数据规模不确定或可能发生变化的情况下。
