目录
构造与析构
模拟实现时，依然使用vector作为容器的名字，为了防止与std命名空间中的vector冲突，使用自定义的命名空间，将模拟实现的类放入即可。vecotr容器中可以存储多种类型的值，所以需要使用模板的方式。类的实现方法也有多种，以下实现采用三指针的方式，比如容器中的有效元素是两个，容量为6，那么其内部结构下图：
给出三种构造函数，无参构造函数、n个元素的构造函数、给定迭代器(类似于指针，以下代码默认为指针)区间的构造函数。代码如下：
namespace gss{
template <class T>
class vector{
public:
typedef T* iterator;
vector()
:_start(nullptr)
, _finish(nullptr)
, _end_ofStorage(nullptr)
{
}
vector(size_t n, const T& value = T())//n个元素的构造函数
:_start(nullptr)
, _finish(nullptr)
, _end_ofStorage(nullptr)
{
_start = new T[n];//开辟新空间
_finish = _start;
_end_ofStorage = _start + n;
for (size_t i = 0; i < n; i++){//将n个元素放进去
*_finish = value;
++_finish;
}
}
template <class Iterator>//因为给定的迭代器类型不能确定，所以也使用模板的方式
vector(Iterator first, Iterator last)//给定区间构造
:_start(nullptr)
, _finish(nullptr)
, _end_ofStorage(nullptr)
{
int n = 0;//不能直接用last-first得到n，因为从first到last的这段区间可能不连续
Iterator temp = first;
while (temp != last){
n++;
temp++;
}
_start = new T[n];//开辟新空间
_finish = _start;
_end_ofStorage = _start + n;
while (first != last){//将n个元素放进去
*_finish = *first;
_finish++;
first++;
}
}
~vector(){
if (_start){//如果_start不空，在释放资源
delete[] _start;
_start = nullptr;
_finish = nullptr;
_end_ofStorage = nullptr;
}
}
private:
iterator _start;
iterator _finish;
iterator _end_ofStorage;
};
}构造函数比较简单，就是开辟新空间，将给定的元素放入申请的这段空间中就可以。需要注意的是：给定迭代器区间构造的过程中，不能使用给定的两个迭代器直接做减法，因为这两个迭代器可能是链表的，也就是说底层空间不连续。
以下给出的代码都放在命名空间gss中的vector类中。
简单方法的模拟
如下是迭代器、计算元素个数、计算容量、以及[]重载的模拟：
iterator begin(){//返回指向第一个元素的迭代器
return _start;
}
iterator end(){//该迭代器指向末尾元素的下一个位置
return _finish;
}
size_t size()const{//返回有效元素个数
return _finish - _start;
}
size_t capacity()const{//返回容量
return _end_ofStorage - _start;
}
T& operator[](size_t i){//重载[]，返回值为引用类型
assert(i < capacity());
return *(_start + i);
}
const T& operator[](size_t i)const{
assert(i < capacity());
return *(_start + i);
}拷贝构造与赋值运算符重载
浅拷贝问题
如下代码，如果在拷贝构造的时候，仅仅只是将arr中变量的值拷贝给arr1，那么在这两个对象中的_start指针将会指向同一块空间，在最后对象声明周期结束后调用析构函数时，_start指向的空间将会被释放两次，运行直接报错。浅拷贝后
深拷贝
vector容器中的拷贝构造与赋值运算符重载都是深拷贝，也就是说要把原来对象中指针_start指向的空间中的内容拷贝一份，然后让新对象中_start指针以及其他指针指向新的空间，代码如下：
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_ofStorage(nullptr)
{
_start = new T[v.capacity()];//开辟新空间
_finish = _start;
_end_ofStorage = _start+v.capacity();
T* temp = v._start;
for (; temp != v._finish;temp++){//拷贝原对象指针指向的空间中所有的值
*_finish = *temp;
_finish++;
}
}赋值运算符重载也可以使用类似于以上的方式给出，完成深拷贝，但是这样代码显得有点重复，接下来使用一种比较简洁的思路给出代码：
void swap(vector<T> s){
std::swap(_start,s._start);
std::swap(_finish, s._finish);
std::swap(_end_ofStorage, s._end_ofStorage);
}
vector<T>& operator=(vector<T> s){//在传递参数时，会调用拷贝构造，构造出对象s
swap(s);
return *this;
}看到这段代码，很多同学心里会有疑惑，这么简单一段代码就完成了赋值运算符重载？
我们来分析一下以上代码，调用赋值运算符重载的时候，s是一个形参，也就是说传递参数的时候s是调用拷贝构造构造出来的临时对象，那么只需要让s中的指针与被赋值对象中的指针交换即可，用一副简图来理解一下：
而且交换完成以后，临时对象出了函数作用域生命周期会结束，在生命周期结束后，编译器会自动调用析构函数来释放临时对象的资源，所以也不用担心内存泄漏。
?扩容
reserve()
vector容器可以手动扩容，与扩容有关的函数主要有resize()与reserve()方法，所以也模拟实现一下这两个函数。
reserve()函数是将增加对象的容量，并不改变有效元素的个数，如果要扩容的容量小于原来对象的容量，则不做处理。代码如下：
void reserve(size_t n){
if (n>capacity()){
size_t oldsize = size();
T* temp = new T[n];//申请新空间
//memcpy(temp,_start,size);注意不能使用memcpy
if (_start){//先判断旧空间中有没有元素
for (size_t i = 0; i < oldsize; i++){//拷贝旧元素
temp[i] = _start[i];
}
delete[] _start;//释放旧空间
}
_start = temp;//指向新空间
_finish = _start +oldsize;
_end_ofStorage = _start + n;
}
}这段代码要注意两个点：
第一点就是首先需要调用size()，将原空间有效元素个数保存起来，因为_finish最后的指向需要在_start的位置上加上原空间有效元素的个数。
第二点：在拷贝旧空间元素时，不能使用memcpy()函数进行拷贝。如果vector容器中保存的是基本类型的变量，那么使用memcpy()没有问题。如果保存的是string类型（底层也使用指针）的变量，此时使memcpy()进行拷贝只是将gss::vector<string>容器中_start所指向的内容拷贝了一份，而这些被拷贝的内容只是string类对象中的指针以及其它值，真正的字符串并没有被拷贝。下图表示对gss::vector<string>类型对象扩容时，在reserve函数中使用memcpy()的结果：
很明显，扩容后容器中的string类型对象中的指针还是指向了原来的空间，但是原来的空间在拷贝结束后就被释放掉了。所以说memcpy()在这里是不能使用的。
那为什么循环的方式就可以呢？
因为temp[i] = _start[i];这句代码对于string类型的对象可以调用他们的赋值运算符重载，完成深拷贝。
resize()
resize()的作用是改变对象有效元素的个数，在C++库中对resize的定义是这样的：
?如果n小于有效元素的个数，那么直接将有效元素个数改为n个。如果n大于有效元素个数，但是小于容量,那么有效元素个数改为n，n个元素中默认值的部分直接补成val。如果n大于容量，那么先扩容，在将有效元素个数改为n，n个元素中默认值的部分直接补成val。
代码实现如下：
void resize(size_t n, T value = T()){
if (n<size()){//n小于原有效元素个数，直接修改有效元素个数
_finish = _start + n;
}
else{
if (n>capacity()){
reserve(n);
}
iterator it = _finish;
_finish = _start + n;
while (it != _finish){
*it = value;
it++;
}
}
}插入与删除
push_back()
尾插是比较简单的，但是要注意的是需要判断容量是否够用，以及刚开始容量为0时，第一次扩容问题。代码如下：
void push_back(const T& value){
if (size() == capacity()){
reserve(capacity() == 0 ? 2 : capacity() * 2);//容量为0时，将其扩容为2
}
*_finish = value;
_finish++;
}insert()
insert是在任意位置插入n个元素，第一个参数是迭代器类型的。其中一种的模拟实现如下：
void insert(iterator position, size_t n, T& val){
if (n<=0){
return;
}
int oldsize = size();//记录原对象中有效元素个数
iterator it = _start;
int count = 0;//记录要插入的位置与第一个位置相差的个数
while (it != position){
it++;
count++;
}
size_t len = size() + n;
if (len > capacity()){//有效元素个数超出了容量，需要扩容
reserve(len);
position = _start + count;//更新position，防止失效
}
_finish = _finish + n;//将_finish放在正确的位置
for (int i = oldsize - 1; i >= count;i--){
_start[i + n] = _start[i];
}
while (n>0){//开始插入
n--;
_start[count++] = val;
}
}?注意：扩容后position就失效了，需要及时更新,然后在插入元素。
erase()
erase是删除对象中的元素，来实现其中的一种。
iterator erase(iterator position){
iterator it = position;
_finish = _finish - 1;
while (it!=_finish){
*it = *(it + 1);
it++;
}
return position;
}注意:该函数的返回值是要删除的元素下一个位置元素对应的迭代器。
