序列容器之vector · STL源碼剖析

### 前言 ? 在STL編程中，我們最常用到的就是容器，容器可分為序列容器和關聯容器；本文記錄的是我們經常使用的序列容器之vector，vector的數據安排和操作方式類似于C++內置數組類型array，唯一的區別就是在于空間的靈活運用。內置數組array是靜態空間，一旦分配了內存空間就不能改變，而vector容器可以根據用戶數據的變化而不斷調整內存空間的大小。 ? ? ?vector容器有已使用空間和可用空間，已使用空間是指vector容器的大小，可用空間是指vector容器可容納的最大數據空間capacity。vector容器是占用一段連續線性空間，所以vector容器的迭代器就等價于原生態的指針；vector的實現依賴于內存的配置和內存的初始化，以及迭代器。其中內存的配置是最重要的，因為每當配置內存空間時，可能會發生數據移動，回收舊的內存空間，如果不斷地重復這些操作會降低操作效率，所有vector容器在分配內存時，并不是用戶數據占多少就分配多少，它會分配一些內存空間留著備用，即是用戶可用空間。關于vector類定義可參考[《](http://zh.cppreference.com/w/cpp/container/vector)[vector](http://zh.cppreference.com/w/cpp/container/vector)[庫文件》](http://zh.cppreference.com/w/cpp/container/vector)或者[《](http://msdn.microsoft.com/zh-cn/library/9xd04bzs.aspx)[MSDN庫的vector](http://msdn.microsoft.com/zh-cn/library/9xd04bzs.aspx)[類》](http://msdn.microsoft.com/zh-cn/library/9xd04bzs.aspx)；以下源代碼在SGI STL的文件<stl_vector.h>中。 ### vector容器 ### vector容器的數據結構 ? ? ?vector容器采用的是線性連續空間的數據結構，使用兩個迭代器來管理這片連續內存空間，這兩個迭代器分別是指向目前使用空間的頭start和指向目前使用空間的尾finish，兩個迭代器的范圍[start,finish)表示容器的大小size()。由于為了提高容器的訪問效率，為用戶分配內存空間時，會分配多余的備用空間，即容器的容量，以迭代器end_of_storage作為可用空間的尾，則容器的容量capacity()為[start,end_of_storage)范圍的線性連續空間。 ~~~ //Alloc是SGI STL的空間配置器，默認是第二級配置器 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > class vector : protected _Vector_base<_Tp, _Alloc> { ... protected: _Tp* _M_start;//表示目前使用空間的頭 _Tp* _M_finish;//表示目前使用空間的尾 _Tp* _M_end_of_storage;//表示目前可用空間的尾 ... }; ~~~ ? 下面給出vector的數據結構圖： ![](https://box.kancloud.cn/2016-07-12_5784b877725b4.jpg) ### vector迭代器 ?vector容器維護的空間的線性連續的，所以普通指針也可以作為迭代器，滿足vector的訪問操作；如：operator*，operator->，operator++，operator--，operator+，operator-，operator+=，operator-=等操作；同時vector容器支持隨機訪問，所以，vector提供的是隨機訪問迭代器。 ~~~ //Alloc是SGI STL的空間配置器，默認是第二級配置器 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > class vector : protected _Vector_base<_Tp, _Alloc> { public://vector的內嵌型別定義,是iterator_traits<I>服務的類型 typedef _Tp value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type* iterator;//vector容器的迭代器是普通指針 typedef const value_type* const_iterator; ... public://以下定義vector迭代器 iterator begin() { return _M_start; }//指向已使用空間頭的迭代器 const_iterator begin() const { return _M_start; } iterator end() { return _M_finish; }//指向已使用空間尾的迭代器 const_iterator end() const { return _M_finish; } reverse_iterator rbegin() { return reverse_iterator(end()); } const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } ... }; ~~~ ### vector的構造函數和析構函數 ? 這里把vector容器的構造函數列出來講解，主要是我們平常使用vector容器時，首先要要定義相應的容器對象，所以，如果我們對vector容器的構造函數了解比較透徹時，在應用當中就會比較得心應手。在以下源碼的前面我會總結出vector容器的構造函數及其使用方法。 ~~~ /*以下是vector容器的構造函數*********************** /************************************ *** //默認構造函數*************************** * explicit vector( const Allocator& alloc = Allocator() ); * *** //具有初始值和容器大小的構造函數******************* * explicit vector( size_type count, * * const T& value = T(), * * const Allocator& alloc = Allocator()); * * vector( size_type count, * * const T& value, * * const Allocator& alloc = Allocator()); * *** //只有容器大小的構造函數*********************** * explicit vector( size_type count ); * *** //用兩個迭代器區間表示容器大小的構造函數*************** * template< class InputIt > * * vector( InputIt first, InputIt last, * * const Allocator& alloc = Allocator() ); * *** //拷貝構造函數*************************** * vector( const vector& other ); * * vector( const vector& other, const Allocator& alloc ); * *** //移動構造函數*************************** * vector( vector&& other ); * * vector( vector&& other, const Allocator& alloc ); * *** //用初始列表的值構造容器，列表內的元素值可以不同*********** * vector( std::initializer_list<T> init, * * const Allocator& alloc = Allocator() ); * *************************************/ explicit vector(const allocator_type& __a = allocator_type()) : _Base(__a) {}//默認構造函數 vector(size_type __n, const _Tp& __value, const allocator_type& __a = allocator_type()) : _Base(__n, __a)//構造函數，里面包含n個初始值為value的元素 //全局函數，填充值函數，即從地址M_start開始連續填充n個初始值為value的元素 { _M_finish = uninitialized_fill_n(_M_start, __n, __value); } explicit vector(size_type __n)//該構造函數不接受初始值，只接受容易包含元素的個數n : _Base(__n, allocator_type()) { _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); } vector(const vector<_Tp, _Alloc>& __x) : _Base(__x.size(), __x.get_allocator())//拷貝構造函數 { _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); } #ifdef __STL_MEMBER_TEMPLATES // Check whether it's an integral type. If so, it's not an iterator. /*這個是某個區間的構造函數，首先判斷輸入是否為整數_Integral() *采用__type_traits技術 */ template <class _InputIterator> vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) { typedef typename _Is_integer<_InputIterator>::_Integral _Integral; _M_initialize_aux(__first, __last, _Integral()); } template <class _Integer> //若輸入為整數，則調用該函數 void _M_initialize_aux(_Integer __n, _Integer __value, __true_type) { _M_start = _M_allocate(__n); _M_end_of_storage = _M_start + __n; _M_finish = uninitialized_fill_n(_M_start, __n, __value); } template <class _InputIterator> //若輸入不是整數，則采用Traits技術繼續判斷迭代器的類型 void _M_initialize_aux(_InputIterator __first, _InputIterator __last, __false_type) { _M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first)); } #else vector(const _Tp* __first, const _Tp* __last, const allocator_type& __a = allocator_type()) : _Base(__last - __first, __a) { _M_finish = uninitialized_copy(__first, __last, _M_start); } #endif /* __STL_MEMBER_TEMPLATES */ ~vector() { destroy(_M_start, _M_finish); }//析構函數 ~~~ ### vector容器的成員函數 ?vector容器的成員函數使我們訪問容器時經常會用到，為了加深對其了解，這里單獨對成員函數源碼進行了詳細的注解。 ~~~ /*以下是容器的一些成員函數*/ size_type size() const//vector容器大小(已使用空間大小)，即容器內存儲元素的個數 { return size_type(end() - begin()); } size_type max_size() const//返回可容納最大元素數 { return size_type(-1) / sizeof(_Tp); } size_type capacity() const//vector容器可用空間的大小 { return size_type(_M_end_of_storage - begin()); } bool empty() const//判斷容器是否為空 { return begin() == end(); } reference operator[](size_type __n) { return *(begin() + __n); }//返回指定位置的元素 const_reference operator[](size_type __n) const { return *(begin() + __n); } #ifdef __STL_THROW_RANGE_ERRORS //若用戶要求的空間大于可用空間，拋出錯去信息，即越界檢查 void _M_range_check(size_type __n) const { if (__n >= this->size()) __stl_throw_range_error("vector"); } reference at(size_type __n)//訪問指定元素，并且進行越界檢查 { _M_range_check(__n); return (*this)[__n]; }//訪問前，先進行越界檢查 const_reference at(size_type __n) const { _M_range_check(__n); return (*this)[__n]; } #endif /* __STL_THROW_RANGE_ERRORS */ void reserve(size_type __n) {//改變可用空間內存大小 if (capacity() < __n) { const size_type __old_size = size(); //重新分配大小為n的內存空間，并把原來數據復制到新分配空間 iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish); destroy(_M_start, _M_finish);//釋放容器元素對象 _M_deallocate(_M_start, _M_end_of_storage - _M_start);//回收原來的內存空間 //調整迭代器所指的地址,因為原來迭代器所指的地址已經失效 _M_start = __tmp; _M_finish = __tmp + __old_size; _M_end_of_storage = _M_start + __n; } } reference front() { return *begin(); }//返回第一個元素 const_reference front() const { return *begin(); } reference back() { return *(end() - 1); }//返回容器最后一個元素 const_reference back() const { return *(end() - 1); } void push_back(const _Tp& __x) {//在最尾端插入元素 if (_M_finish != _M_end_of_storage) {//若有可用的內存空間 construct(_M_finish, __x);//構造對象 ++_M_finish; } else//若沒有可用的內存空間,調用以下函數，把x插入到指定位置 _M_insert_aux(end(), __x); } void push_back() { if (_M_finish != _M_end_of_storage) { construct(_M_finish); ++_M_finish; } else _M_insert_aux(end()); } void swap(vector<_Tp, _Alloc>& __x) { /*交換容器的內容 *這里使用的方法是交換迭代器所指的地址 */ __STD::swap(_M_start, __x._M_start); __STD::swap(_M_finish, __x._M_finish); __STD::swap(_M_end_of_storage, __x._M_end_of_storage); } iterator insert(iterator __position, const _Tp& __x) {//把x值插入到指定的位置 size_type __n = __position - begin(); if (_M_finish != _M_end_of_storage && __position == end()) { construct(_M_finish, __x); ++_M_finish; } else _M_insert_aux(__position, __x); return begin() + __n; } iterator insert(iterator __position) { size_type __n = __position - begin(); if (_M_finish != _M_end_of_storage && __position == end()) { construct(_M_finish); ++_M_finish; } else _M_insert_aux(__position); return begin() + __n; } void insert (iterator __pos, size_type __n, const _Tp& __x) { //在pos位置連續插入n個初始值為x的元素 _M_fill_insert(__pos, __n, __x); } void _M_fill_insert (iterator __pos, size_type __n, const _Tp& __x); void pop_back() {//取出最尾端元素 --_M_finish; destroy(_M_finish);//析構對象 } iterator erase(iterator __position) {//擦除指定位置元素 if (__position + 1 != end()) copy(__position + 1, _M_finish, __position);//后續元素前移一位 --_M_finish; destroy(_M_finish);//析構對象 return __position; } iterator erase(iterator __first, iterator __last) {//擦除兩個迭代器區間的元素 iterator __i = copy(__last, _M_finish, __first);//把不擦除的元素前移 destroy(__i, _M_finish);//析構對象 _M_finish = _M_finish - (__last - __first);//調整finish的所指的位置 return __first; } void resize(size_type __new_size, const _Tp& __x) {//改變容器中可存儲的元素個數，并不會分配新的空間 if (__new_size < size()) //若調整后的內存空間比原來的小 erase(begin() + __new_size, end());//擦除多余的元素 else insert(end(), __new_size - size(), __x);//比原來多余的空間都賦予初值x } void resize(size_type __new_size) { resize(__new_size, _Tp()); } void clear() { erase(begin(), end()); }//清空容器 // assign(), a generalized assignment member function. Two // versions: one that takes a count, and one that takes a range. // The range version is a member template, so we dispatch on whether // or not the type is an integer. /*該函數有兩種類型： void assign( size_type count, const T& value ); template< class InputIt > void assign( InputIt first, InputIt last ); */ //把容器內容替換為n個初始值為value void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); } void _M_fill_assign(size_type __n, const _Tp& __val); #ifdef __STL_MEMBER_TEMPLATES template <class _InputIterator> void assign(_InputIterator __first, _InputIterator __last) { typedef typename _Is_integer<_InputIterator>::_Integral _Integral; _M_assign_dispatch(__first, __last, _Integral()); } template <class _Integer> void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) { _M_fill_assign((size_type) __n, (_Tp) __val); } template <class _InputIter> void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type) { _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first)); } template <class _InputIterator> void _M_assign_aux(_InputIterator __first, _InputIterator __last, input_iterator_tag); template <class _ForwardIterator> void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag); #endif /* __STL_MEMBER_TEMPLATES */ ~~~ ? ??根據以上成員函數的注釋，這里對其中幾個函數進一步詳細的講解：iterator erase(iterator __first, iterator __last)，void insert (iterator __pos, size_type __n, const _Tp& __x)； ? 其中擦除函數是擦除輸入迭代器之間的元素，但是沒有回收內存空間，只是把內存空間作為備用空間，首先看下該函數的源代碼： ~~~ iterator erase(iterator __first, iterator __last) {//擦除兩個迭代器區間的元素 iterator __i = copy(__last, _M_finish, __first);//把不擦除的元素前移 destroy(__i, _M_finish);//析構對象 _M_finish = _M_finish - (__last - __first);//調整finish的所指的位置 return __first; } ~~~ ? ? ? ? ??根據上面函數的定義，我們可以知道，迭代器start和end_of_storage并沒有改變，只是調整迭代器finish，并析構待擦除元素對象；下面通過圖解進行分析： ![](https://box.kancloud.cn/2016-07-12_5784b877896e7.jpg) ? 插入元素函數是在指定位置position上連續插入n個初始值為x的元素，根據插入元素個數和可用空間大小的比較，分別進行不同的初始化，詳細見源碼分析： ~~~ void insert (iterator __pos, size_type __n, const _Tp& __x) { //在pos位置連續插入n個初始值為x的元素 _M_fill_insert(__pos, __n, __x); } template <class _Tp, class _Alloc> void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n, const _Tp& __x) { if (__n != 0) {//當n不為0，插入才有效 if (size_type(_M_end_of_storage - _M_finish) >= __n) {//若有足夠的可用空間,即備用空間不小于新插入元素個數 _Tp __x_copy = __x; const size_type __elems_after = _M_finish - __position;//計算插入點之后的現有元素個數 iterator __old_finish = _M_finish; //case1-a：插入點之后的現有元素個數大于新插入元素個數 if (__elems_after > __n) { uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);//把[finish-n,finish)之間的數據復制[finish,finish+n) _M_finish += __n;//調整迭代器finish所指的位置 copy_backward(__position, __old_finish - __n, __old_finish);//把[position,old_finish-n)之間的數據復制[old_finish-n,old_finish) fill(__position, __position + __n, __x_copy);//在指定位置(插入點)填充初始值 } //case1-b：插入點之后的現有元素個數不大于新插入元素個數 else { uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);//先在可用空間填入n-elems_after個初始值x _M_finish += __n - __elems_after;//調整迭代器finish uninitialized_copy(__position, __old_finish, _M_finish);//把[position,old_finish)之間的數據復制到[old_finish,finish) _M_finish += __elems_after; fill(__position, __old_finish, __x_copy); } } //case2：若備用空間小于新插入元素個數 else {//若備用空間小于新插入元素個數，則分配新的空間 //并把原始數據復制到新的空間，調整迭代器 const size_type __old_size = size(); //獲取原始空間的大小 //新的空間為舊空間的兩倍，或為舊空間+新增長元素個數 const size_type __len = __old_size + max(__old_size, __n); //配置新的空間 iterator __new_start = _M_allocate(__len); iterator __new_finish = __new_start; __STL_TRY {//把插入點之前的原始數據復制到新的空間 __new_finish = uninitialized_copy(_M_start, __position, __new_start); //將新加入數據添加在[new_finish,new_finish+n) __new_finish = uninitialized_fill_n(__new_finish, __n, __x); //將插入點之后的原始數據復制到新空間 __new_finish = uninitialized_copy(__position, _M_finish, __new_finish); } //釋放原來空間的對象和內存 __STL_UNWIND((destroy(__new_start,__new_finish), _M_deallocate(__new_start,__len))); destroy(_M_start, _M_finish); _M_deallocate(_M_start, _M_end_of_storage - _M_start); //調整迭代器所指的位置 _M_start = __new_start; _M_finish = __new_finish; _M_end_of_storage = __new_start + __len; } } } ~~~ ? 下面對不同情況利用圖解方式對插入函數進行分析： ? ? ? case1-a：對應的源代碼解析中的case1-a情況； ![](https://box.kancloud.cn/2016-07-12_5784b877a28dd.jpg) ? ? ? ?case1-b：對應源碼剖析中的case1-b情況： ![](https://box.kancloud.cn/2016-07-12_5784b877c231d.jpg) ? ? ?case2：針對源碼剖析的case2情況： ![](https://box.kancloud.cn/2016-07-12_5784b877dc559.jpg) ### vector的操作符重載 ? 關于操作符重載的這里只給出源代碼的注釋： ~~~ template <class _Tp, class _Alloc> inline bool //操作符重載，判斷兩個容器是否相等，即容器大小和容器內容是否都相等 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { return __x.size() == __y.size() && equal(__x.begin(), __x.end(), __y.begin()); /*STL中equal函數的實現如下： * template<class InputIt1, class InputIt2> * bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2) * { * for (; first1 != last1; ++first1, ++first2) * { * if (!(*first1 == *first2)) * { * return false; * } * } * return true; * } */ } template <class _Tp, class _Alloc> inline bool operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { /*函數原型： template<class InputIt1, class InputIt2> bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2) { for ( ; (first1 != last1) && (first2 != last2); first1++, first2++ ) { if (*first1 < *first2) return true; if (*first2 < *first1) return false; } return (first1 == last1) && (first2 != last2); } */ return lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); } #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER template <class _Tp, class _Alloc> inline void swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) { __x.swap(__y); } template <class _Tp, class _Alloc> inline bool operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { return !(__x == __y); } template <class _Tp, class _Alloc> inline bool operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { return __y < __x; } template <class _Tp, class _Alloc> inline bool operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { return !(__y < __x); } template <class _Tp, class _Alloc> inline bool operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { return !(__x < __y); } #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ template <class _Tp, class _Alloc> vector<_Tp,_Alloc>& vector<_Tp,_Alloc>::operator=(const vector<_Tp, _Alloc>& __x) { if (&__x != this) { const size_type __xlen = __x.size(); if (__xlen > capacity()) { iterator __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end()); destroy(_M_start, _M_finish); _M_deallocate(_M_start, _M_end_of_storage - _M_start); _M_start = __tmp; _M_end_of_storage = _M_start + __xlen; } else if (size() >= __xlen) { iterator __i = copy(__x.begin(), __x.end(), begin()); destroy(__i, _M_finish); } else { copy(__x.begin(), __x.begin() + size(), _M_start); uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish); } _M_finish = _M_start + __xlen; } return *this; } ~~~ ### 總結 ? ?vector容器主要是對該數據結構的了解，并且掌握其中的成員函數，做到這兩點，對vector容器的使用就比較方便了。參考文獻：[【1】](http://www.aichengxu.com/view/33003)，[【2】](http://blog.csdn.net/hackbuteer1/article/details/7724547)，[【3】](http://blog.csdn.net/v_july_v/article/details/6681522)