vector的模拟实现

一、vector的简单使用

vector的各种接口其实是和string是差不多的，你能熟练的使用string了之后，vector自然就通了。

二、vector迭代器失效问题

1、insert插入元素迭代器失效及解决办法

在上期string的模拟实现中，我们在vs和g++编译器中，分别查看string的扩容情况，我们也来看看，vector在两个不同的编译器下的扩容情况：

#include <iostream>
#include <vector>
using namespace std;
int main()
{vector<int> vc;size_t oldCapacity = vc.capacity();cout << "起始的容量是：" << oldCapacity << endl;int i = 0;while(i < 100){if(oldCapacity < vc.capacity()){cout << "扩容后:" << vc.capacity() << endl;oldCapacity = vc.capacity(); }vc.push_back(i++);}return 0;
}

• 在g++上

• 在vs上

可以看到vector的扩容机制和string是一样的，在g++上是2倍扩容，而在vs上大约是1.5倍扩容，只不过它们的其实容量是不一样的。

了解了vector的扩容机制后，我们就可以来看看insert迭代器失效问题了。

int main()
{vector<int> vc;vc.push_back(1);vc.push_back(2);vc.push_back(3);vc.push_back(4);auto pos = vc.begin();vc.insert(pos + 2, 5);vc.insert(pos + 2, 6);    // 这段代码会出现错误return 0;
}

运行结果：

这里错误表示重复释放内存或者内存损坏。

为什么会出现这种情况呢？这其实就是扩容导致的，我们画图来理解一下。

为了避免insert的迭代器失效，insert有返回值来解决该问题。

它的返回值是当前新插入位置的迭代器。

解决办法：

于是我们每次使用了insert后，获取它的返回值，这样就可以避免迭代器失效了。

#include <iostream>
#include <vector>
using namespace std;
int main()
{vector<int> vc;vc.push_back(1);vc.push_back(2);vc.push_back(3);vc.push_back(4);auto pos = vc.begin();pos = vc.insert(pos + 2, 5);   // 改进代码vc.insert(pos + 2, 6);for(auto e : vc){cout << e << " ";}cout << endl;return 0;
}

2、erase删除元素后迭代器失效及解决办法

首先，erase是删除元素，不会影响vector的容量变化，所以erase迭代器失效的问题和insert是完全不一样的。

2.1、g++中

实例：我们想在vector中删除所有的偶数。

#include <iostream>
#include <vector>
using namespace std;
int main()
{vector<int> vc;vc.push_back(1);vc.push_back(2);vc.push_back(2);vc.push_back(3);vc.push_back(5);cout << "删除前的序列：";for(auto e : vc){cout << e << " ";}cout << endl;auto it = vc.begin();while(it != vc.end()){if(*it % 2 == 0){vc.erase(it);}it++;}cout << "删除后的序列：";for(auto e : vc){cout << e << " ";}cout << endl;return 0;
}

可以看到没有得到我们想要的结果，还有个2没有被删除。

那在vector中再插入一点数呢？vc.push_back(6);

可以看到出现了段错误，为什么会出现这种情况呢？

当中间有连续的偶数时，会删除不成功，而当最后一个数是偶数时，it会出现越界，而循环判断条件是it != vc.end()，自然会迭代器失效了。

而erase同样具有返回值，我们需要获得erase的返回值，这样就可以删除成功了。

修改代码：

