首先要知道vector是什么
vector是什么
1.vector是表示可变大小数组的序列容器。
- 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
- 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大 小。
- vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
- 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增 长。
- 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。
vector的实现
要实现一个容器第一步肯定还是确定vector的成员变量，并且因为vector和我们知道的普通数组不一样的就是，普通的数组内部只能储存整型的数据，但是vector你传入什么类型那么它就会实例化成能储存你传入类型的容器。由此实现vector需要使用到模板。
下面是vector的模拟实现基本代码：
template<class T>
class vector
{
private:
T* start;
T* end;
T* endofstorage;
};至于为什么vector的成员变量是三个指针。
下面我来解释这三个指针的用途：这三个指针指向的是同一片连续空间的不同位置。其中从start指向的是空间的开始，而end指向的是这个空间储存的有效数据的下一位。而endofstorage指向的是这篇空间的末尾。
无参默认构造和析构函数
下面是vector的无参的默认构造函数
vector()//首先实现一个无参的默认构造函数
:start(nullptr)
,end(nullptr)
,endofstorage(nullptr)
{}
~vector()
{
delete[] _start;//释放空间
_start = _end = _endofstorage = nullptr;
}//析构函数然后下面我们来实现拷贝构造但是在实现拷贝构造之前肯定要让vector存在开辟空间的函数
reserve函数
//下面是和string一样的基本信息获取函数,连续的空间指针相减得到的就是两个指针之间的元素个数
size_t size()
{
return _end - _start
}
size_t capacity()
{
return _endofstorage - _start;
}
void reserve(size_t n)
{
//第一步需要判断是否需要扩容，而连续的空间指针相减得到的就是两个指针之间的元素个数
size_t __capacity = capacity();//获取当前的容量
size_t __size = size();//获取当前的有效数据长度
if (n > __capacity)//需要扩容
{
T* tmp = new T[n];//首先创建一个n个大小的新空间
if (_start)//如果原空间中存在信息，而非空
{
memcpy(tmp, _start, sizeof(T)*__size);//将原空间数据拷贝到新空间
}
_start = tmp;//将新空间赋值过去
_end = _start + __size;
_endofstorage = _start + n;//在这里就可以体现出我们提前将原空间有效数据记录下来的好处了
//如果在这里你没有记录原空间的有效数据个数，而是采用函数计算，但是不要忘了现在的_start指向了一片新空间
//而end指向的任然是老空间就会出现错误
//所以这里需要记录老空间的有效数据个数
delete[] _start;//删除原空间内存
}
}在完成了reserve函数之后，我们就可以去完成push_back函数往vector中插入数据了。
push_back和[]函数
void push_back(const T& x)//尾插入一个数据
{
if (_end == _endofstorage)//判断空间是否足够
{
reserve(capacity() == 0 ? 4 : 2 * capacity());//这里的双目表达式，在capacity本省便为0的时候会创建4个大小的
//空间，不然就按照空间两倍的大小扩容
}
*_end = x;//之后让*_end指向的那个空间填入x
_end++;//再让_end++
}下面我们再来完成[]函数，之后来检测一下是否有错误存在。
T& operator[](size_t n)
{
assert(n < size());//首先判断是否超出有效数据范围。
return *(_start + n);//然后返回这个数据即可
}//并且我们现在重载的这个操作符既能读也能写
T operator[](size_t n) const
{
assert(n < size_t n);
return *(_start + n);
}//这个函数则是只有读的功能下面是测试和运行截图（测试代码就不写了，可以在下图查看）
正向迭代器的模拟
既然已经完成了基本的输入输出，下面我们就来完成迭代器的模拟实现。因为vector的空间也是连续的所以使用原生指针即可。
typedef T* iterator;
typedef const T* const_iterator;//const迭代器是可以改变指针的指向，但是不能通过指针去修改值
iterator begin()
{
return _start;
}
iterator end()
{
return _end;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _end;
}
最后是测试和运行截图：
反向迭代器的模拟
和正向迭代器不一样，反向迭代器就不能使用原生指针了，因为反向迭代器的加加，反而需要我们去让指针减减，而反向迭代器的减减又需要我们去加加指针。
所以我们需要自己在写一个类用于反向迭代器的模拟（模板）。
如下：
template<class T, class ref,class ptr>
struct Reserve_iterator
{
typedef Reserve_iterator<T, ref, ptr> self;
T* _stu;//这个便是反向迭代器的成员变量是一个T* 的指针
//然后下面我们来模拟一个指针能做的++，--，*，->,!=,==
Reserve_iterator(T* tmp = nullptr)
:_stu(tmp)
{}
self operator++()//前置++
{
_stu--;//将T*的指针减减，就是反向迭代器的加加
return *this;
}
self operator--()//前置--
{
_stu++;
return *this;
}//和上一个一样
self operator++(int)//后置++这里的int就只是表明这是一个后置++而已
{
self tmp(*this);
_stu--;
return tmp;
}
self operator--(int)
{
self tmp(*this);
_stu++;
return tmp;
}
//下面要重载*和->
//这两个函数也是为什么要传入三个模板参数的原因
//对于反向迭代器而言const版本和非const版本唯一的不同也就是，const版本的迭代器不能通过指针去修改值
//那么对于const迭代器的*我们就可以返回const T&，非const迭代器就直接返回T&即可
//所以我们设置了三个模板参数
ptr operator*()
{
return (*_stu);
}
ref operator->()
{
return _stu;
}
bool operator!=(const self& b)
{
return _stu != b._stu;
}
bool operator==(const self& b)
{
return _stu == b._stu;
}
};但是只完成这一个类也无法完成反向迭代器，最后还需要再vector的类中加入rbegin和rend函数
如下：
typedef Reserve_iterator<T, T*, T&> reserve_iterator;
typedef Reserve_iterator<T, const T*, const T&> const_reserve_iterator;
reserve_iterator rbegin()//返回反向迭代器的开头
{
return (_end - 1);//因为_end指向的是有效数据的下一位
}
reserve_iterator rend()//反向迭代器的结束
{
return _start - 1;//这里的_start也需要减一，因为循环结束的条件是it和rend相等如果方向迭代器的rend返回的是开头元素的指针
//那么当it和rend相等的时候不会进入循环，也就会导致原本开头的元素会被漏掉
}
const_reserve_iterator rbegin() const
{
return (_end - 1);
}
const_reserve_iterator rend() const
{
return _start - 1;
}那么为什么反向迭代器要三个模板参数呢？究其原因是为了区分const反向迭代器和非const反向迭代器
const 反向迭代器和非const的不同就在于两个函数，一个是*一个是->, 对于const迭代器而言。返回的 是const T& 而非const迭代器返回的是T& ，对于->函数const迭代器返回的是const T*。非const迭代器返回的是 T*。
所以我们将这几个不同的返回值作为模板参数，让我们只用写一个结构体就能实例化出，const反向迭代器和非const反向迭代器。
下面是测试和运行截图：
复制拷贝函数和赋值=函数
下面我们来完成vector的复制拷贝函数以及=函数。
vector(vector<T>& b)
{
//我们需要拷贝b的内容，首先就需要拥有和b一样大的空间
reserve(b.capacity());//创建空间
for (int i = 0; i < b.size(); i++)
{
push_back(b[i]);//再将b里面的数据尾插入*this中完成拷贝。
}
}
void swap(vector<T>& b)
{
std::swap(_start, b._start);
std::swap(_end, b._end);
std::swap(_endofstorage, b._endofstorage);
}
vector<T>& operator=(vector<T> b)
{
//这里的=我就使用了新式的写法，将要拷贝的vector在传参的时候，就将其拷贝完成，
//然后让b和*this交换，即能把原空间释放（离开这个函数后b就会被销毁），也能完成*This的赋值
swap(b);
return *this;
}下面是测试截图：
resize函数
和string的resize函数一样，resize也需要考虑三种情况。
void resize(size_t n, T tmp = T())
{
if (n < size())//当n小于有效数据个数的时候需要我们删除元素
{
_end = _start + n;
}
else//需要我们增加数据，并且可能会伴有扩容
{
reserve(n);//如果n小于容量那么这个函数什么也不会做
for (int i = size(); i < n; i++)
{
*(first + i) = tmp;//从最后一个元素开始往后赋值
}
}
}那么在这里我来解释一下，为什么tmp的全缺省使用的是T（）而不是0，因为我们完成的vector是一个模板，它不是专门储存整型的容器，而是一个既能储存内置类型也能储存自定义类型的容器。所以这里的全缺省填的是匿名对象，让其能去调用这个T的构造函数，而在c++11之后内置类型也支持了默认构造。所以这里天的是一个匿名对象。
下面是测试实例：
使用迭代器的构造函数
在库里面还有一种构造函数的方法，就是使用迭代器区间去初始化，并且这个迭代器是支持所有容器的迭代器的（使用模板）。
template <class InputIterator>
vector(InputIterator start,InputIterator,end)
{
while (start != end)
{
push_back(*start);//将迭代器指向的元素尾插到*this中
start++;
}
}下面是测试实例
insert函数
和string的insert函数不同 它是插入到一个迭代器的前面。返回的也是插入数据的那个迭代器。
首先第一个是在某个迭代器前面插入一个数据：
iterator insert(iterator pos, const T& x = T())
{
//第一步还是要判断要插入的位置是否超出了有效数据的长度
assert(pos >= _start);
assert(pos <= _end);
//下面需要判断空间是否需要扩容
if (_end == _endofstorage)
{
//记录pos是在哪一个位置的迭代器，因为扩容后
//pos指向的那个空间就会被释放
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;//再次让pos指向它应该在的位置
}
//然后连续的空间需要插入还是使用从后向前的移动方法
iterator tmp = _end;
while (tmp >= pos)
{
*(tmp + 1) = *(tmp);
tmp--;
}
*pos = x;
_end++;
return pos;
}//这个是插入一个数据下一个是在某个迭代器的前面插入n个数据
iterator insert(iterator pos, size_t n, const T& x = T())
{
assert(pos >= _start);
assert(pos <= _end);
//第一步创建一个临时的足够大的空间
size_t len = pos - _start;//求出在pos前面存在多少数据
T* tmp = new T[size() + n];//创建一个足够大的空间
size_t tmpi = 0;
for (; tmpi < len; tmpi++)
{
tmp[tmpi] = *(_start + tmpi);
}//将pos前面的数据放到tmp中去
while (n--)
{
tmp[tmpi++] = x;
}//将n个数据放到tmp中去
//最后将pos后的数据放到tmp中去
for (int i = len; i < size(); i++)
{
tmp[tmpi++] = *(_start + i);
}
delete[] _start;//释放原空间储存
_start = tmp;
_end = _start + tmpi;
_endofstorage = _start + n + size();
return pos;
}//在pos前面插入n个数据因为使用迭代器完成插入一段数据如果是使用移动的方式，那么在插入数据时比较复杂，所以这里我才已经的是先创建一个足够大的空间，然后将pos前面的数据放到这个新数组中去，然后插入数据，最后将pos后面的数据再放到这个新创建的数组中去。由此完成。
还有一个方法就是移动数据
iterator insert(iterator pos, size_t n, const T& x = T())
{
size_t add = pos - _start;//首先找到pos在vector的哪一个位置
size_t len = size();//记录原本的空间大小
reserve(len + n+1);//扩容需要多扩容一个空间，否则在移动之后会导致
//_size指向超出容量的空间导致析构出错，析构出错的原因也就是
//_szie指向了超出容量的那一个空间，最后导致错误
pos = _start + add;//重新找到pos
for (int i = _end - _start; i >= add; i--)//移动数据
{
*(_start + i + n) = *(_start + i);
}
size_t times = n;
while (times--)
{
*(_start + add) = x;
add++;
}
_end = _start + len + n;
return pos;
}需要注意的是如果使用这种方法俺么
下面是测试和运行截图：
erase函数
首先erase函数有两个版本，一个删除迭代器此时指向的那一个元素，还有一个是删除一段迭代去区间。
首先来完成删除迭代器指向的那一个元素。
//删除pos位置的元素
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _end);
size_t len = pos - _start;
for (int i = len; i < size(); i++)
{
*(_start + i) = *(_start + i + 1);
}//从后往前移动数据
_end--;
return _start + len;//最后返回删除数据后的那个迭代器
}//删除一个元素删除一段迭代器区间的数据：
iterator erase(iterator first,iterator last)
{
assert(first >= _start);
assert(first < _end);
assert(last >= first);
assert(last <= _end);
if (last == _end)//删除从first开始往后的能删的所有元素
{
_end = first;//直接让_end等于_first即可
return _;
}
else
{
//将last往后的元素从后往前移动即可
for (int i = last - _start; i <size(); i++)
{
*first = *(_start + i);
first++;
}
_end = first;
return _start;
}
}测试即运行截图：
在完成了这两个函数之后，push_back和pop_back等函数就可以复用这两个函数完成了。我这里就不写了。
希望这篇博客对你能有所帮助，如果发现了任何错误，欢迎指出。我一定改正。