C＋＋———— Vector
一、vector的介绍及使用
1.1 vector的介绍
1.2 vector 的使用
1.21 vector的定义
演示：
1.22 vector iterator 的使用
1.begin+end
主要作用：获取第一个数据位置的迭代器和最后一个数据的下一个位置的迭代器。
演示：
2.rbegin+rend
主要作用：rbegin获取最后一个数据位置的迭代器，rend获取第一个数据的前一个位置的迭代器。
演示：
1.23 vector空间增长问题
演示：
注解：capacity的代码在g++和vs下分别运行下会发现，vs下的capacity是按1.5倍增长的，g++是按2倍增长的，由此可以到底每一次增长多少是不确定的，需要看编译器。
reserve是负责开辟空间的，如果提前知道需要多少空间可以使用reserve统一开辟，减少vector增容的代价问题
resize在开空间时，还会初始化，影响size.
1.23 vector增删查改
演示：
1.24迭代器失效
迭代器的主要作用就是让算法不用关心底层数据结构，其实本质是指针或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T*。因此迭代器失效，实际就是迭代器底层对应的指针成为了野指针
例子一：
1.会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、 insert、assgin、push_back（由于vector本质底层是数组，地址都是连在一起的，当他需要扩容的时候一般都是，开辟新的空间，并复制需要的值，释放原来的空间，造成如果不更新迭代器，那么迭代器指向的是原来的空间，但是这时候原空间已经被释放了）
做法：更新迭代器
例子二：指定位置元素的删除操作——erase
解释：如上图，这段代码崩了，有两个问题，第一个问题是：erase本质其实是覆盖，将该删除位置的数据被后面的数据给覆盖，上面这段代码但他判断一个数据为偶数的时候，会移动后面的数据到要被删除的位置，再++t会错过，移动数据的判断(如下图错过3的判断)。
第二个错误：当最后一个数据是偶数时，end()的迭代器会-1，it会++，因此错过end()和it的判断，二者一直相等
如果将代码改为如下图所示，就没有以上两个错误了 ，但是仍然报错了
这是因为vs对迭代器的失效检测比较极端，直接认为再erase后的迭代器失效了。再g++下就没有这么严格这段程序就是正确的。
正确改法：erase会返回删除值位置的迭代器
二、vector 的模拟实现
再模拟实现之前，我们可以看一看 vector的原码，发现string不同的是vector的三个成员函数都是迭代器，这里值得注意的是，vector的模拟实现使用的是模板，模板不接受定义和实现分离，所以我们使用一个文件vector.h来实现
1.vector的构造和析构
代码：
vector()
{
}
//v2(v1)
vector(vector<T>& v)
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
//v2 = v1
//现代写法
/*swap(vector<T>& v)
{
std::swap(this->_star = v._star);
std::swap(this->_finish = v._finish);
std::swap(this->_end_of_storage = v._end_of_storage);
}
vector<T>& operator=(vector<T> v)
{
swap(v);
}*/
//传统写法
vector<T>& operator=(vector<T> v)
{
delete[]_start;
_start = _finish = _end_of_storage = nullptr;
reserve(v.size());
for (auto e : v)
{
push_back(e);
}
return *this;
}解析：为什么vector的构造什么东西的没有写，那是因为我们再成员变量给了一个缺省值，作用于初始化列表，vector再构造时会走初始化列表把_start,_finish，_end_of_storage置成nullptr
能不能不写vector的默认构造？不能，因为拷贝构造也属于构造，如果不写编译器没有办法生成默认构造
能不能不写缺省？不能因为拷贝构造也属于构造，没有默认构造成员变量会变成随机值
赋值有两种写法一种传统一种现代，现代主要利用自定义类型的传值会调用拷贝构造，举个例子:
v1 = v2调用赋值时v2需要传值v，此时调用拷贝构造把v2的值传给v，v中存储的值就是v2的且两者是独立的不涉及浅拷贝，我们把v1与v2的内容交换，v是局部变量，出来作用域就自动释放了，这是v会把原来v1的内容给释放，v1现在的值与v2相同
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}2.end和begin的迭代器
代码：
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
iterator begin()const
{
return _start;
}
iterator end()const
{
return _finish;
}3.resize
代码：
void reserve(size_t n)
{
if (n > capacity())
{
size_t Oldsize = size();
T* tmp = new T[n];
for (size_t i = 0; i < Oldsize(); i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finsh = _start + Oldsize;
_end_of_storage = _start + n;
}
}问题分析：为什么不用memcpy
1.memcpy是内存的二进制格式的拷贝，将一段内存空间中的内容原封不动的拷贝到另外一段内存空间中
2.如果拷贝的是内置类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型的元素，并且自定义类型的元素中涉及到资源管理时，就会出错，因为memcpy是浅拷贝。（结论：如果对象中涉及资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃）
4.size capacity
size_t size()
{
return _finsh - _start;
}
size_t capacity()
{
return _end_of_storage - start;
}
size_t size()const
{
return _finsh - _start;
}
size_t capacity()const
{
return _end_of_storage - start;
}5. push_back pop_back
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity == 0 ? 4 : capacity() * 2);
}
*_finsh = x;
finsh++;
}
void pop_back()
{
assert(_finsh > _start);
--finsh;
}6. []
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i)const
{
assert(i < size());
return _start[i];
}7.insert 和erase
代码：
void insert(iterator pos, const T& x)
{
assert(pos > _start);
assert(pos < _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;//reserve之后迭代器失效，记录pos的位置，方便更新
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;//更新pos
}
iterator end = _finish - 1;
while (pos <= end)
{
*(end + 1) = *end;
end--;
}
*pos = x;
_finish++;
}
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator end = pos + 1;
while (end < _finish)
{
*(end - 1) = *end;
end++;
}
_finish--;
return pos;
}