vector 核心接口和模拟实现

std::vector是 C STL 最常用的动态数组底层是连续内存支持动态扩容、随机访问。下面先梳理核心接口再用 C 手写模拟实现底层原理 完整代码。一、vector 核心接口常用1. 构造与析构cpp运行vectorT v; // 默认构造 vectorT v(n, val); // 构造n个val vectorT v(begin, end); // 迭代器区间构造 vectorT v(other); // 拷贝构造 ~vector(); // 析构释放内存2. 容量操作cpp运行size_t size(); // 有效元素个数 size_t capacity(); // 总容量可存储元素总数 bool empty(); // 判断是否为空 void reserve(n); // 扩容仅改变容量n不初始化 void resize(n, val); // 改变有效元素个数多删少补val默认0 void shrink_to_fit(); // 缩容容量大小3. 访问元素cpp运行T operator[](i); // 随机访问无越界检查 T at(i); // 随机访问有越界检查抛异常 T front(); // 首元素 T back(); // 尾元素 T* data(); // 返回底层数组指针4. 修改操作cpp运行void push_back(val); // 尾插 void pop_back(); // 尾删 iterator insert(pos, val); // 指定位置插入 iterator erase(pos); // 删除指定位置 void clear(); // 清空有效元素不释放空间 void swap(other); // 交换两个vector5. 迭代器iteratorcpp运行iterator begin(); // 指向首元素 iterator end(); // 指向尾元素下一个位置二、vector 模拟实现手写原理1. 底层原理vector 底层用三个指针管理内存_start指向数组起始位置_finish指向最后一个有效元素的下一个位置_end_of_storage指向容量末尾的下一个位置扩容机制通常是1.5 倍 或 2 倍 扩容不同编译器不同扩容流程开辟新空间 → 拷贝旧数据 → 释放旧空间 → 更新指针2. 完整模拟实现代码cpp运行#include iostream #include cassert #include algorithm // swap // 命名空间隔离避免和std冲突 namespace my_vector { // 模拟vector templateclass T class vector { public: // 迭代器 原生指针 typedef T* iterator; typedef const T* const_iterator; // ------------------- 构造 析构 ------------------- // 默认构造 vector() : _start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} // 构造n个val vector(size_t n, const T val T()) { reserve(n); for (size_t i 0; i n; i) push_back(val); } // 迭代器区间构造 templateclass InputIterator vector(InputIterator begin, InputIterator end) { while (begin ! end) { push_back(*begin); begin; } } // 拷贝构造 vector(const vectorT v) { // 开辟新空间 _start new T[v.capacity()]; // 拷贝元素 for (size_t i 0; i v.size(); i) _start[i] v._start[i]; _finish _start v.size(); _end_of_storage _start v.capacity(); } // 赋值重载现代写法swap vectorT operator(vectorT v) { swap(v); return *this; } // 析构 ~vector() { if (_start) { delete[] _start; _start _finish _end_of_storage nullptr; } } // ------------------- 迭代器 ------------------- iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } // ------------------- 容量 大小 ------------------- size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } bool empty() const { return _start _finish; } // 扩容只改容量不改大小 void reserve(size_t n) { if (n capacity()) { size_t old_size size(); // 开辟新空间 T* tmp new T[n]; // 拷贝旧数据 for (size_t i 0; i old_size; i) tmp[i] _start[i]; // 释放旧空间 delete[] _start; // 更新指针 _start tmp; _finish _start old_size; _end_of_storage _start n; } } // 改大小多删少补 void resize(size_t n, const T val T()) { if (n size()) _finish _start n; else { reserve(n); while (_finish _start n) { *_finish val; _finish; } } } // ------------------- 访问元素 ------------------- T operator[](size_t pos) { assert(pos size()); return _start[pos]; } const T operator[](size_t pos) const { assert(pos size()); return _start[pos]; } T front() { return *_start; } T back() { return *(_finish - 1); } T* data() { return _start; } // ------------------- 修改操作 ------------------- // 尾插 void push_back(const T val) { // 满了就扩容2倍 if (_finish _end_of_storage) reserve(capacity() 0 ? 4 : capacity() * 2); *_finish val; _finish; } // 尾删 void pop_back() { assert(!empty()); --_finish; } // 指定位置插入 iterator insert(iterator pos, const T val) { assert(pos _start pos _finish); size_t len pos - _start; // 扩容会导致迭代器失效先更新pos if (_finish _end_of_storage) { reserve(capacity() 0 ? 4 : capacity() * 2); pos _start len; } // 数据后移 iterator end _finish; while (end pos) { *end *(end - 1); --end; } // 插入 *pos val; _finish; return pos; } // 删除指定位置 iterator erase(iterator pos) { assert(pos _start pos _finish); // 数据前移 iterator start pos; while (start _finish - 1) { *start *(start 1); start; } --_finish; return pos; } // 清空元素 void clear() { _finish _start; } // 交换 void swap(vectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } private: iterator _start; // 数组起始 iterator _finish; // 有效元素末尾 iterator _end_of_storage; // 容量末尾 }; }3. 测试代码cpp运行// 测试 void test_my_vector() { my_vector::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); // 遍历 for (auto e : v) std::cout e ; // 1 2 3 std::cout \n; v.insert(v.begin() 1, 99); // 1 99 2 3 v.erase(v.end() - 1); // 1 99 2 for (size_t i 0; i v.size(); i) std::cout v[i] ; } int main() { test_my_vector(); return 0; }三、核心知识点总结底层结构连续内存 三个指针管理支持随机访问。扩容规则自动 2 倍 / 1.5 倍 扩容扩容必开新空间、拷贝数据。迭代器本质就是原生指针insert/erase会导致迭代器失效。reserve vs resizereserve(n)只扩容不改有效元素个数。resize(n)改有效元素个数多删少补。模拟实现核心指针操作、内存管理、扩容逻辑、数据移动。总结vector 核心是动态连续数组靠三个指针管理内存常用接口push_back/pop_back/insert/erase/reserve/resize/[]手写模拟的关键扩容机制指针移动迭代器失效处理。