C++动态数组原理与刷题实战：从基础到优化-育师

1. 从数组到动态数组：C++线性表的核心进化

在C++的世界里，数组是最基础也是最强大的数据结构之一。作为线性表的物理实现方式，普通数组在内存中占据连续的存储空间，这种特性使得它能够以O(1)时间复杂度进行随机访问——这也是它最大的优势。但固定大小的限制让传统数组在实际开发中常常捉襟见肘，特别是在刷题和算法竞赛场景下，数据规模经常难以提前预判。

动态数组（如C++中的vector）应运而生，它在保留数组优点的同时，通过巧妙的扩容机制解决了尺寸固定的痛点。当我在LeetCode上刷到第53题"最大子数组和"时，深刻体会到动态数组的便利性——不需要预先知道输入规模，可以边读取数据边处理，这种灵活性是普通数组无法比拟的。

2. 线性表基础：数组的物理实现与操作特性

2.1 数组的内存布局与访问原理

数组在内存中是连续的字节块，假设我们声明int arr[10]，系统会分配sizeof(int)10字节的连续空间。这种布局使得计算元素地址变得极其高效：arr[i]的地址=基地址+i元素大小。在x86架构下，这种计算会被编译为简单的LEA指令，这也是数组访问速度快的根本原因。

int arr[5] = {1,2,3,4,5}; // 内存布局示例（假设int为4字节）： // 地址 值 // 0x1000 1 // 0x1004 2 // 0x1008 3 // 0x100C 4 // 0x1010 5

2.2 数组操作的时空复杂度分析

访问：O(1) - 直接地址计算
搜索：O(n) - 需要遍历（无序情况下）
插入/删除：O(n) - 需要移动后续元素
空间：O(n) - 连续占用内存

在刷题时，这种特性决定了数组适合"读多写少"的场景。比如在"两数之和"问题中，如果先对数组排序，就能使用双指针法以O(nlogn)时间解决，而直接暴力搜索需要O(n²)。

3. 动态数组实现原理与工程实践

3.1 C++ vector的扩容机制

STL中的vector采用"几何扩容"策略，当size==capacity时，会分配新的内存（通常是原容量的1.5或2倍），然后将旧元素移动（C++11后）或拷贝到新空间。这个策略使得均摊时间复杂度保持在O(1)。

vector<int> v; for(int i=0; i<100; ++i){ v.push_back(i); cout << "size:" << v.size() << " capacity:" << v.capacity() << endl; } // 典型输出（VS2019）： // size:1 capacity:1 // size:2 capacity:2 // size:3 capacity:3 // size:4 capacity:4 // size:5 capacity:6 // size:7 capacity:9 // ...

重要提示：频繁扩容会导致性能下降，如果预先知道大致规模，应该用reserve()预留空间

3.2 手写简易动态数组

理解原理最好的方式就是自己实现。下面是一个简化版的动态数组模板：

template<typename T> class MyVector { private: T* data; size_t size; size_t capacity; void reallocate(size_t new_cap) { T* new_data = new T[new_cap]; for(size_t i=0; i<size; ++i) { new_data[i] = std::move(data[i]); } delete[] data; data = new_data; capacity = new_cap; } public: MyVector() : data(nullptr), size(0), capacity(0) {} void push_back(const T& value) { if(size >= capacity) { reallocate(capacity == 0 ? 1 : capacity*2); } data[size++] = value; } // 其他成员函数省略... };

这个实现虽然简陋，但揭示了动态数组的核心机制。在工程实践中，还需要考虑异常安全、迭代器失效等问题。

4. 刷题实战：数组类问题解法精要

4.1 双指针法的典型应用

双指针是处理数组问题的利器，在"移除元素"、"有序数组去重"等问题中表现优异。以LeetCode 26题为例：

int removeDuplicates(vector<int>& nums) { if(nums.empty()) return 0; int slow = 0; for(int fast=1; fast<nums.size(); ++fast){ if(nums[fast] != nums[slow]){ nums[++slow] = nums[fast]; } } return slow+1; }

这种写法时间复杂度O(n)，空间复杂度O(1)，比使用额外空间的哈希表法更优。关键在于理解slow指针标记了当前有效序列的末尾，fast指针探索新元素。

4.2 滑动窗口解决子数组问题

对于"和大于等于target的最短子数组"这类问题，滑动窗口是标准解法：

int minSubArrayLen(int target, vector<int>& nums) { int left = 0, sum = 0; int min_len = INT_MAX; for(int right=0; right<nums.size(); ++right){ sum += nums[right]; while(sum >= target){ min_len = min(min_len, right-left+1); sum -= nums[left++]; } } return min_len == INT_MAX ? 0 : min_len; }

窗口滑动时保持的时间复杂度是O(n)，比暴力法的O(n²)高效得多。关键在于理解窗口扩张和收缩的条件。

5. 性能优化与常见陷阱

5.1 避免vector的无效操作

reserve vs resize：reserve只分配内存不构造对象，resize会构造对象
emplace_back vs push_back：emplace_back直接构造，避免临时对象
erase的陷阱：for(auto it=v.begin(); it!=v.end(); ){ it = v.erase(it); }

5.2 多维数组的内存局部性

处理矩阵问题时，访问顺序影响巨大：

// 差的访问方式 - 按列访问 for(int j=0; j<cols; ++j) for(int i=0; i<rows; ++i) sum += matrix[i][j]; // 好的访问方式 - 按行访问 for(int i=0; i<rows; ++i) for(int j=0; j<cols; ++j) sum += matrix[i][j];

现代CPU的缓存机制使得顺序访问比跳跃访问快数倍。在图像处理等场景中，这种优化可能带来10倍以上的性能提升。