C++ vector 之 【模拟实现vector须知、完整的模拟实现 】

1.模拟实现vector须知

(1)C++标准库实现的vector存放在命名空间std中，为了避免冲突

我们模拟实现vector时，需要创建一个新的命名空间存储我们自己模拟实现的vector

(2)模板的完整定义通常应该放在头文件中(具体原因后续讲解)

vector是一个类模板

所以模拟实现时，我将在.h文件中完整模拟实现vector
(3)vector可以被理解为一个动态数组，模拟实现一个动态数组时，

我们选择在堆上去申请空间，选择用指针显示管理这块内存，指针就可以作为成员变量

空间上所存储数据的数据类型是什么呢，所以需要指定数组元素的数据类型，

但是，为了所实现的代码能够适用于多种数据类型(即满足泛型编程)

模拟实现vector时将元素的数据类型视为一个模板参数(为了方便叙述，将其命名为T)，

2.完整模拟实现 

2.1成员变量

如上图(取自侯捷老师的STL源码剖析)

start 变量指向动态数组的第一个元素位置

finish 变量指向动态数组的最后一个元素的下一个位置

end_of_storage 变量指向动态数组空间的最后一个位置的下一个位置

这些指针变量的类型都是 T* （T代表的是元素的数据类型）

vector中的迭代器就是 指针的别名

namespace dfq
{template<class T>class vector{typedef T* iterator;//成员函数public://成员变量private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};
}

(1)在成员变量声明之后给定一个缺省值，

这样，我们在书写构造函数时就可以减少书写初始化成员变量的步骤

(2)而且vector中的三个指针初始值都为空

 2.2模拟实现vector中的迭代器及[ ]操作符

typedef T* iterator;
iterator begin()
{return _start;
}iterator end()
{return _finish;
}
typedef const T* const_iterator;
const_iterator begin()const
{return _start;
}const_iterator end()const
{return _finish;
}T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}const T& operator[](size_t pos)const
{assert(pos < size());return _start[pos];
}

(1)vector中，迭代器(iterator)就是指针的别名，我们模拟实现的时候也这样干

注意：普通对象的迭代器和const对象的迭代器不同

因为普通对象可读可修改，const对象只可读

(2)重载[ ]操作符时也要注意普通对象与const对象的区别，并检查下标的有效性

2.3.模拟实现vector中的无参构造函数

vector(){}

(1)我们在成员变量声明时给定了缺省值，所以只需要写一个"空"的无参构造函数

实际上，编译器还是会去走该构造函数的初始化列表，并初始化相应成员变量

(2)此函数不可不写，因为后续我们将模拟实现其他种类的构造函数(不包含全缺省构造函数)

实现其他种类的构造函数且没有无参构造函数之后，我们就不能创建一个空的vector对象

这与真实的vector不符，具体原因就是：

实现其他种类的构造函数且没有无参构造函数后，编译器不会自动生成一个构造函数

那么创建一个空对象时就没有合适的默认构造函数可以被调用，编译器就会报错

2.4模拟实现vector中的析构函数

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

(1)释放空间，并置空相应变量

2.5.模拟实现vector中的 size、capacity 函数

size_t size()const
{return _finish - _start;
}
size_t capacity()const
{return _end_of_storage - _start;
}

(1)指针相减就是元素个数，这里计算的并不是空间占多少个字节

(2)两个函数必须加上cosnt修饰，

因为不管是普通对象还是const对象都可能需要调用这两个函数

加上cosnt修饰之后，不管是普通对象还是const对象都可以调用这两个函数

如果不加，只有普通对象可以调用这两个函数，与真实不符

 2.6.模拟实现vector中的 reserve 函数

