- 迭代器
- 构造函数
- 无参构造函数
- 带长度和初始化值的构造函数
- 使用迭代器的构造函数
- 拷贝构造函数
- 赋值运算符重载
- reserve函数和resize函数
- 插入函数
- 尾插
- insert函数
- 单个元素的插入
- 插入多个元素
- 插入一段区间
- 删除函数
- 尾删
- erase函数
- 删除单个元素
- 删除一段元素
- 重载[]运算符
- 其他函数
- size()函数
- capacity()函数
- 析构函数
在上一篇的博客中，我详细介绍了vector的使用，为了能够更好的使用vector，还需要仔细了解它的底层原理。
vector内部的成员有三个：
| 成员 | 标志 |
|---|---|
| _start | 表示已用空间的起始位置 |
| _finish | 表示已用空间的终止位置 |
| _end_of_storage | 表示可用空间的终止位置 |
vector在存储方式上与数组是一样的，都是使用连续空间进行存储的，与数组不同的是它是动态的，因此vector的迭代器必须支持随机访问。正因为是连续空间的存储方式，原生指针就可以作为vector的迭代器。
//实现迭代器
iterator begin()
{
return _start;
}
const_iterator begin() const
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator end() const
{
return _finish;
}
构造函数
构造函数有很多种：
无参构造函数无参构造，说明vector中所有的指针都是空指针，vector内部没有分配空间。那么可以通过初始化vector中的三个成员为空指针来进行构造。
vector()
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{}
带长度和初始化值的构造函数
在创建时在vector放入n个初始化值，也就是在开始的时候对vector的空间和内容进行初始化。
vector(int n, const T& val = T())//这里的第二个值为初始化值，缺省值相当于一个匿名对象，也就是你是什么类型，就初始化什么
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
reserve(n);
//将要初始化的值放进去
//可以通过指针来实现，也可以通过push_back实现
while (n--)
{
//push_back(val);
*(_start + n) = val;
_finish++;
}
}
在实现的时候为了防止代码冗余，在修改空间的时候复用了reserve函数(reserve函数的实现在下面介绍)，对内容的初始化遍历赋值或者复用push_back函数。
使用迭代器的构造函数由于vector是通过连续空间进行存储的，那么它的迭代器可以用原生指针来代替，具有随机访问的功能。那么通过迭代器来进行初始化就是遍历这一段空间，将该段空间具有的值放入。
//3、通过迭代器初始化 //使用函数模板 templatevector(InputIterator first, InputIterator last) { reserve(last - first); while (first != last) { //push_back(*first); first++; } }
使用函数模板的原因是，迭代器的种类也有很多，那么如果只写一个单一的函数，遇到其他的迭代器还得重新再写一个，这个就可以通过函数模板解决。
拷贝构造函数拷贝构造函数就是对于给定的一个vector，构造一个与之相同的vector。为了减少代码的冗余，尽量使用已经写好的函数复用。那么我们的思路可以是这样的：要拷贝构造一个与给定的vector，首先内部空间一定是相同的，那么可以用reserve函数开辟与给定的vector相同的空间；然后对内部的元素进行遍历拷贝。
//拷贝构造函数 //下面这种开辟空间以及成员变量的修改操作是在reserve函数中进行的 //这块存在一点问题：正常来说，如果拷贝构造不进行初始化的话，在reserve时不是空指针就会对空间进行释放，此时就会报错 vector(const vector& v) : _start(nullptr) , _finish(nullptr) , _endOfStorage(nullptr) { reserve(v.capacity()); //此处同理也不能用memcpy进行拷贝 //如果命名为cbegin，cend就会出错 for (auto e : v) push_back(e); }
这里面有几处细节需要注意：
1、在用reserve函数进行拷贝构造的时候，需要对成员变量进行空指针初始化，这是由于调用的是reserve函数，在开始开辟空间的时候会对原空间进行释放，此时如果没有初始化就是野指针，那么此时释放就会出错。
2、这里对于元素的拷贝不能用memcpy，因为memcpy拷贝的时候进行的是浅拷贝，在vector析构的时候，就会出现析构两次的情况。
当然这里也可以不用reserve函数，自己来开辟空间进行拷贝构造。
vector(const vector赋值运算符重载& v) //: _start(nullptr) //, _finish(nullptr) //, _endOfStorage(nullptr) { _start = new T[v.capacity()]; for (size_t i = 0; i < v.size(); ++i) _start[i] = v._start[i]; _finish = _start + v.size(); _endOfStorage = _start + v.capacity(); }
赋值运算符的重载多采用现代写法
void swap(vector& v) { //用域限定符首先查找全局的 ::swap(_start, v._start); ::swap(_finish, v._finish); ::swap(_endOfStorage, v._endOfStorage); } //如果是用现代写法的话，在交换之后v就会销毁，如果不初始化为空指针，就会销毁随机空间，这是错误的 //用交换函数这里不能带引用，否则就会改变原来的值 vector & operator=(vector v)//之所以可以交换，是因为在传参的时候进行了深拷贝，交换之后v就会销毁，刚好将原来的空间释放 { swap(v);//这里的交换函数最好自己实现一下，如果用库函数给的，就需要多次进行深拷贝 return *this; }
现代写法的赋值运算符重载是通过交换两个不同的vector来完成的。为了不改变原vector的值，在传参的时候没有加引用，此时编译器会拷贝构造一份，我们将该vector与当前的进行交换。交换之后v会自动销毁，完成拷贝构造的目的。
注意：
1、由于现代写法的拷贝构造需要用到拷贝构造，并且交换之后会进行释放，那么这里就需要将拷贝构造进行初始化。
2、这里的交换函数最好自己实现一下，如果用库函数给的，就需要多次进行深拷贝。
reserve函数是用来改变vector的空间容量的。reserve函数分为两个方面，如果改变的空间容量小于当前容量，reserve函数是什么都不做的，也不会去改变空间容量；如果改变的空间容量大于当前容量，reserve会将vector的空间改为想要开辟的容量。
vector开空间的时候是需要付出代价的，也就是重新配置，移动数据，释放原空间三步。
//reserve函数
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();//要将原本size的长度保存下来，否则后面扩容之后就会改变指针
//delete[] _start;//销毁_start也就意味着将其他的指针也销毁了
iterator tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, sizeof(T)*sz);
//memcpy拷贝是浅拷贝，也就是直接将源文件的空间给到目标文件的空间
//如果是内置类型或适合浅拷贝类型，这样做是没问题的
//如果涉及到资源管理，那么就会出现释放两次的情况
for (size_t i = 0; i < sz; ++i)
tmp[i] = _start[i];//可以直接赋值，这样对于一些深拷贝的类型，赋值重载是深拷贝，完全没有问题
delete[] _start;//销毁_start也就意味着将其他的指针也销毁了
}
_start = tmp;
_finish = _start + sz;
_endOfStorage = _start + n;
}
}
resize函数是用来改变当前有效空间的大小，并且可以为新的空间赋值。
resize实现时分为三类：
第一类是改变的长度小于当前有效长度，那么此时只需要将_finsh的位置前移即可。
第二类是改变的长度大于有效长度，但是小于空间容量。此时只需要将新增的长度赋值即可。
第三类是改变的长度大于空间容量，那么就需要先开辟新的空间，然后在新增的长度中赋值。
可以发现，第一类就是将有效长度减去即可。第二类和第三类空间的增长与reserve函数相同，那么可以调用reserve函数，只需要对新的长度赋值即可。
//resize函数
void resize(size_t n, T val = T())
{
if (n > size())
{
reserve(n);
int len = n - size();
while (len--)
{
*_finish = val;
_finish++;
}
}
else
{
_finish -= (size() - n);
}
}
插入函数
尾插
vector的尾部插入就是在_finish的位置插入一个元素，这里只需要考虑的是空间满了的扩容情况。
//尾插
void push_back(const T& val)
{
//如果空间够了就扩容
if (_finish == _endOfStorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = val;
++_finish;
}
insert函数
insert函数是在任意位置进行插入，由于vector是连续的空间，因此在任意位置插入是需要进行数据的挪动的，代价比较大。
单个元素的插入//1、单个元素的插入
iterator insert(iterator pos, const T& val)
{
assert(pos);
//如果空间不够就扩容
if (_finish == _endOfStorage)
{
int newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
iterator ptr = _finish;
//挪动数据
while (ptr != pos)
{
*ptr = *(ptr - 1);
--ptr;
}
*pos = val;
_finish++;
return pos + 1;
}
插入多个元素
//2、插入多个元素
void insert(iterator pos, int n, const T& val)
{
assert(pos);
//扩容之后空间就变了，因此需要记录下原来元素的坐标
size_t old_sz = pos - _start;
iterator new_ptr = _finish + n;//得到插入多个元素之后的长度
//大于容量则需要扩容
if (new_ptr > _endOfStorage)
reserve(new_ptr - _start);
pos = _start + old_sz;
iterator ptr = pos;
//挪动数据
while (ptr != _finish)
{
*(ptr + n) = *ptr;
++ptr;
}
_finish += n;
//从pos位置开始放入多个元素
while (n--)
{
*pos = val;
pos++;
}
}
插入一段区间
//3、在某个位置插入区间 template删除函数 尾删void insert(iterator pos, InputIterator first, InputIterator last) { assert(pos); //首先算出要插入的长度 int len = last - first; size_t old_sz = pos - _start; iterator new_ptr = _finish + len;//得到插入多个元素之后的长度 //大于容量则需要扩容 if (new_ptr > _endOfStorage) reserve(new_ptr - _start); pos = _start + old_sz; iterator ptr = pos; //挪动数据 while (ptr != _finish) { *(ptr + len) = *ptr; ++ptr; } _finish += len; while (first != last) { *pos = *first; pos++; first++; } }
//尾删
void pop_back()
{
//这里要断言一下，如果为空则不能尾删
assert(!empty());
_finish--;
}
erase函数
删除单个元素
//1、删除单个元素
iterator erase(iterator pos)
{
assert(pos);
iterator ptr = pos + 1;
while (ptr != _finish)
{
*(ptr - 1) = *ptr;
ptr++;
}
_finish--;
return pos;
}
删除一段元素
//2、删除一段元素
void erase(iterator first, iterator last)
{
int len = last - first;
iterator ptr = last + 1;
while (ptr != _finish)
{
*(ptr - len) = *ptr;
ptr++;
}
_finish -= len;
}
重载[]运算符
重载[]运算符能够使得vector像数组一样去访问元素
//重载[]运算符
T& operator[](size_t n)
{
return *(_start + n);
}
const T& operator[](size_t n) const
{
return *(_start + n);
}
其他函数
size()函数
//size函数
size_t size() const
{
return _finish - _start;
}
capacity()函数
//capacity函数
size_t capacity() const
{
return _endOfStorage - _start;
}
析构函数
//析构函数
~vector()
{
if (_start)
delete[] _start;//销毁_start相当于将整个vector销毁
_start = _finish = _endOfStorage = nullptr;
}