auto it = vc.begin();
while(it != vc.end()){if(*it % 2 == 0){it = vc.erase(it);  // 删除成功返回返回值}else{it++;              // 不是偶数才执行it++语句}}

2.2、vs中

刚刚在g++中，我们第一种情况删除连续偶数没有成功，但是没有报错，程序是成功运行了的，但是在vs中，它进行了强制检查，只要使用了erase(it)，it迭代器就会失效，就会报错。

所以不管是在g++中还是vs中，我们都要给erase返回值，以防迭代器失效。

三、vector深度剖析及模拟实现

1、模拟实现的接口总览

namespace csj
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;// 默认成员函数vector();                              // 构造函数vector(int n, const T& val = T())      // 构造函数template <class InputIterator>         // 模版中还可以嵌套模版vector(InputIterator first, InputIterator last);   // 迭代器构造函数vector(const vector<T>& v);vector<T>& operator=(vector<T> tmp);~vector();// 迭代器相关函数iterator begin();iterator end();const_iterator begin() const;const_iteraot end() const;// 容量相关的函数size_t size() const;size_t capacity() const;void reserve(size_t n);void resize(size_t n, const T& val = T());bool empty() const;// 修改容器内容相关的函数void push_back(const T& x);void pop_back();void insert(iterator pos, const T& x);iterator erase(iterator pos);void swap(vector<T>& tmp);// 访问容器相关的函数const T& operator[](size_t pos) const;// 成员变量private:private:// 有些编译器对内置类型不处理，所以我们还是要给缺省值iterator _start = nullptr;       // 指向容器的开始iterator _finish = nullptr;      // 指向容器有效内容的尾iterator _endofstorage = nullptr;// 指向容器容量的尾};
}

2、vector中的三个成员变量

iterator _start = nullptr;       // 指向容器的开始
iterator _finish = nullptr;      // 指向容器有效内容的尾
iterator _endofstorage = nullptr;// 指向容器容量的尾

因为源码也叫这三个名字，所以我们模拟实现也跟着源码走。

iterator是typedef出来的，它是T*，所以这三个成员变量都是指针类型。

而且为了方便写构成函数时，我们都要单独初始化这三个变量，所以我们给上缺省值。

3、vector中的三种构造函数

3.1、无参的构造函数

vector(){}   

3.2 、迭代器区间的构造函数

vector中不仅可以存放int，其他各种类型的数据（string，vector，char，double等等）都可以存放，所以我们也不知道具体存放什么内容，所以这里使用了函数模版。

template <class InputIterator>  
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);    // 每次尾插到新的vector中即可first++;}
}

3.3、n个val值的构造函数

vector(size_t n, const T& val = T())
{reserve(n);    // 因为知道了是n个数，所以可以先开n个大小的空间，减少扩容，提高效率for (size_t i = 0; i < n; i++){push_back(val);    // 同样尾插到末尾}
}

这里说说，第二个参数const T& val = T()中的T()是什么意思？其实这里就是缺省参数，因为我们不知道插入的val是什么类型的，自定义类型还是内置类型，对于自定义类型就是相当于调用无参的构造函数，如string()；但是对于内置类型是什么呢？int()，其实在c++中内置类型也可以看作是一个类，它们也有自己的默认构造函数，而这里的int()就是0。

所以c++中万物皆对象！

4、vector的拷贝构造函数

4.1 浅拷贝问题

void reserve(size_t n)
{if (n > capacity())      //  当n > capacity，才进行开辟新空间{size_t sz = size();  // 提前保存下来T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * sz);  // 会出现浅拷贝delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}
}

当reserve的时候，就是需要开辟新的空间，然后将原来的值拷贝到新空间，释放旧空间。但是我们不能使用memcpy来拷贝内容：

当vector存放的内置类型，这样当然没有问题，但是当vector中的是内置类型（string）就会出现问题。

如果此时我们使用memcpy拷贝构造的话，它仅仅只是复制指针，而不是复制指针指向的内容。

这样又会出现同一块空间，连续析构两次的问题，所以我们要进行深拷贝。

4.2 深拷贝问题

深拷贝就是我们手动的一个一个赋值过去。

for (size_t i = 0; i < sz; i++)
{tmp[i] = _start[i];   // 深拷贝
}

拷贝构造函数：

vector(const vector<T>& v)
{reserve(v.capacity());   // 可以不写，push_back中可以扩容，但是先reserve可以减少扩容带来的消耗for (size_t i = 0; i < v.size(); i++){push_back(v[i]);     // 同样尾插到新的vector中即可}
}

5、赋值运算符重载函数（复用拷贝构造函数）

vector<T>& operator=(vector<T> tmp)  // 这里的传参会调用拷贝构造
{swap(tmp);return *this;
}

这里的赋值运算符重载函数上次说的string的赋值运算符重载函数是一样的写法，都是现代写法。

6、析构函数

~vector()
{delete[] _start;       // 注意这里的_start是像数组一样使用的，所以要用delete []_start = _finish = _endofstorage = nullptr;
}

7、迭代器相关的接口

begin和end

这里的begin和end有两种，一个是普通的迭代器，也就是可读，可修改。还有一个是重载出来的const迭代器，只能读。

普通迭代器：

