vector的模拟实现
@[TOC]
vector就是一个顺序表而已，只不过它是类模板，可以实例化出不同的模板类。下面我们通过模拟实现来进一步的熟悉vector。
vector的成员变量
与顺序表的成员不一样，顺序表的成员变量是指向数组的一个指针，实际数据的大小，空间的容量。而
vector的成员变量都是指针，三个指针，分别为指向所开空间的头，指向实际数据的尾，指向空间的尾。那么size,capacity也都可以很容易的表示出来。
cpp template<class T>
class vector
{
public:
typedef T* iterator;
private:
iterator start;
iterator finish;//这里的finish指向的是最后一个数的下一个位置
iterator end_of_storage;
};计算它的大小size，容量capaticy
size=finish-start,capacity=end_of_storage-start
cpp size_t size()cosnt
{
return finish - start;
}
size_t capacity()const
{
return end_of_storage - start;
}首尾的标志begin，end,首尾元素front,back
begin就直接返回第一个元素的地址，end返回最后一个元素的地址。
cpp iterator begin()
{
return start;
}
iterator end()
{
return finish;
}
front,back
cpp T& front()
{
return *start;
}
T& back()
{
return *(finish - 1);
}[]运算符的重载
首先要判断一下位置是否合法。同时还要返回引用，因为可能会对数据进行修改。
cpp T& operator[](size_t pos)
{
assert(pos < size());
return *(start + pos);
}
const T& operator[](size_t pos)const
{
assert(pos < size());
return *(start + pos);
}判断是否为空empty
只需要判断头尾是否相等就可以，相等就是空，不相等就不为空。
cpp bool empty()
{
return start == finish;
}构造，析构函数
构造函数
无参的拷贝构造,对应无参的构造函数直接都初始化为空指针就可以。
cpp vector()
:start(nullptr)
, finish(nullptr)
, end_of_storage(nullptr)
{}含参的构造 把n个数据都初始为一个值。
cpp vector(size_t n, const T& val = T())
:start(nullptr),finish(nullptr),end_of_storage(nullptr)
//写这句话的目的就是因为开始的时候指针都没有初始化，都是野指针，当开辟空间的时候会出现错误。
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
start[i] = val;
}
finish = start + n;
}
const T& val = T(),对于这个参数，读者们可能看不懂，T()生成的是匿名对象，对于内置类型，它生成的是0。用一段区间去初始化构造
cpp template<class InputIterator>
vector(InputIterator first, InputIterator last)
:start(nullptr),finish(nullptr),end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}拷贝构造
拷贝构造要考虑深浅拷贝的问题，不能单纯的进行值的拷贝。
cpp vector(const vector<T>& v)
{
start = new T[v.size()];
for (size_t i = 0; i < v.size(); ++i)
{
start[i] = v.start[i];
}
finish = start + v.size();
end_of_storage = finish;
}析构函数
对申请的空间进行释放
cpp ~vector()
{
delete[] start;
start = finish = end_of_storage = nullptr;
}改变容量的大小reserve
对于
reserve，当给的参数小于等于实际空间大小的时候，此操作是不容许的，所以不会有什么操作，只有当大于实际空间的时候才会进行扩容。
cppvoid reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (start)
{
for (size_t i = 0; i < sz; ++i)
{
tmp[i] = start[i];//要注意这里，当这里是自定义类型的时候，这里就是赋值（赋值运算符的重载，要自己实现一下）
}
delete[] start;
}
start = tmp;
finish = start + sz;//这里需要改变数据结尾指针的指向，因为空间重新开辟了。
end_of_storage = start + n;//当然，空间的指针指向也需要改变
}
}resize改变元素的个数n
当n小于容器个数的时候，直接把个数减少到n，空间的大小不变。 当n大于容器个数的时候，我们需要开空间，把多开的空间默认初始化尾0，当然要把之前的元素拷贝到新的空间里面，是深拷贝哦。
cpp void resize(size_t n, const T& val = T())
{
if (n < size())
{
finish = start + n;
}
else if (n > size())
{
iterator temp = new T[n];
for (size_t i = 0; i < n; ++i)
{
if (i < size())
temp[i] = start[i];
else
temp[i] = val;
}
delete[] start;
start = temp;
finish = start + n;
end_of_storage = finish;
}
}尾插
尾插的时候需要注意什么呢？ 尾插需要注意是否要进行扩容，对插入的类型需要考虑。
cpp void push_back(const T& x)
{
if (size() == capacity())
{
//扩容
size_t len = size() == 0 ? 4 : size() * 2;
reserve(len);
}
*finish = x;
finish++;
}尾删
直接进行删除就可以，删除的时候要判断数据是否为空。
cpp void pop_back()
{
assert(size());
--finish;
}任意位置删除
cpp iterator erase(iterator pos)
{
assert(pos < finish);
assert(pos >= start);
iterator cur = pos;
while (cur != finish)
{
*cur = *(cur + 1);
cur++;
}
finish--;
return pos;
}任意位置插入
cpp iterator insert(iterator pos, const T& x)
{
assert(pos <= finish);
assert(pos >= start);
size_t p = pos - start;
if (finish == end_of_storage)
{
reserve(capacity() + 1);
}
for (size_t i = size()-1; i>p; --i)
{
start[i] = start[i - 1];
}
start[p] = x;
return start + p;
}赋值运算符的重载
赋值也会涉及深拷贝，要注意，当然，如果自己进行赋值，就是没有必要的，所以要判断一下。
cpp vector<T>& operator=(const vector<T>& v)
{
if (start != v.start)
{
iterator temp = new T[v.size()];
for (size_t i = 0; i < v.size(); ++i)
{
temp[i] = v.start[i];
}
delete[] start;
start = temp;
finish = start + v.size();
end_of_storage = finish;
}
return *this;
}腾讯云开发者