void reserve(size_t n)
{if (n > capacity()){size_t old_size = _finish - _start;iterator temp = new T[n];//拷贝数据注意潜在的深拷贝问题for (size_t i = 0; i < size(); ++i){temp[i] = _start[i];}delete[] _start;_start = temp;_finish = _start + old_size;_end_of_storage = _start + n;}
}

(1)reserve函数只扩容不缩容

所以只有当所需要的空间大小大于 当前容量时，才会进行扩容操作

(2)n 指的是元素个数，需要开辟 n 个元素所占据的的空间，只需要 new T[n] 并返回起始位置的指针，而不需要像使用 malloc 一样需要计算总共的大小

(3)真实空间申请涉及内存池等内容，

为了理解以及实现的简单，模拟实现vector时直接使用操作符new申请空间即可

(4)扩容时需要将原有数据拷贝到新开辟的空间上，这里需要注意隐藏的深拷贝问题

for (size_t i = 0; i < size(); ++i)
{temp[i] = _start[i];
}

如果是内置类型，对应下标的元素直接进行赋值即可

如果是自定义类型，会去调用相应对象的赋值重载函数以防止浅拷贝问题

如果选择以往的memcpy就行逐字节的拷贝

memcpy(_start, v._start, sizeof(T) * v.size()); wrong

就会出现下面的问题

(1)新开辟的空间与原有空间对应的元素对象指向同一块内容，那么

当原有空间销毁时，对象指向的内容也会被销毁，此时新开辟的空间中的元素对象就会指向释放的空间，内容就会是一团乱码，不符合我们的预期

(2)所以为了防止这种情况，需要调用赋值重载函数，赋值重载函数就是一次深拷贝

我们这里调用了赋值重载函数，如果用户的自定义类型没有显示定义赋值重载函数

那么扩容出错的锅得用户自己背

 

(5)扩容之后所有的迭代器失效，需要重新指定或获取

_finish = _start + old_size;//right
_finish = _start + size();//wrong

因为size函数的内部实现依赖于_finish，_start，而此时的_start已经改变，_finish仍指向原来的空间，所以此时调用的size函数的返回值就不正确

解决方法就是提前保存一下长度

size_t old_size = _finish - _start;

2.7 模拟实现vector中的 push_back 函数

void push_back(const T& val)
{//首先判断扩容if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = val;++_finish;
}

 (1)首先判断一下是否扩容，然后插入值并改变_finish的位置即可

 2.8.模拟实现vector中的 insert 函数

iterator insert(iterator pos, const T& val)
{//检查位置有效性assert(pos >= _start && pos <= _finish);//扩容，导致迭代器失效if (_finish == _end_of_storage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}//挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = val;++_finish;return pos;
}

(1)insert函数的含义就是在pos位置插入一个值，其中 pos的类型是 T* (即迭代器)

此时就需要先检查pos位置的有效性，pos可以等于_finish，即尾插

(2)判断是否扩容，需要注意的是，扩容会导致所有迭代器失效，包括pos

解决方法就是 存储 pos位置的相对位置

size_t len = pos - _start;
...
pos = _start + len;

(3)然后挪动数据，插入值，改变_finish 的值

(4)insert函数选择返回 插入位置的迭代器，方便后续重新获取迭代器

2.9 模拟实现vector中的 erase 函数

iterator erase(iterator pos)
{//检查位置有效性assert(pos >= _start && pos < _finish);//挪动数据iterator next = pos + 1;while (next != _finish){*(next - 1) = *next;++next;}//数量减一--_finish;return pos;
}

(1)与insert一样，erase函数中 pos的类型是 T* (即迭代器)

此时也需要先检查pos位置的有效性，

(2)然后挪动数据，插入值，改变_finish 的值

(3)erase函数选择返回 删除位置的迭代器，方便后续重新获取迭代器

2.10  pop_back函数

void pop_back()
{erase(_finish - 1);
}

复用erase函数即可

2.11 resize函数

void resize(size_t n, const T& val = T())
{//讨论三种情况//size     capacity     n//5          10          3//5          10          8//5          10          13if (n < size()){_finish = _start + n;}else{//后两种情况合二为一reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}
}

(1)resize函数会改变容器中的元素个数，并初始化添加的元素，初始值都带有缺省值

这里需要注意，内置类型的缺省值一般是0、nullptr，

自定义类型的缺省值一般是由默认构造函数创建的对象，

这里的 T() 就是创建一个 T类型的临时对象

C++中的内置类型也适用于 T() 表达式

(2)如注释一样，实现resize函数需要考虑三种情况

//size     capacity     n
    //5          10          3
    //5          10          8
    //5          10          13

第一种情况 所需元素个数n小于当前元素个数size时，

直接更改_finish的位置即可(一般不抹除值)

第二三种情况合在一起，先判断是否开空间，然后添值即可

2.14 拷贝构造函数

vector(const vector<T>& v)
{reserve(v.capacity());for (size_t i = 0; i < v.size(); ++i){_start[i] = v._start[i];}_finish = _start + v.size();
}

(1)直接调用reserve函数开好空间

(2)注意隐藏的深拷贝问题，选择使用=，而不是memcpy拷贝数据

(3)因为*this对象三个成员变量初始值都为空，reserve函数开好空间之后 _finish仍为空

所以拷贝好数据之后需要改变 _finish 的值

2.13 赋值重载函数

//v1 = v2;
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;
}

v1 = v2

(1)赋值重载函数的参数不用引用，

使得函数传参时就会调用拷贝构造函数，v 即是 v2 的深拷贝

然后将 对象v 与 *this对象进行交换， 函数调用完毕之时

*this 对象 成功被赋值， *this对象原有的资源也被成功释放

函数传参后：

交换两个对象

 

函数结束

 

2.14 其他构造函数

template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);++first;}
}//vector<int> v(10, 10);
//vector<int> v(10u, 10);
vector(size_t n, const T& val = T())
{resize(n, val);
}vector(int n, const T& val = T())
{resize(n, val);
}

(1)迭代器区间进行初始化(模板中套模板)

解引用迭代器进行尾插即可

(2)使用n个初始值为val的数据构造vector对象

注意val的初始值缺省值是 T()

n的类型有int和size_t，防止编译器优化之后选择使用迭代器区间进行初始化而报错

vector<int> v(10, 10);

这行代码中 10 的类型默认为 int，

我们本意是想调用 vector(size_t n, const T& val = T())；函数进行对象的构造

但是由于经过编译器的类型推导

vector(InputIterator first, InputIterator last)函数更符合类型一致性

所以vector<int> v(10, 10);会去调用vector(InputIterator first, InputIterator last)函数

但是int不支持 * 操作，push_back(*first);出错，导致无法完成构造

解决方法:

(1)显示指定变量n的类型

vector<int> v(10u, 10);

(2)函数重载，使n的类型有int和size_t

vector(size_t n, const T& val = T())
{resize(n, val);
}vector(int n, const T& val = T())
{resize(n, val);
}