iterator begin()
{return _start;     // 返回容器的首地址
}
iterator end()
{return _finish;    // 返回最后一个数据的下一个位置的地址
}

const迭代器：

const迭代器供const对象使用的。

const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}

8、容量相关的接口

size和capacity

在C语言中，同一数组中的元素的指针相减就可以得到它们之间的元素个数，而这里正好满足。

size_t size() const
{return _finish - _start;    // 指针-指针 = 个数
}
size_t capacity() const
{return _endofstorage - _start;
}

reserve

void reserve(size_t n)
{if (n > capacity()){size_t sz = size();  // 提前保存下来T* 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;_endofstorage = _start + n;}
}

resize

resize同样是改变size的大小，也可能会改变capacity的大小。

• 当n <= size()的时候，就是尾删。
• 当n > size()的时候，就是尾插值。

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;}}
}

empty

当没有值的时候，自然_finish 和 _start是相等的。

bool empty() const
{return _finish == _start;
}

9、修改容器内容相关的接口

push_back

对于尾插，你可以自己写，但是要注意此时是否为空，为空了，你就要进行扩容操作。或者你复用insert的代码（推荐）。

void push_back(const T& x)
{/*if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;*/insert(_finish, x);   // 直接复用insert
}

pop_back

在尾删的时候，先断言操作，强制处理，没有元素了后，还在尾删，程序直接崩。

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

insert

注意之前我们说的insert迭代器失效是，扩容导致原来空间失效了，故而原来迭代器失效了，但是下面的代码单独的处理了这种情况，也就不会迭代器失效了。

void insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);// 插入数据之前先判断扩容if (_finish == _endofstorage){size_t len = pos - _start;     // 防止扩容后，迭代器失效，先记录下来。reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;            //  然后再计算当前迭代器的位置}iterator end = _finish - 1;       // 最后一个元素的位置while (end >= pos){*(end + 1) = *end;end--;}*pos = x;_finish++;}

erase

erase后迭代器会失效，所以要有返回值。

iterator erase(iterator pos)
{assert(pos >= _start);    // 断言pos是否符合assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;   // 依次移动数据进行覆盖it++;}_finish--;             // 删除了值后，_finish记得--return pos;
}

swap

为了交换两个容器的值，我们使用库中的swap进行操作，一定要记得要使用std::。这个函数是为了给现代写法的赋值运算符重载函数使用的。

void swap(vector<T>& tmp)
{std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_endofstorage, tmp._endofstorage);
}

10、访问容器相关的接口

operator[]

和迭代器差不多，我们重载两个版本出来，一个是非const版本，可读可写；另一个是const版本，可读不可写。

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模拟实现的全部代码

namespace csj
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;vector(){}vector(const vector<T>& v){reserve(v.capacity());   // 可以不写，push_back中可以扩容，但是先reserve可以减少扩容带来的消耗for (size_t i = 0; i < v.size(); i++){push_back(v[i]);}}template <class InputIterator>  // 模版中还可以嵌套模版vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}vector(size_t n, const T& val = T())   // 参数的类型不同，构成重载{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}void swap(vector<T>& tmp){std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_endofstorage, tmp._endofstorage);}vector<T>& operator=(vector<T> tmp)  // 这里的传参会调用拷贝构造{swap(tmp);return *this;}void reserve(size_t n){if (n > capacity())      // 当n > capacity，才进行开辟新空间{size_t sz = size();  // 记录当前元素个数T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz);  // 会出现浅拷贝for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];  }delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}// 这里要使用构造函数，因为不知道vector中的元素是int，double，还是string等等。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;}}}void push_back(const T& x){/*if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;*/insert(_finish, x);}void pop_back(){assert(!empty());_finish--;}void insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);// 插入数据之前先判断扩容if (_finish == _endofstorage){size_t len = pos - _start;     // 防止扩容后，迭代器失效，先记录下来。reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;           //  然后再计算当前迭代器的位置}iterator end = _finish - 1;      // 最后一个元素的位置while (end >= pos){*(end + 1) = *end;end--;}*pos = x;_finish++;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;it++;}_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];}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 _endofstorage - _start;}bool empty() const{return _finish - _start;}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}private:iterator _start = nullptr; // 有些编译器对内置类型不处理，所以我们还是要给缺省值iterator _finish = nullptr;iterator _endofstorage = nullptr;};
}