STL vector的内部实现原理及基本用法（源码解析）

本文基于STL 源代码，但是不考虑分配器，迭代器，异常处理try/catch等内容，同时对（）、 （）、 （）函数也不会过度分析。

一、的定义

template<class _Ty,class _Ax>class vector: public _Vector_val<_Ty, _Ax>{   // varying size array of values
public:/********/
protected:pointer _Myfirst;   // pointer to beginning of arraypointer _Mylast;    // pointer to current end of sequencepointer _Myend; // pointer to end of array};
1
2
3
4
5
6
7
8
9
10
11
12
13

简单理解，就是是利用上述三个指针来表示的，基本示意图如下：

两个关键大小：

大小：size= - ；

容量：= - ；

分别对应于()、()两个函数。

size表示中已有元素的个数，容量表示最多可存储的元素的个数；为了降低二次分配时的成本，实际配置的大小可能比客户需求的更大一些，以备将来扩充，这就是容量的概念。即>=size，当等于时，容器此时已满，若再要加入新的元素时，就要重新进行内存分配，整个的数据都要移动到新内存。二次分配成本较高，在实际操作时，应尽量预留一定空间，避免二次分配。

二、构造与析构

1、构造

的构造函数主要有以下几种：

    vector() : _Mybase(){   // construct empty vector_Buy(0);}       explicit vector(size_type _Count) : _Mybase(){   // construct from _Count * _Ty()_Construct_n(_Count, _Ty());}vector(size_type _Count, const _Ty& _Val) : _Mybase(){   // construct from _Count * _Val_Construct_n(_Count, _Val);}vector(const _Myt& _Right) : _Mybase(_Right._Alval){   // construct by copying _Rightif (_Buy(_Right.size()))_Mylast = _Ucopy(_Right.begin(), _Right.end(), _Myfirst);}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

优异性能的秘诀之一，就是配置比其所容纳的元素所需更多的内存，一般在使用之前，就先预留足够空间，以避免二次分配，这样可以使的性能达到最佳。因此元素个数是个远比元素值 _Val重要的参数，因此当构造一个时，首要参数一定是元素个数。

由上各构造函数可知，基本上所有构造函数都是基于 _n() 的

    bool _Buy(size_type _Capacity){   // allocate array with _Capacity elements_Myfirst = 0, _Mylast = 0, _Myend = 0;if (_Capacity == 0)    //_Count为0时，直接返回return (false);else{   // nonempty array, allocate storage_Myfirst = this->_Alval.allocate(_Capacity);  //分配内存，并更新成员变量_Mylast = _Myfirst;_Myend = _Myfirst + _Capacity;}return (true);}void _Construct_n(size_type _Count, const _Ty& _Val){   // 构造含有_Count个值为_Val的元素的容器if (_Buy(_Count))_Mylast = _Ufill(_Myfirst, _Count, _Val);}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这样就完成了容器的构造了。

2、析构

的析构函数很简单，就是先销毁所有已存在的元素，然后释放所有内存

    void _Tidy(){   // free all storageif (_Myfirst != 0){   // something to free, destroy and deallocate it_Destroy(_Myfirst, _Mylast);this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);}_Myfirst = 0, _Mylast = 0, _Myend = 0;}
1
2
3
4
5
6
7
8
9

三、插入和删除元素

的插入和删除元素是通过push_ back () 、 ()两个接口来实现的，他们的内部实现也非常简单

    void push_back(const _Ty& _Val){   // insert element at endif (size() < capacity())_Mylast = _Ufill(_Mylast, 1, _Val);elseinsert(end(), _Val);    //空间不足时，就会触发内存的二次分配}void pop_back(){   // erase element at endif (!empty()){   // erase last element_Destroy(_Mylast - 1, _Mylast);--_Mylast;}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

四、其他接口

1、()操作

之前提到过（Count） 函数主要是预留Count大小的空间，对应的是容器的容量，目的是保证（ - ）>=Count。只有当空间不足时，才会操作，即重新分配一块内存，将原有元素拷贝到新内存，并销毁原有内存

    void reserve(size_type _Count){   // determine new minimum length of allocated storageif (capacity() < _Count){   // not enough room, reallocatepointer _Ptr = this->_Alval.allocate(_Count);_Umove(begin(), end(), _Ptr);size_type _Size = size();if (_Myfirst != 0){   // destroy and deallocate old array_Destroy(_Myfirst, _Mylast);this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);}_Myend = _Ptr + _Count;_Mylast = _Ptr + _Size;_Myfirst = _Ptr;}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2、()操作

（Count） 函数主要是用于改变size的，也就是改变的大小，最终改变的是（ - ）的值，当size < Count时,就插入元素，当size >Count时，就擦除元素。

    void resize(size_type _Newsize, _Ty _Val){   // determine new length, padding with _Val elements as neededif (size() < _Newsize)_Insert_n(end(), _Newsize - size(), _Val);else if (_Newsize < size())erase(begin() + _Newsize, end());}
1
2
3
4
5
6
7

3、()操作

()操作和()操作都会利用到()这个函数，这个函数非常重要，也比其他函数稍微复杂一点

虽然(, , _Val ) 函数比较长，但是操作都非常简单，主要可以分为以下几种情况：

    else if (_Capacity < size() + _Count){   // not enough room, reallocate_Capacity = max_size() - _Capacity / 2 < _Capacity? 0 : _Capacity + _Capacity / 2;    // try to grow by 50%if (_Capacity < size() + _Count)_Capacity = size() + _Count;pointer _Newvec = this->_Alval.allocate(_Capacity);pointer _Ptr = _Newvec;_Ptr = _Umove(_Myfirst, _VEC_ITER_BASE(_Where),_Newvec);    // copy prefix_Ptr = _Ufill(_Ptr, _Count, _Val);  // add new stuff_Umove(_VEC_ITER_BASE(_Where), _Mylast, _Ptr);  // copy suffix//内存释放与变量更新}
1
2
3
4
5
6
7
8
9
10
11
12
13

这种情况下，数据从原始容器移动到新分配内存时是从前到后移动的

    else if ((size_type)(_Mylast - _VEC_ITER_BASE(_Where)) < _Count){   // new stuff spills off end_Umove(_VEC_ITER_BASE(_Where), _Mylast,_VEC_ITER_BASE(_Where) + _Count);   // copy suffix_Ufill(_Mylast, _Count - (_Mylast - _VEC_ITER_BASE(_Where)),_Val);  // insert new stuff off end_Mylast += _Count;std::fill(_VEC_ITER_BASE(_Where), _Mylast - _Count,_Val);  // insert up to old end}
1
2
3
4
5
6
7
8
9
10

            {   // new stuff can all be assigned_Ty _Tmp = _Val;    // in case _Val is in sequencepointer _Oldend = _Mylast;_Mylast = _Umove(_Oldend - _Count, _Oldend,_Mylast);   // copy suffix_STDEXT _Unchecked_move_backward(_VEC_ITER_BASE(_Where), _Oldend - _Count,_Oldend);   // copy holestd::fill(_VEC_ITER_BASE(_Where), _VEC_ITER_BASE(_Where) + _Count,_Tmp);  // insert into hole}
1
2
3
4
5
6
7
8
9
10
11

4、erase()操作

iterator erase(const_iterator _First_arg,const_iterator _Last_arg){   // erase [_First, _Last)iterator _First = _Make_iter(_First_arg);iterator _Last = _Make_iter(_Last_arg);if (_First != _Last){   // worth doing, copy down over holepointer _Ptr = _STDEXT unchecked_copy(_VEC_ITER_BASE(_Last), _Mylast,_VEC_ITER_BASE(_First));_Destroy(_Ptr, _Mylast);_Mylast = _Ptr;}return (_First);}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

主要操作就是将后半部分的有效元素向前拷贝，并将后面空间的无效元素析构，并更新变量

5、()操作

()操作最终都会调用到下面的函数，主要操作是首先擦除容器中已有的全部元素，在从头开始插入Count个Val元素

void _Assign_n(size_type _Count, const _Ty& _Val){   // assign _Count * _Val_Ty _Tmp = _Val;    // in case _Val is in sequenceerase(begin(), end());insert(begin(), _Count, _Tmp);}
1
2
3
4
5
6

五、基本使用

在经过上述对内部实现的分析后，再来理解相应接口就变得简单得多。

对外接口主要可以分为：

ector c
vector  c1(c2)
vector  c(n)
vector  c(n, elem)
vector  c(beg,end)
c.~ vector ()
1
2
3
4
5
6

c.push_back(elem)
c.pop_back()
c.insert(pos,elem)
c.insert(pos,n,elem)
c.insert(pos,beg,end)
c.erase(pos)
c.erase(beg,end)
c.clear()
c.assign(beg,end)
c.assign(n,elem)
1
2
3
4
5
6
7
8
9
10

c.capacity()
c.max_size()
c.resize(num)
c.reserve()
c.size()
1
2
3
4
5

c.begin()
c.end()
c.rbegin()
c.rend()
1
2
3
4

operator[]
c.at(idx)
c.front()
c.back()
1
2
3
4