? ? ? ? Vector是一个线性表，可以当做是数组来使用。vector的大多数函数和使用方法都跟string类似，所以这里主要是注意实现的方法。
一、vector的简单使用
?
vector<int> v; //显示实例化 指定存储的数据类型
v.push_back(1); //插入数据
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
vector<int>::iterator fd = find(v.begin(), v.end(), 3);
if (fd != v.end()) {
v.insert(fd, 30);
}
for (auto e : v) {
cout << e << " ";
}
cout << endl;
fd = find(v.begin(), v.end(), 30);
if (fd != v.end()) {
v.erase(fd);
}
for (auto e : v) {
cout << e << " ";
}
cout << endl;? ? ? ?
????????像vetcor这样的容器在这里就跟string有点不同的地方，有些函数为了能减少代码冗余也为了方便使用，就把某些函数写在了头文件<algorithm>中，像这里的find()函数，vector可以用，其他容器都可以用，就免的每个容器里面都实现一次。
? ? ? ? 而且可以看出来vector内置的很多函数名字和使用的方法都跟string差不多。这也是编写库的工程师故意而为之，就是为了方便只学习了一个容器其他的可以很快的入手。
二、vetor的模拟实现
?
namespace zs
{
template<clss T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
size_t size() const
{
return _finish - _start;
}
size_t capacity()const
{
return _end_of_storage - _start;
}
private:
iterator _start; //数组开头
iterator _finish; //数组结尾
iterator _end_of_storage; //开辟的空间大小
}
}? ? ? ? 因为vector可以存储多种数据，可以是内置类型也可以是自定义类型，但是你是不知道你具体用的时候是要使用哪种类型的，所以这里使用一个变量来记录数据的长度和容量是不太方便的。
????????所以这里把size()和capacity()定义成了函数，使用指针来即时的计算。
PS：typedef要放在public下面，放在private下面在外面是无法调用的。
//构造函数
vector()
:_start(nullptr)
, _finish(nullptr)
,_end_of_storage(nullptr)
{
}
//析构函数
~vector()
{
delete[] _start;
_start = _finish = _finish = nullptr;
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
//常量对象会调用下面的两个函数 比如 const vector<int>& v 还需要一个常量迭代器const_iterator
iterator begin()const
{
return _start;
}
iterator end()const
{
return _finish;
}?
//扩容
void reserve(size_t n)
{
if (n > capacity()) {
size_t sz = size();
T* temp = new T[n];
if (_start) {
memcpy(temp,_start,sizeof(T) * sz);
delete[] _start;
}
_start = temp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}? ? ? ? 扩容的函数比较容易理解没什么要注意的。
T& operator[](size_t pos)
{
assert(pos<size());
return _start[pos];
}
void push_back(const T& x)
{
if (_finish == _end_of_storage) {
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
_finish++;
}
void pop_back()
{
assert(_finish > _start);
--_finish;
}
? ? ? ? 重载[ ]，因为底层还是用数组存储数据，所以这里复用一下数组的[ ]就可以了。
? ? ? ? push_back()，这里因为不知道具体使用的时候要存储什么数据，所以使用了摸板，而且这里使用了const修饰参数，那么这里就可以使用 push_back("hello")? 这种隐式类型转换。
void insert(iterator pos,const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
//这里如果发生扩容 pos位置失效了 所以要更新一下
if (_finish == _end_of_storage) {
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++;
}
//stl规定erase返回pos迭代器位置的下一个迭代器
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos <= _finish);
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
_finish--;
//库里面会缩容，也会造成迭代器失效
//if (size()<capacity()/2) {
// //... 缩容
//}
return pos;
}????????insert/erase? pos的位置，不要直接访问pos，一定要更新。直接访问可以能出现出乎意料的结果，这就是迭代器失效。
? ? ? ? 这里pos是个迭代器，本质是个指针，在做插入操作的时候，如果容器容量不够会发生扩容。而这时要访问的就是一段新的空间，pos如果不更新的话还是指向原来的空间，变为一个野指针，造成迭代器失效。
iterator begin()
{
return _start;
}
//传引用这里会失效
v.insert(v.begin(),1);? ? ? ? 还有这里insert使用的传值传参，如果这里改成引用void insert(iterator& pos，const T& x)；会导致这种上面的写法失效。
? ? ? ? begin()；这里是传值返回，返回是的临时变量，临时变量具有常性。但是如果用const修饰pos，void insert(const iterator& pos，const T& x)；会导致pos无法修改，前面讲了如果发生扩容要更新pos，所以这里只能用传值传参。
????????
//删除偶数
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
//迭代器失效
auto it=v.begin();
while(it!=v.end()){
if(*it%2==0){
v.erase(it);
}
it++;
}
? ? ? ?
????????这里也会造成迭代器失效并报错?，这是因为在erase()函数内部，每次删除一个元素，后面的数据会往前覆盖，那么删除位置数据就变成了下一个要判断的数据，而这里it指针++，则会错过造成删除的错误。
????????而且当删除最后一个数据的时候，_finish指针减1，而it还在++，指针错过导致还会进入循环，进入erase()时断言判断越界。
//真确写法
auto it=v.begin();
while(it!=v.end()){
if(*it%2==0){
it=v.erase(it);
}
else{
it++;
}
}?
