?个人主页: 起名字真南
?个人专栏:【数据结构初阶】 【C语言】 【C++】 【OJ题解】
目录
1. 引言2. 实现思路3. `vector` 容器的代码实现4. 代码详解4.1 构造与析构函数4.2 容量管理4.3 迭代器与访问操作4.4 增删操作 5.测试代码6. 时间和空间复杂度分析7. 总结
1. 引言
vector 是 C++ 标准模板库（STL）中最常用的动态数组容器。它不仅提供了自动扩容、快速访问、灵活增删等功能，还能高效地管理内存。本篇文章将带大家实现一个简化版的 vector，包含动态扩容、元素插入删除、访问等操作，以此深入理解其内部实现原理，尤其是动态数组的管理机制。
2. 实现思路
我们将实现的 vector 具有如下核心功能：
3. vector 容器的代码实现
以下是完整的代码实现，功能完备，包含了构造、析构、拷贝、赋值重载、容量管理、增删操作和元素访问等基本操作：
#pragma once#include <iostream>#include <assert.h>namespace wzr { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; // 默认构造函数 vector() : _start(nullptr) , _finish(nullptr), _endOfStorage(nullptr) {} // 构造函数：构造n个value vector(size_t n, const T& value = T()) : _start(nullptr) , _finish(nullptr) , _endOfStorage(nullptr) { reserve(n); while (n--) { push_back(value); } //其实我们会发现这两串代码会有一些冗余，当我们使用vector(10,1) //编译器在编译的时候就已经将T实例化成int类型， //并且编译器会认为10，1是int，如果两个类型一致就会选择是区间构造，会报错。 vector(int n, const T & value = T()):_start(new T[n]), _finish(_start + n), _endOfStorage(_finish){reserve(n);for (int i = 0; i < n; i++){_start[i] = value;}} // 拷贝构造函数 vector(const vector<T>& v) : _start(nullptr) , _finish(nullptr) , _endOfStorage(nullptr) { reserve(v.capacity()); iterator it = begin(); const_iterator vit = v.cbegin(); while (vit != v.cend()) { *it++ = *vit++; } _finish = it; } //如果使用iterator作为迭代器进行区间初始化构造， //那么容器就是能是vector//重新声明迭代器，迭代区间[first, last)可以是任意容量的迭代器template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}} // 赋值操作符重载（采用拷贝交换优化） vector<T>& operator=(vector<T> v) { swap(v); return *this; } // 析构函数 ~vector() { if (_start) { delete[] _start; _start = _finish = _endOfStorage = nullptr; } } // 迭代器 iterator begin() { return _start; } iterator end() { return _finish; } const_iterator cbegin() const { return _start; } const_iterator cend() const { return _finish; } // 容量管理 size_t size() const { return _finish - _start; } size_t capacity() const { return _endOfStorage - _start; } bool empty() const { return _start == _finish; } // 预留空间 void reserve(size_t n) { if (n > capacity()) { size_t oldSize = size(); T* tmp = new T[n]; if (_start) { for (size_t i = 0; i < oldSize; i++) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + oldSize; _endOfStorage = _start + n; } } // 改变大小 void resize(size_t n, const T& value = T()) { if (n <= size()) { _finish = _start + n; } else { if (n > capacity()) { reserve(n); } iterator it = _finish; _finish = _start + n; while (it != _finish) { *it = value; it++; } } } // 元素访问 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; } const T& front() const { return *_start; } T& back() { return *(_finish - 1); } const T& back() const { return *(_finish - 1); } // 增删操作 void push_back(const T& value) { insert(end(), value); } void pop_back() { erase(end() - 1); } // 交换两个vector void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endOfStorage, v._endOfStorage); } // 插入 iterator insert(iterator pos, const T& x) { assert(pos <= _finish); if (_finish == _endOfStorage) { size_t newcapacity = (capacity() == 0 ? 1 : 2 * capacity()); reserve(newcapacity); pos = _start + size(); } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; --end; } *pos = x; ++_finish; return pos; } // 删除 iterator erase(iterator pos) { iterator begin = pos + 1; while (begin != end()) { *(begin - 1) = *begin; begin++; } --_finish; return pos; } private: iterator _start; // 数据起始指针 iterator _finish; // 有效数据的结束指针 iterator _endOfStorage; // 总容量的结束指针 };}4. 代码详解
4.1 构造与析构函数
vector()：默认构造函数，初始化指针为 nullptr，用于构造空的 vector。vector(size_t n, const T& value = T())：构造一个大小为 n 的 vector，并用 value 初始化每个元素。调用 reserve(n) 分配空间，再通过 push_back 插入元素。vector(const vector<T>& v)：拷贝构造函数。分配与 v 相同的空间后，逐个拷贝 v 中的元素。vector(InputIterator first,InputIterator last):使用迭代器区间去构造函数。~vector()：析构函数。释放动态分配的内存，并将所有指针置为 nullptr。 4.2 容量管理
reserve(size_t n)：扩容函数。若 n 大于当前容量，则分配一个大小为 n 的新空间，将原数据拷贝至新空间，并释放旧空间。resize(size_t n, const T& value = T())：调整 vector 大小。若 n 小于当前大小，则只需调整 _finish。若 n 大于容量，则扩容并初始化新增元素。 4.3 迭代器与访问操作
begin() 和 end()：返回 _start 和 _finish，用于迭代 vector。operator[]：通过下标访问元素，并通过 assert 检查越界访问。front() 和 back()：返回首尾元素的引用，支持首尾元素的快速访问。 4.4 增删操作
push_back(const T& value)：在尾部插入元素 value。若容量不足，调用 reserve 扩容。pop_back()：删除最后一个元素，通过调整 _finish 指针实现。insert(iterator pos, const T& x)：在指定位置插入元素 x。若容量不足，则扩容；随后将 [pos, end) 的数据右移，腾出插入位置。erase(iterator pos)：删除指定位置的元素。将 [pos + 1, end) 的数据左移一位以覆盖删除位置，更新 _finish 指针。 5.测试代码
#include"Vector.h"namespace wzr{void Test01(){vector<int> v1;vector<int> v2(10, 6);int array[] = { 1,2,3,4,5 };vector<int> v3(array, array + sizeof(array) / sizeof(array[0]));vector<int> v4(v3);for (size_t i = 0; i < v2.size(); i++){cout << v2[i] << " ";}cout << endl;auto it = v3.begin();while (it != v3.end()){cout << *it << " ";it++;}cout << endl;for (auto itt : v4){cout << itt << " ";}cout << endl;}void Test02(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);cout << v.size() << endl;cout << v.capacity() << endl;cout << v.front() << endl;cout << v.back() << endl;cout << v[0] << endl;for (auto e : v){cout << e << " ";}cout << endl;v.pop_back();v.pop_back();v.insert(v.begin(), 0);for (auto e : v){cout << e << " ";}cout << endl;v.erase(v.begin() + 1);for (auto e : v){cout << e << " ";}cout << endl;}}int main(){//wzr::Test01();wzr::Test02();return 0;}6. 时间和空间复杂度分析
push_back：均摊时间复杂度为O(1)，因为扩容后插入操作是常数时间的。pop_back：O(1)。resize：O(n)。insert 和 erase：最坏情况时间复杂度为O(n)，因为需要移动大量数据。 7. 总结
通过对各个函数的详细解析，我们手动实现了一个简化版的 vector，展示了 C++ 标准库中 vector 的核心功能。希望通过这篇文章，大家能更好地理解 vector 容器