标题：【C++ STL】模拟实现 vector
@水墨不写bug
（图片来源于网络）
正文开始：
STL中的vector是一个动态数组，支持随机访问，可以根据需要来扩展数组空间。
本项目将实现vector的部分常用功能，以增强对vector的熟悉程度，了解STL容器的工作原理，积累项目经验，也为将来自主实现和改造容器奠定坚实的基础。
STL内实现的vector是一个类模板，也就是vector的数据类型理论上可以是任意的数据类型，本文力求与STl采取类似的方法，通过类模板来实现vector。更接近于STL的实现方法，自然会让你对STL有更深的理解。
一、明确方式，铺平道路
1.文件问题
以前我们在实现string的时候，采用分文件操作：
string.h
string.cpp
这是一个非常好的习惯，无疑为在项目进展，和后期维护时提供了便利。但是我们要实现的vector是通过类模板来实现的，如果还将vector类内部的函数的声明与定义分离，就会出现问题：
由于类模板在编译时不会实例化，所以当我们想要调用这个类的成员函数的时候，就会发现没有匹配的成员函数，没有办法调用成员函数。于是，在用类模板实现vector时，我们不再分为vector.h和vector.cpp两个文件，而是将h和cpp文件合并为一个h文件，这样在同一个类模板中就可以调用成员函数了。
二、vector功能简介
I、构造函数和析构函数
- 默认构造函数：创建一个空的vector对象。
- 带大小和初始值的构造函数：创建一个包含指定数量元素的vector，每个元素都被初始化为相同的值。
- 范围构造函数：通过迭代器或指针的范围来初始化vector。
- 拷贝构造函数：使用另一个vector对象来初始化新的vector对象。
- 移动构造函数（C++11及以后）：使用另一个vector对象的资源来初始化新的vector对象，同时使原对象变为空。
- 初始化列表构造函数（C++11及以后）：使用初始化列表来初始化vector。
- 析构函数：销毁vector对象，释放其占用的内存。
II、迭代器
- begin()：返回指向vector第一个元素的迭代器。
- end()：返回指向vector最后一个元素之后位置的迭代器（不是最后一个元素）。
- rbegin()：返回指向vector最后一个元素的反向迭代器。
- rend()：返回指向vector第一个元素之前位置的反向迭代器。
- cbegin() 和 cend()：与begin()和end()类似，但返回的迭代器是const类型，不能用于修改元素。
III、容量操作
- size()：返回vector中元素的当前数量。
- max_size()：返回vector能够容纳的最大元素数量（通常是一个很大的值，但具体取决于系统和编译器的实现）。
- capacity()：返回vector当前分配的存储容量，可能大于或等于size()返回的值。
- reserve(n)：请求vector的存储容量至少为n，如果当前容量小于n，则重新分配内存。
- shrink_to_fit()（C++11及以后）：尝试将vector的capacity减少为其当前size的大小，但不一定成功，因为释放内存是可选的。
IV、修改容器
- push_back(value)：在vector的末尾添加一个元素。
- pop_back()：移除vector的最后一个元素。
- insert(pos, value)：在指定位置pos之前插入一个元素value。
- erase(pos)：移除指定位置pos的元素，并返回指向被移除元素之后位置的迭代器。
- clear()：移除vector中的所有元素，使其变为空。
- assign(first, last)：用范围[first, last)内的元素替换vector的内容。
- assign(n, value)：用n个值为value的元素替换vector的内容。
V、元素访问
- operator[]：通过下标访问vector中的元素。
- at(pos)：通过位置pos访问vector中的元素，并进行范围检查。
- front()：返回vector中第一个元素的引用。
- back()：返回vector中最后一个元素的引用。
- data()：返回指向vector中第一个元素的指针（C++11及以后）。
VI、其他操作
- swap(other)：交换两个vector的内容。
- find(value)：在vector中查找值为value的第一个元素，并返回指向该元素的迭代器，如果未找到则返回end()。
- sort()：对vector中的元素进行排序。
- reverse()：颠倒vector中元素的顺序。
三、实现
通过本文，你可以跟随我的思路来了解实现 vector 的底层思路，以及实现的原理。
由于我们将vector实现在一个 .h 文件，并且要实现类模板vector，于是我们先写出框架： 先定义模板参数；
template<typename T> class vector { private: T* _start;//数组的开始位置 T* _finish;//数组内最后一个数据的下一个位置，finish-start表示数组内元素个数 T* _end_of_storage; //数组最后一个能存储元素的下一个位置，end_of_storage - start 表示数组的容量 };
一个类，想要创建一个对象，必须要有构造函数：
STL的vector在实例化之后，默认是已经开辟好了空间，只不过size == 0 ，及内部没有数据而已。
这里我们化繁为简，在构造函数内部不开辟空间，而是在使用或者说对vector对象进行操作的时候再开辟动态空间，于是我们可以直接在变量声明时给默认值并且使用不传参的默认构造函数：
template<typename T> class vector { vector() = default; private: T* _start = nullptr; T* _finish = nullptr; T* _end_of_storage = nullptr; };
push_back是对vector进行最基本的操作，想要实现push_back，则需要考虑扩容逻辑：
如果vector的size（） == capacity （）则表示vector已经满了，需要进行扩容，扩容是多次进行的，我们就单独将扩容用的reserve（）实现出来即可；（上文加黑即为要实现的函数）
size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } //保留空间 void reserve(int n) { //先保存size,防止_start,_finish变化，导致size无法计算 int oldsize = size(); //要求保留的大于现有的，扩容 if (n > capacity()) { T* tem = new T[n]; if (_start) { for (size_t i = 0; i < oldsize; i++) { tem[i] = _start[i]; } } if(_start) delete[] _start; _start = tem; _finish = _start + oldsize; _end_of_storage = _start + n; } //否则，不缩容 }在实现了这些函数之后，就可以实现push_back（）函数的逻辑了。当然，有了尾插，就少不了尾删：pop_back(),由于尾删的逻辑简单，直接给出代码：
//尾插一个T对象 void push_back(const T& t) { if (size() == capacity()) //需要扩容 { //二倍扩容逻辑 int Newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(Newcapacity); //改变capacity,不改变size } //扩容完毕，开始尾插 *_finish = t; ++_finish; } void pop_back() { assert(size() > 0); --_finish; }
STL内的vector是支持迭代器访问的，也就是支持范围for；由于范围for在编译的时候会自动找begin（）和end（），所以我们需要定义迭代器iterator，同时实现begin（），end（），为使用范围for做准备：
//迭代器 typedef T* iterator; typedef const T* const_iterator; iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }
到这里我们发现我们还需要先完善默认的成员函数，默认成员不完善，意味着这个vector使用的是编译器默认生成的成员函数，在大多数情况下会出现问题：
比如：容器内部是指向堆区的指针，使用默认构造会导致浅拷贝的问题。
这就给于我们警示：默认成员函数能自己手动实现，就自己手动实现。
//构造函数，迭代器区间初始化 template<typename inputIterator> //支持任意容器的迭代器初始化:string vector(const inputIterator& begin,const inputIterator& end) //左闭右开 { reserve(end-begin); iterator it = begin; while (it != end) { push_back(*it); ++it; } } //整形匹配 vector(int n, const T& val = T()) { reserve(n); //reserve不改变capacity for (int i = 0; i < n; i++) { _start[i] = val; } //用多少申请多少，size等于容量 _finish = _end_of_storage = _start + n; } //自定义类型匹配 vector(size_t n,const T& val = T()) { reserve(n); for (size_t i = 0; i < n; i++) { _start[i] = val; } } //拷贝构造 vector(const vector<T>& t) //目标，将t深拷贝给*this { reserve(t.capacity()); for (const auto& e : t) { push_back(e); } } void swap(vector<T> tem) { std::swap(_finish, tem._finish); std::swap(_start, tem._start); std::swap(_end_of_storage, tem._end_of_storage); } //赋值重载 vector<T> operator=(const vector<T> tem) //拷贝构造创建一个临时对象，用于交换得到有效数据 // 只要完成拷贝构造即可完成赋值重载 { //现代写法 swap(tem); return *this; } //析构函数 ~vector() { if(_start) delete _start; _finish = _end_of_storage = nullptr; }
接下来我们还需要实现vector内部对象的随机访问，由于vector内部的数据类型是模板，数据类型不能确定，这就需要我们重载 [] 操作符，也就是实现operator[]函数：
//一般类型调用，可读可写 T& operator[](size_t pos) { //空间地址有效 assert(pos < size() && pos >= 0); return _start[pos]; } //const对象调用的，read-only const T& operator[](size_t pos) const { //空间地址有效 assert(pos < size() && pos >= 0); return _start[pos]; }
仅仅有了尾插和尾删是不够的，我们还要实现任意位置的插入删除：
//在pos位置插入对象 iterator insert(iterator pos, const T& t) //由于可能需要扩容，会发生迭代器失效，对内部而言 //迭代器pos在扩容前后指向的对象不再相同，对外部也是同样的会发生 { if (size() == capacity()) //需要扩容 { int len = pos - _start; int Newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(Newcapacity); //改变capacity,不改变size //记录len，解决迭代器失效的问题 pos = _start + len; } //移动对象 iterator end = _finish; while (end != pos) { *end = *(end - 1); --end; } *pos = t; return pos; } //一般不会出现迭代器失效的问题 iterator erase(iterator pos) { iterator oldpos = pos; iterator start = pos + 1; while (start < _finish) { *(start - 1) = *start; ++start; } --_finish; return oldpos; }
接下来，为了避免命名冲突，体现封装，我们要将上述实现的vector封装在我们自己的命名空间中，我的命名空间的名称为：ddsm
STL的vector模拟实现：
#pragma once #include<iostream> #include<cstring> #include<cassert> using namespace std; namespace ddsm { template<typename T> class vector { public: vector() = default; //构造函数，迭代器区间初始化 template<typename inputIterator> //支持任意容器的迭代器初始化:string vector(const inputIterator& begin,const inputIterator& end) //左闭右开 { reserve(end-begin); iterator it = begin; while (it != end) { push_back(*it); ++it; } } //整形匹配 vector(int n, const T& val = T()) { reserve(n); //reserve不改变capacity for (int i = 0; i < n; i++) { _start[i] = val; } //用多少申请多少，size等于容量 _finish = _end_of_storage = _start + n; } //自定义类型匹配 vector(size_t n,const T& val = T()) { reserve(n); for (size_t i = 0; i < n; i++) { _start[i] = val; } } //拷贝构造 vector(const vector<T>& t) //目标，将t深拷贝给*this { reserve(t.capacity()); for (const auto& e : t) { push_back(e); } } 防止迭代器失效 //int _len = t.size(); //int _capacity = t.capacity(); //将原t内容拷贝到tem //iterator tem = new T[_capacity]; //iterator ptem = tem; //iterator start = t._start; //while (start != t._finish) //{ // *ptem = *start; // ++ptem; // ++start; //} tem给*this //_start = tem; //_finish = _start + _len; //_end_of_storage = _start + _capacity; /* iterator tem = new T[capacity()]; iterator ptem = tem; iterator start = t._start; //将原vector内容拷贝到新vector while (start != t._finish) { *ptem = *start; ++ptem; ++start; }*/ void swap(vector<T> tem) { std::swap(_finish, tem._finish); std::swap(_start, tem._start); std::swap(_end_of_storage, tem._end_of_storage); } //赋值重载 vector<T> operator=(const vector<T> tem) //拷贝构造创建一个临时对象，用于交换得到有效数据 // 只要完成拷贝构造即可完成赋值重载 { //现代写法 swap(tem); return *this; } //迭代器 typedef T* iterator; typedef const T* const_iterator; size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } //保留空间 void reserve(int n) { //先保存size,防止_start,_finish变化，导致size无法计算 int oldsize = size(); //要求保留的大于现有的，扩容 if (n > capacity()) { T* tem = new T[n]; if (_start) { for (size_t i = 0; i < oldsize; i++) { tem[i] = _start[i]; } } if(_start) delete[] _start; _start = tem; _finish = _start + oldsize; _end_of_storage = _start + n; } //否则，不缩容 } //尾插一个T对象 void push_back(const T& t) { if (size() == capacity()) //需要扩容 { int Newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(Newcapacity); //改变capacity,不改变size } //扩容完毕，开始尾插 *_finish = t; ++_finish; } //一般类型调用，可读可写 T& operator[](size_t pos) { //空间地址有效 assert(pos < size() && pos >= 0); return _start[pos]; } //const对象调用的，read-only const T& operator[](size_t pos) const { //空间地址有效 assert(pos < size() && pos >= 0); return _start[pos]; } void pop_back() { assert(size() > 0); --_finish; } //在pos位置插入对象 iterator insert(iterator pos, const T& t) //由于可能需要扩容，会发生迭代器失效，对内部而言 //迭代器pos在扩容前后指向的对象不再相同，对外部也是同样的会发生 { if (size() == capacity()) //需要扩容 { int len = pos - _start; int Newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(Newcapacity); //改变capacity,不改变size //记录len，解决迭代器失效的问题 pos = _start + len; } //移动对象 iterator end = _finish; while (end != pos) { *end = *(end - 1); --end; } *pos = t; return pos; } //一般不会出现迭代器失效的问题 iterator erase(iterator pos) { iterator oldpos = pos; iterator start = pos + 1; while (start < _finish) { *(start - 1) = *start; ++start; } --_finish; return oldpos; } //析构函数 ~vector() { if(_start) delete _start; _finish = _end_of_storage = nullptr; } private: iterator _start = nullptr; iterator _finish = nullptr; iterator _end_of_storage = nullptr; }; //非成员函数，流插入 ostream& operator<<(ostream& out, vector<int> v) { for (const auto& e : v) { cout << e << " "; } cout << endl; return out; } };
完·~
未经作者同意禁止转载