vector 容器初识

一、常见用法与接口与 string 类似vector 提供了构造、容量、访问、插入删除等一套完整的接口其中多数用法与 string 默奏一致。构造方式包括空构造、指定大小和初始值、拷贝构造、迭代器范围构造。访问方式与 string 完全一样operator[] 和 at()。示例 1vector 基本用法#include iostream#include vectorusing namespace std;int main() {vectorint v1;vectorint v2(5, 42); // 5个42vectorint v3(v2); // 拷贝vectorint v4 {1,2,3,4,5}; // 初始化列表(C11)cout v2 size v2.size() cap v2.capacity() \n;for (size_t i 0; i v4.size(); i)cout v4[i] ;cout \n;cout front v4.front() back v4.back() \n;return 0;}二、扩容机制vector 的核心特性是动态扩容——当容量不足时会申请一块更大空间将旧元素迁移过去释放旧空间。不同平台的扩容策略不同VS (PJ 版本)约 1.5 倍增长g (SGI 版本)2 倍增长频繁扩容会带来明显的性能开销如果事先能够确定元素个数建议用 reserve() 预留好空间。示例 2扩容行为观察#include iostream#include vectorusing namespace std;int main() {vectorint v;size_t last 0;for (int i 0; i 100; i) {v.push_back(i);if (v.capacity() ! last) {cout cap changed: v.capacity() \n;last v.capacity();}}// 使用 reserve 预留vectorint v2;v2.reserve(100);cout v2 capacity after reserve(100): v2.capacity() \n;for (int i 0; i 100; i) v2.push_back(i);cout v2 size v2.size() cap v2.capacity() \n;return 0;}三、插入与删除vector 的插入删除接口与 string 非常类似push_back(val) / pop_back()尾部插入/删除O(1)insert(pos, val)在指定位置插入后续元素后移erase(pos)删除指定位置后续元素前移这些操作均可能引起迭代器失效示例 3插入与删除#include iostream#include vectorusing namespace std;int main() {vectorint v {1, 2, 3, 4, 5};v.push_back(6);v.pop_back();// 在第 2 个位置插入 99v.insert(v.begin() 1, 99);// 删除第 3 个元素v.erase(v.begin() 2);for (int x : v) cout x ;cout \n;// 使用算法库中的 findauto it find(v.begin(), v.end(), 99);if (it ! v.end())cout found 99 at pos (it - v.begin()) \n;return 0;}四、迭代器失效这是 vector 最重要的注意点之一。当 vector 发生扩容或删除操作时旧的迭代器指向的内存可能已被释放或未定义继续使用会导致程序崩溃。引起迭代器失效的操作扩容操作resize、reserve、push_back、insert、assign 等erase 删除任意位置元素后该位置及之后的迭代器均失效解决办法在使用前重新给迭代器赋值接收 insert/erase 的返回值。示例 4迭代器失效与解决方案#include iostream#include vectorusing namespace std;int main() {vectorint v {1, 2, 3, 4, 5, 6};// 删除所有偶数必须接收 erase 返回值auto it v.begin();while (it ! v.end()) {if (*it % 2 0)it v.erase(it); // 删除后迭代器失效重新赋值elseit;}for (int x : v) cout x ;cout \n;// 扩容后迭代器失效vectorint v2 {1, 2, 3};auto it2 v2.begin();v2.push_back(4); // 可能扩容// cout *it2; // 未定义行为it2 v2.begin(); // 重新赋值cout *it2 \n; // 正确return 0;}五、常见 OJ以下是两个经典的 vector 应用题目可以用来训练 vector 的使用。示例 5杨辉三角#include iostream#include vectorusing namespace std;vectorvectorint generate(int n) {vectorvectorint vv(n);for (int i 0; i n; i) {vv[i].resize(i 1, 1);for (int j 1; j i; j)vv[i][j] vv[i-1][j-1] vv[i-1][j];}return vv;}int main() {auto vv generate(5);for (auto row : vv) {for (int x : row) cout x ;cout \n;}return 0;}示例 6删除排序数组中的重复项#include iostream#include vectorusing namespace std;int removeDuplicates(vectorint nums) {if (nums.empty()) return 0;int k 1;for (int i 1; i (int)nums.size(); i)if (nums[i] ! nums[k-1])nums[k] nums[i];nums.resize(k);return k;}int main() {vectorint v {0,0,1,1,1,2,2,3,3,4};int len removeDuplicates(v);cout len len [ ;for (int x : v) cout x ;cout ]\n;return 0;}六、模拟实现与深拷贝问题vector 的模拟实现核心是管理三个指针start、finish、end_of_storage。一个常见的坑是用 memcpy 进行容器内容的拷贝——如果元素是自定义类型如 stringmemcpy 只会浅拷贝导致多个对象共享同一块内存释放时崩溃。这与之前学习类与对象时的深浅拷贝问题是一致的。正确做法是递归地调用元素的拷贝构造或赋值运算符。示例 7模拟实现的核心框架#include iostream#include cstringusing namespace std;templatetypename Tclass Vector {public:Vector() : _start(nullptr), _finish(nullptr), _end(nullptr) {}~Vector() {for (T* p _start; p ! _finish; p) p-~T();operator delete(_start);}void push_back(const T val) {if (_finish _end)reserve(capacity() 0 ? 2 : capacity() * 2);new (_finish) T(val); // placement new_finish;}size_t size() const { return _finish - _start; }size_t capacity() const { return _end - _start; }T operator[](size_t i) { return _start[i]; }private:void reserve(size_t n) {if (n capacity()) {T* newData (T*)operator new(n * sizeof(T));size_t oldSize size();for (size_t i 0; i oldSize; i)new (newData i) T(_start[i]); // 调用拷贝构造for (T* p _start; p ! _finish; p) p-~T();operator delete(_start);_start newData;_finish _start oldSize;_end _start n;}}T* _start;T* _finish;T* _end;};int main() {Vectorint v;v.push_back(10);v.push_back(20);v.push_back(30);for (size_t i 0; i v.size(); i)cout v[i] ;cout \n;return 0;}总结vector 是一个动态数组内存连续支持 O(1) 随机访问扩容策略因平台而异VS 1.5倍 / g 2倍可用 reserve 优化迭代器失效是最常见的坑扩容和 erase 后必须重新赋值模拟实现时不能用 memcpy 替代深拷贝后续将学习 list、deque 等其他容器与 vector 形成对比