目录
前言
vector是顺序表。
vector运用动态内存分配空间，比起其他容器，vector在插入和读取数据上比较方便，但是在删除时要一个个挪动数据，这一点可能会有点效率低，因此需要频繁删除的文件不适合用vector存储。
vector在使用中需要掌握主要的几个接口，其他情况看文档和c++官网的说明就可以使用。
本次模拟实现只是为了更深入了解vector的功能。
一、vector实现注意事项
1.reserve和resize
reserve负责开空间，需要扩容就使用它，如果知道要扩多少的话，它可以缓解vector增容的尴尬。（根据编译器不同，平常都是1.5倍或者2倍形式扩容）
resize不仅可以开空间，它还能初始化。
2.迭代器失效
迭代器很方便的一点是它可以让算法不关注底层，底层实际上就是个指针，或者对指针进行了封装。迭代器失效就是指针所指向的空间销毁了，指针就变成了野指针，野指针又再次被使用就会造成非法访问，程序可能会崩溃。
什么情况可能会导致迭代器失效？
a.扩容，reserve或者resize扩容和erase删除，resize也用reserve扩容（我模拟实现的时候）。这种情况处理reserve扩容就可以，我们c++扩容都是异地扩容，那么之前的_start指针指向的空间要手动释放，然后让它指向一个新的建立好并拷贝了之前数据的空间。这个时候，之前指向那块空间的迭代器就会失效。
指向原空间的指针不仅有_start还有_finish和_endofstorage。当迭代器失效后，依附于传这些指针作为参数的函数也会失效。所以要使用这些函数得在扩容前先记住。三个指针都得在扩容后重新更新。
b.删除。如果使用erase进行删除，理论上来说，不会导致底层空间的改变，只有在pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的。因此删除vector任意位置的时候，vs认为该位置上迭代器失效。pos被删除后，它就不能再被使用了。用它循环++ 、--等操作都是不可以的。要使用的话只能重新建个迭代器记住pos位置。用这个临时迭代器来循环。
二、vector模拟实现部分常用功能
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace ting
{
template<class T>
class vector
{
public:
// Vector的迭代器是一个原生指针
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator cbegin() const
{
return _start;
}
const_iterator cend() const
{
return _finish;
}
// construct and destroy
vector()
:_start(nullptr)
,_finish(nullptr)
,_endOfStorage(nullptr)
{
}
vector(int n, const T& value = T())
:_start(nullptr)
,_finish(nullptr)
,_endOfStorage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n;++i)
{
push_back(value);
}
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
,_finish(nullptr)
,_endOfStorage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endOfStorage(nullptr)
{
/*vector<T> tmp(v.begin(), v.end());
swap(tmp);*/
reserve(v.size()); // 分配足够的内存空间
for (size_t i = 0; i < v.size(); ++i)
{
_start[i] = v._start[i]; // 逐个复制元素
}
_finish = _start + v.size(); // 更新 _finish 指针
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endOfStorage, v._endOfStorage);
}
vector<T>& operator= (vector<T> v)
{
swap(v);//传来的是临时对象，临时对象要经过拷贝构造，所以先拷贝一个临时对象再交换
return *this;
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
}
// capacity
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endOfStorage - _start;
}
void reserve(size_t n)
{
size_t size = this->size();
if (n > capacity())
{
T* tmp = new T[n];
if (_start)
{
for (size_t i = 0; i < size; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start+size;
_endOfStorage = _start+n;
}
}
void resize(size_t n, const T& value = T())
{
//1.n比size要小，保留前n个
//2.n比size大，比capacity小，用specified val填充多出的size
//3.n比capacity大，同上
size_t size = this->size();
while (n > capacity())
{
reserve(n);
}
if (n <= size)
{
_finish = _start + n;
}
else
{
while (_finish < _start + n)
{
*_finish = value;
++_finish;
}
}
}
///access///
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos)const
{
assert(pos < size());
return _start[pos];
}
///modify/
void push_back(const T& x)
{
/*if (_finish + 1 >= _endOfStorage)
{
reserve(2 * size());
}
*_finish = x;
++_finish;*/
insert(end(), x);
}
void pop_back()
{
/*if(_start)
--_finish;*/
erase(end() - 1);
}
iterator insert(iterator pos, const T& x)
{
assert(pos<= _finish && pos >= _start);
if (_finish == _endOfStorage)//扩容会导致迭代器pos失效
{
size_t n = pos - _start;//记住pos的位置
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
pos = _start + n;//再重新给pos赋值
}
//挪动数据
iterator it = _finish -1;
while (it >= pos)
{
*(it + 1) = *it;//最后一步是把pos的值给pos+1的位置
--it;
}
//插入数据
*pos = x;
++_finish;
return pos;//返回插入的数据的位置
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos <= _finish);
iterator it = pos + 1;
while (it < _finish)
{
//第一步是把pos+1的值给pos
//最后一步是把_finish-1的值给_finish-2;
*(it-1) = *it;
++it;
}
--_finish;
return pos;//新的pos是原来的pos+1的值，覆盖掉了pos
}
private:
iterator _start; // 指向数据块的开始
iterator _finish; // 指向有效数据的尾
iterator _endOfStorage; // 指向存储容量的尾
};
}