目录
定义vector类
各成员函数的实现
构造函数
迭代器
size与capacity——求大小与容量
reserve——扩容
关于reserve中的深浅拷贝问题
resize——扩容并初始化
push_back——尾插
pop_back——尾删
insert——插入
erase——删除
empty——判空
[]重载——访问元素
传值构造
迭代器区间构造
赋值重载
拷贝构造
拷贝构造中的深浅拷贝问题
析构函数
完整源码
文章导读
本章我们将参照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(); //写法2 vector<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; }; }
