1. C vector基础概念与核心特性在C标准库中vector是最常用且功能强大的序列容器之一。它本质上是一个动态数组能够自动管理内存并在运行时根据需要调整大小。与普通数组相比vector的最大优势在于其灵活性——你不需要预先知道元素数量容器会自动处理扩容问题。vector在内存中采用连续存储方式这意味着它支持随机访问通过下标或迭代器时间复杂度为O(1)。这种特性使得vector在需要频繁访问元素的场景下表现优异。同时vector的尾部插入和删除操作效率很高均摊O(1)时间复杂度但在中间或头部进行插入删除则效率较低O(n)时间复杂度。注意虽然vector可以动态增长但频繁的扩容操作会导致性能损耗。当元素数量超过当前容量时vector会重新分配更大的内存空间通常是当前容量的2倍并将原有元素拷贝到新空间。1.1 vector的基本操作创建一个vector非常简单以下是几种常见的初始化方式#include vector using namespace std; // 空vector vectorint v1; // 包含10个元素每个初始化为0 vectorint v2(10); // 包含10个元素每个初始化为5 vectorint v3(10, 5); // 通过初始化列表创建 vectorint v4 {1, 2, 3, 4, 5}; // 通过数组创建 int arr[] {1, 2, 3}; vectorint v5(arr, arr sizeof(arr)/sizeof(arr[0]));vector提供了丰富的成员函数来操作元素v.push_back(10); // 尾部添加元素 v.pop_back(); // 删除尾部元素 v.size(); // 返回元素数量 v.empty(); // 判断是否为空 v.clear(); // 清空所有元素 v.front(); // 访问第一个元素 v.back(); // 访问最后一个元素 v.at(2); // 安全访问元素会检查边界 v[2]; // 直接访问元素不检查边界1.2 vector的迭代器vector支持多种迭代器操作这是STL容器的重要特性vectorint::iterator it; for(it v.begin(); it ! v.end(); it) { cout *it ; } // 使用C11范围for循环 for(auto num : v) { cout num ; } // 反向迭代器 for(auto rit v.rbegin(); rit ! v.rend(); rit) { cout *rit ; }迭代器失效是使用vector时需要特别注意的问题。当vector进行插入或删除操作时可能会导致现有的迭代器失效。例如vectorint v {1, 2, 3, 4}; auto it v.begin() 2; v.insert(v.begin(), 0); // 插入操作可能导致it失效 // 此时使用it是未定义行为2. vector的内存管理与性能优化2.1 vector的容量机制vector采用动态数组实现内部维护三个关键指针指向数据起始位置的指针、指向最后一个元素之后的指针以及指向分配内存末尾的指针。这三个指针分别对应begin()、end()和capacity()的概念。vectorint v; cout size: v.size() endl; // 当前元素数量 cout capacity: v.capacity() endl; // 当前分配的内存容量当size达到capacity时vector会执行扩容操作。不同编译器的扩容策略可能不同但通常是当前容量的2倍。这种指数增长策略保证了插入操作的均摊时间复杂度为O(1)。2.2 预留空间优化如果你预先知道vector需要存储大量元素可以使用reserve()方法预先分配足够空间避免多次扩容带来的性能损耗vectorint v; v.reserve(1000); // 预先分配1000个元素的空间 for(int i 0; i 1000; i) { v.push_back(i); // 不会触发扩容 }另一个相关方法是shrink_to_fit()它请求移除未使用的容量使capacity()等于size()。但注意这是非强制性的请求具体实现可能忽略它。2.3 元素访问性能对比vector提供了多种元素访问方式它们的性能特点有所不同访问方式安全性性能适用场景operator[]不安全最高确定索引有效时at()安全中等需要边界检查时front()/back()不安全高访问首尾元素时迭代器不安全高遍历或算法操作时在实际应用中operator[]通常是最快的访问方式但使用前应确保索引有效。at()会进行边界检查如果索引无效会抛出std::out_of_range异常。3. vector的高级用法与技巧3.1 vector的交换与移动C11引入了移动语义vector也支持高效的移动操作vectorint v1 {1, 2, 3}; vectorint v2 std::move(v1); // 移动构造v1现在为空 // 交换两个vector的内容没有内存分配 v1.swap(v2);swap()操作非常高效它只是交换内部指针不涉及元素的实际移动。这在需要清空vector并释放内存时特别有用vectorint v(1000); // 清空v并释放内存 vectorint().swap(v);3.2 vector与自定义类型vector可以存储任何可拷贝和可移动的类型包括自定义类class MyClass { public: MyClass(int x) : data(x) {} // 需要定义拷贝构造函数和赋值运算符 MyClass(const MyClass other) : data(other.data) {} MyClass operator(const MyClass other) { data other.data; return *this; } private: int data; }; vectorMyClass myVec; myVec.push_back(MyClass(10));如果类支持移动语义可以进一步提高性能class MyMovableClass { public: MyMovableClass(int x) : data(new int(x)) {} // 移动构造函数 MyMovableClass(MyMovableClass other) noexcept : data(other.data) { other.data nullptr; } ~MyMovableClass() { delete data; } private: int* data; };3.3 vector的emplace操作C11引入了emplace系列方法它们直接在容器内构造元素避免了临时对象的创建和拷贝vectorpairint, string v; v.emplace_back(1, one); // 直接在vector中构造pair // 等同于 v.push_back(make_pair(1, one)); 但更高效emplace_back()比push_back()更高效特别是对于复杂类型因为它避免了临时对象的创建和拷贝/移动操作。4. vector的常见问题与解决方案4.1 迭代器失效问题vector的某些操作会导致迭代器失效这是常见的问题来源。主要情况包括插入元素所有迭代器可能失效如果触发了扩容删除元素被删除元素之后的迭代器会失效resize/reserve可能使所有迭代器失效安全的使用模式是避免保存迭代器长期使用或者在修改操作后重新获取迭代器。4.2 性能陷阱vector虽然高效但不当使用会导致性能问题频繁在头部或中间插入考虑使用list或deque未预分配足够空间导致多次扩容存储大对象vector存储大对象时移动成本高考虑存储指针或使用专门容器4.3 二维vector的使用vector可以嵌套使用创建多维数组这是常见的动态二维数组实现方式// 创建5x10的二维数组初始化为0 vectorvectorint matrix(5, vectorint(10, 0)); // 不规则二维数组 vectorvectorint jagged; jagged.push_back(vectorint(3)); jagged.push_back(vectorint(5));多维vector的访问方式与普通数组类似matrix[2][3] 42; // 访问第3行第4列元素需要注意的是这种实现方式在内存中不是完全连续的每个内层vector独立分配内存。如果需要完全连续的内存布局可以考虑使用一维vector模拟多维数组// 5行10列的二维数组使用一维vector实现 vectorint matrix(5 * 10); // 访问第i行第j列元素matrix[i * 10 j]4.4 vector与算法结合vector与STL算法完美配合可以高效实现各种操作vectorint v {3, 1, 4, 1, 5, 9, 2, 6}; // 排序 sort(v.begin(), v.end()); // 查找 auto it find(v.begin(), v.end(), 5); if(it ! v.end()) { cout Found at position: it - v.begin(); } // 移除重复元素需要先排序 sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); // 使用lambda表达式 sort(v.begin(), v.end(), [](int a, int b) { return a b; // 降序排序 });5. vector在实际项目中的应用案例5.1 游戏开发中的应用在游戏开发中vector常用于存储游戏实体、粒子效果、渲染数据等。例如class GameObject { // 游戏对象基类 }; vectorunique_ptrGameObject gameObjects; // 每帧更新所有游戏对象 for(auto obj : gameObjects) { obj-update(); } // 渲染所有游戏对象 for(auto obj : gameObjects) { obj-render(); }使用unique_ptr可以安全地管理动态分配的游戏对象生命周期同时vector提供了高效的遍历和随机访问能力。5.2 数据处理与分析在数据处理应用中vector常用于存储和操作数据集vectordouble dataset; // 从文件加载数据 loadDataFromFile(data.txt, dataset); // 计算平均值 double sum accumulate(dataset.begin(), dataset.end(), 0.0); double mean sum / dataset.size(); // 找出离群值 vectordouble outliers; copy_if(dataset.begin(), dataset.end(), back_inserter(outliers), [mean](double x) { return abs(x - mean) 2 * standardDeviation; });5.3 算法竞赛中的应用在算法竞赛中vector是解决各种问题的利器// 图的邻接表表示 vectorvectorpairint, int graph(n); // n个顶点 // 添加边 void addEdge(int u, int v, int w) { graph[u].emplace_back(v, w); graph[v].emplace_back(u, w); // 无向图 } // Dijkstra算法实现 vectorint dijkstra(int start) { vectorint dist(n, INT_MAX); dist[start] 0; priority_queuepairint, int pq; pq.push({0, start}); while(!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if(-d dist[u]) continue; for(auto [v, w] : graph[u]) { if(dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({-dist[v], v}); } } } return dist; }6. vector与其他容器的比较与选择6.1 vector vs array特性vectorarray (C风格数组)大小动态可变固定大小内存管理自动手动访问速度快快插入/删除尾部快其他位置慢不支持安全性边界检查(at())无边界检查适用场景大小不确定或可能变化大小固定且已知6.2 vector vs list特性vectorlist内存布局连续非连续随机访问O(1)O(n)插入/删除尾部O(1)其他位置O(n)任意位置O(1)内存占用较少无额外指针较多每个元素两个指针缓存友好性高低适用场景频繁访问少插入删除频繁在任意位置插入删除6.3 vector vs deque特性vectordeque内存结构单块连续内存多块连续内存头部操作O(n)O(1)尾部操作O(1)O(1)随机访问略快略慢内存使用更紧凑更分散适用场景主要尾部操作频繁头部和尾部操作在实际项目中选择容器时应考虑以下因素元素的访问模式随机访问还是顺序访问插入和删除的位置和频率内存使用效率的要求缓存友好性的重要性vector在大多数情况下都是首选容器除非有特定的需求如频繁在头部插入删除需要使用其他容器。
