当前位置：首页 > news >正文

vector 核心接口和模拟实现

news 2026/4/30 7:05:09

std::vector是 C++ STL 最常用的动态数组，底层是连续内存，支持动态扩容、随机访问。下面先梳理核心接口，再用 C++ 手写模拟实现（底层原理 + 完整代码）。

一、vector 核心接口（常用）

1. 构造与析构

cpp

运行

vector<T> v; // 默认构造 vector<T> v(n, val); // 构造n个val vector<T> v(begin, end); // 迭代器区间构造 vector<T> 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); // 交换两个vector

5. 迭代器（iterator）

cpp

运行

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 template<class 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); } // 迭代器区间构造 template<class InputIterator> vector(InputIterator begin, InputIterator end) { while (begin != end) { push_back(*begin); ++begin; } } // 拷贝构造 vector(const vector<T>& 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） vector<T>& operator=(vector<T> 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(vector<T>& 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::vector<int> 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; }