C++ 学习笔记(三)——容器与数组
- 2026-04-22 10:26:19
C++ 学习笔记
完整整理版· 含原理解析 / 易错对比 / 速查表
涵盖：数据类型· 函数与作用域 · 容器 · 字符串 · 二叉树 · 排序 · 类结构
三、容器与数组
3.1 vector 的基础操作
vector 是 C++ 最常用的动态数组，大小可在运行时改变，提供了丰富的成员函数。
赋值方式的选择——最高频错误之一
方式 1：push_back（最常用，不需要预先知道大小）
vector<int> tem; // 此时 size=0，容量未定 tem.push_back(1); // 追加到末尾，自动扩容 tem.push_back(2); // tem = {1, 2}，size=2 |
方式 2：下标赋值（必须提前用构造函数开空间）
vector<int> tem(5); // 构造 5 个元素，初始值全为 0 tem[0] = 1; // ✅ 合法，已分配空间 tem[1] = 2; | |
⚠️ 注意 vector<int> tem; 后直接 tem[0]=1 会越界！此时 tem.size()==0，[] 下标不会自动扩容，结果是未定义行为（UB），程序可能崩溃或输出乱码。 |
访问最后一个元素（C++ 不支持 [-1]）
Python 支持负索引，C++ 不支持。访问最后一个元素有两种标准写法：
vector<int> v = {10, 20, 30}; int last = v.back(); // ✅ 推荐，语义清晰 int last2 = v[v.size() - 1]; // ✅ 等价写法 // v[-1] ❌ C++ 不支持，访问非法内存 |
插入元素到指定位置
vector<int> v = {10, 20, 30}; v.insert(v.begin(), 5); // 插入到开头：{5,10,20,30} v.insert(v.begin() + 2, 99); // 插入到下标2：{5,10,99,20,30} v.insert(v.end(), 100); // 插入到末尾（等价 push_back） | |
��说明insert 的时间复杂度是 O(n)，因为要移动后面的元素。频繁在开头/中间插入时考虑使用 list 或 deque。 |
返回空 vector
// 函数返回类型为 vector<int> 时，返回空容器 return {}; // ✅ 最简洁 return vector<int>(); // ✅ 等价 |
创建预填充 vector
// 一维：长度 n，全零 vector<int> arr(n, 0); // 二维：rows 行 cols 列，全零 vector<vector<int>> grid(rows, vector<int>(cols, 0)); // bool 数组：全 false vector<bool> vis(n, false); // assign 方法：适合先声明、后才知道大小的场景 vector<bool> col, diag1, diag2; col.assign(n, false); diag1.assign(2 * n - 1, false); // 空间 ×2：N皇后中 row-col 可能为负 diag2.assign(2 * n - 1, false); // 用 2n-1 确保下标永远合法 |
vector 切片（截取子数组）
原生数组无切片功能；vector 用迭代器范围构造，语义与 Python [start:end]完全一致，左闭右开：
vector<int> arr = {1, 2, 3, 4, 5}; // 截取下标 [1, 4)，即 {2, 3, 4} vector<int> sub(arr.begin() + 1, arr.begin() + 4); // 截取从下标 2 到末尾：{3, 4, 5} vector<int> tail(arr.begin() + 2, arr.end()); // ⚠️ 常见误用： vector<int> wrong(1, 3); // 这是「1个元素，值为3」，结果 = {3}，与切片无关！ | |
⚠️ 注意 确保 begin()+i <= end()，否则是未定义行为（UB）。程序可能崩溃或输出乱码，编译器不报错，非常难以调试。 |
3.2 原生数组的长度获取与首地址
原生数组（int arr[]）一旦传递给函数就退化为指针，完全丢失长度信息。这是 C++ 的历史遗留设计，实践中尽量用 vector 代替。
// 方法：用 vector 接收，再操作 void process(vector<int>& data) { int len = data.size(); // ✅ 正确获取长度 } // 若需要 int* 指针（传给 C 风格函数等） int* ptr = data.data(); // ✅ 获取底层 int* 首地址 int* ptr2 = &data[0]; // ✅ 等价写法 // ❌ 错误写法 int* ptr3 = &data; // ❌ &data 是 vector<int>* 类型，不是 int* | |
⚠️ 注意 数组首地址（int*）不能赋值给树节点指针（TreeNode*）：head->left = ptr 会报类型不匹配错误。两者完全是不同类型的指针。 |
3.3 原生数组 vs STL 容器能力对比
能力 | 原生数组 int[] | vector<int> |
.empty() 判空 | ❌ 不支持 | ✅ 支持，返回 true/false |
.size() 长度 | ❌ 只能用 sizeof（编译期） | ✅ 支持，运行时动态 |
.back() 末尾元素 | ❌ 不支持 | ✅ 支持 |
[-1] 负索引 | ❌ C++ 不支持 | ❌ 同左，用 .back() |
切片 | ❌ 不支持 | ✅ 迭代器范围构造 |
.push_back() | ❌ 不支持 | ✅ 动态追加 |
获取首地址 | 直接用数组名 | data.data() 或 &data[0] |
传函数后知长度 | ❌ 退化为指针，长度丢失 | ✅ size() 仍然有效 |
3.4 查找容器中是否存在某元素
C++ 没有类似 Python in运算符的语法。对 vector/list 等线性容器，用 std::find()；对 set/map，用 .count()或.find()（更高效）：
#include <algorithm> // 必须引入，std::find 在这里 vector<char> data = {'a','b','c','d'}; char ch = 'b'; // std::find 返回迭代器，找不到时返回 end() if (find(data.begin(), data.end(), ch) != data.end()) { cout << "存在"; } // set 直接用 .count()，O(log n)，比 find O(n) 快 set<char> s = {'a','b','c'}; if (s.count('b')) { cout << "存在"; } // unordered_set 的 .count()，O(1) 平均 unordered_set<int> us = {1,2,3}; if (us.count(2)) { cout << "存在"; } | |
��提示若需要频繁查找某个元素是否存在，将数据放入 unordered_set（哈希集合），查找时间复杂度降至 O(1)，比 vector 的 O(n) 快得多。 |
3.5 哈希表（unordered_map / map）
unordered_map<int,int> mp; // 存入数据 mp[1] = 100; mp[2] = 0; // value=0 也是有效记录！ // 查找：find() vs count() mp.find(1) != mp.end() // ✅ 存在（推荐） mp.count(1) > 0 // ✅ 等价 mp.find(2) != mp.end() // ✅ 也能找到（value=0 不影响查找） // 删除后才真正找不到 mp.erase(2); mp.find(2) != mp.end() // false，删除后找不到了 // 遍历 for (auto& [key, val] : mp) { cout << key << " -> " << val; } | |
⚠️ 注意 mp[key] 在 key 不存在时会自动插入默认值 0！若只想查询而不想修改，用 mp.find(key) 而非 mp[key]。 |
用 set 对二维数组去重
哈希表的 key 不能是数组/vector（没有默认哈希函数）。对二维数组去重时，用 set<vector<int>>（有序，支持 vector 作 key）：
vector<vector<int>> erwei = {{1,2},{3,4},{1,2}}; set<vector<int>> quchong; for (vector<int> val : erwei) { quchong.insert(val); // set 自动去重 } // quchong = {{1,2},{3,4}} // 转回 vector<vector<int>> vector<vector<int>> res(quchong.begin(), quchong.end()); |
3.6 stack 常见陷阱
stack<int> st; // ❌ 空栈调用 top() 直接崩溃（未定义行为） // int x = st.top(); // ✅ 必须先检查非空 if (!st.empty()) { int x = st.top(); // 只查看，不弹出 st.pop(); // pop() 弹出但不返回值 } // ⚠️ 注意：C++ stack 的 pop() 不返回值！ // 要取出并删除，需先 top() 再 pop() int val = st.top(); st.pop(); |
3.7 链表指针的正确初始化
新建一个指针变量时，它只是一个存地址的变量，本身并没有分配任何内存。必须先用 new 分配内存，才能通过 -> 访问成员：
// ❌ 错误：head 只是一个野指针，没有指向任何有效内存 ListNode* head; head->next = nullptr; // 崩溃！解引用野指针 // ✅ 正确：先用 new 分配一个节点 ListNode* head = new ListNode(0); // 分配内存，val=0 head->next = nullptr; // ✅ 安全 // 常见用法：用虚拟头节点简化链表操作 ListNode* dummy = new ListNode(0); dummy->next = head; // 指向真正的链表头 |
END
