💐专栏导读

🌸作者简介：花想云，在读本科生一枚，致力于 C/C++、Linux 学习。

🌸本文收录于 C++系列，本专栏主要内容为 C++ 初阶、C++ 进阶、STL 详解等，专为大学生打造全套 C++ 学习教程，持续更新！

🌸相关专栏推荐：C语言初阶系列 、C语言进阶系列 、数据结构与算法

💐文章导读

本章我们将参照STL源码来模拟实现vector，这要求我们具备数据结构的基础且了解vector的基本使用。模式实现vector，将锻炼我们的代码能力，加深对类和对象的认识，同时能使我们对vector的使用更加游刃有余。

🌷定义vector类

为了区别于标准库中的vector，我们可以使用自己的命名空间，在自己的命名空间中模拟实现vector。我们已经了解过库中vector的基本使用，知道vector是一个可以存储任何类型的容器，为了实现各种类型都可以匹配，我们可以利用模板来实现。

STL源码中，vector包含三个基本成员：

• iterator _start：指向首元素的迭代器；
• iterator _finish：指向尾元素下一位的迭代器；
• iterator _end_of_storage：指向最大容量的下一位的迭代器；

我们可以把迭代器理解为像指针一样的东西。

namespace hxy
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start;iterator _finish;iterator _end_of_storage;};
}

🌷各成员函数的实现

🌺构造函数

	vector():_start(nullptr),_finish(nullptr),_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与capacity——求大小与容量

	size_t size() const{return _finish - _start; //指针相减即为个数}size_t capacity() const{return _end_of_storage - _start;}

🌺reserve——扩容

	void reserve(size_t n){if (n > capacity()){size_t sz = size();//使用中间变量，防止new失败iterator tmp = new T[n];if (_start){//转移数据for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}//释放旧空间delete[] _start;}//指向新空间_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}

关于reserve中的深浅拷贝问题

在reserve的实现中，我们不能使用memcpy来拷贝数据，否则会发生浅拷贝的问题，导致在析构报错。对于简单的内置类型或自定义类型，memcpy是一个不错的选择，既高效又实用。但是一旦元素涉及到资源申请，memcpy只是简单的将一个元素的值拷贝给另一个元素，并不会将该元素指向的空间的内容全部拷贝给另一个元素。所以，我们必须手动实现深拷贝。

🍁错误示例

	void reserve(size_t n){if (n > capacity()){size_t sz = size();//使用中间变量，防止new失败iterator tmp = new T[n];if (_start){//浅拷贝memcpy(tmp, _start, sizeof(T)*size());delete[] _start;}//指向新空间_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}

🌺resize——扩容并初始化

	void resize(size_t n, T val = T()){//n<size()，删除数据if (n < size()){_finish = _start + n;}else{if (n > capacity)reserve(n); //扩容while (_finish != _start + n){//初始化*_finish = val;++_finish;}}}

🌺push_back——尾插

	void push_back(const T& val){//扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}//插入元素*_finish = val;++_finish;}

🌺pop_back——尾删

	void pop_back(){assert(!empty());--_finish;}

🌺insert——插入

	iterator insert(iterator pos,T val=T()) //使用匿名构造{assert(pos >= _start);assert(pos <= _finish);//扩容if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);//扩容后更新pos的位置，解决pos失效的问题pos =_start + len;}//挪动数据iterator end = _finish-1;while (end >= pos){*(end + 1) = *end;--end;}//插入元素*pos = val;++_finish;return pos;}

🌺erase——删除

	iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);//挪动数据iterator end = pos + 1;while (end != _finish){*(end - 1) = *end;++end;}--_finish;return pos;}

🌺empty——判空

	bool empty(){return size() == 0;}

🌺[]重载——访问元素

	T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}

🌺传值构造

	vector<int> v1(10, 5); //用10个5来构造

	vector(size_t n, const T& val = T()):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){//扩容reserve(n);//尾插for (size_t i = 0; i < n; i++){push_back(val);}}//重载版本，防止调用时与迭代器区间构造混淆vector(int n, const T& val = T()):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}

🌺迭代器区间构造

	vector<int> v1(10, 5); vector<string> v2(v1.begin(), v1.end()); //迭代器区间构造

	template<class InputIterator>vector(InputIterator begin, InputIterator end){//扩容reserve(end - begin);while (begin != end){push_back(*begin);++begin;}}

🌺赋值重载

	void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vector<T>& operator=(vector<T> v){swap(v);return*this;}

🌺拷贝构造

	vector(const vector<T>& v){//写法1//_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();//写法2vector<T> tmp(v.begin(), v.end());swap(tmp);}

拷贝构造中的深浅拷贝问题

在写法1中，如果使用memcpy，同样会发生浅拷贝的问题。

🍁错误示例

		vector(const vector<T>& v){_start = new T[v.capacity()];//浅拷贝memcpy(_start, v._start, sizeof(T)*v.size());_finish = _start + v.size();_end_of_storage = _start + v.capacity();}

🌺析构函数

	~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}

完整源码

#include<iostream>
#include<assert.h>
using namespace std;
namespace hxy
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}vector(size_t n, const T& val = T()):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){//扩容reserve(n);//尾插for (size_t i = 0; i < n; i++){push_back(val);}}vector(int n, const T& val = T()):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vector<T>& operator=(vector<T> v){swap(v);return*this;}vector(const vector<T>& v){//写法1_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();写法2//vector<T> tmp(v.begin(), v.end());//swap(tmp);}template<class InputIterator>vector(InputIterator begin, InputIterator end){reserve(end - begin);while (begin != end){push_back(*begin);++begin;}}~vector(){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;}void reserve(size_t n){if (n > capacity()){size_t sz = size();//使用中间变量，防止new失败iterator tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * size());//转移数据for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}//释放旧空间delete[] _start;}//指向新空间_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}void resize(size_t n, T val = T()){//n<size()，删除数据if (n < size()){_finish = _start + n;}else{if (n > capacity)reserve(n); //扩容while (_finish != _start + n){//初始化*_finish = val;++_finish;}}}void push_back(const T& val){//扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}//插入元素*_finish = val;++_finish;}void pop_back(){assert(!empty());--_finish;}iterator insert(iterator pos,T val=T()) //使用匿名构造{assert(pos >= _start);assert(pos <= _finish);//扩容if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);//扩容后更新pos的位置，解决pos失效的问题pos =_start + len;}//挪动数据iterator end = _finish-1;while (end >= pos){*(end + 1) = *end;--end;}//插入元素*pos = val;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);//挪动数据iterator end = pos + 1;while (end != _finish){*(end - 1) = *end;++end;}--_finish;return pos;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}bool empty(){return size() == 0;}private:iterator _start;iterator _finish;iterator _end_of_storage;};
}