时间戳

首页 > 技术文章 > 《STL源码剖析》——Vector

《STL源码剖析》——Vector

xhb19960928 2019-11-11 23:05 原文

vector

vector的源码分为多个文件：vector、<<stl_vector.h>>

vector的底层实现是在<<stl_vector.h>>中

1 vector的基本架构

vector的基本架构如下图所示：

2 vector内的成员变量

在vector本身中，有三个成员变量：_M_start、_M_finish和_M_end_of_storage

_M_start对应的是vector的begin()（目前使用空间的头）

_M_finish对应的是vector的end()（目前使用空间的尾）

_M_end_of_storage对应的则是当前vector的容量（目前可用空间的尾，注意与_M_finish的区别）

3 vector的iterator

vector的iterator是__gnu_cxx::__normal_iterator<pointer, vector>类型的，__normal_iterator的主要声明如下：

    template<typename _Iterator, typename _Container>
    class __normal_iterator {
    protected:
      _Iterator _M_current;
    
      typedef iterator_traits<_Iterator>		__traits_type;
    
    public:
      typedef _Iterator					iterator_type;
      typedef typename __traits_type::iterator_category iterator_category;
      typedef typename __traits_type::value_type  	value_type;
      typedef typename __traits_type::difference_type 	difference_type;
      typedef typename __traits_type::reference 	reference;
      typedef typename __traits_type::pointer   	pointer;
    	
    	// ...
    }

4 push_back与扩容

重点观察一下vector的push_back方法，其源码如下：

    void
    push_back(const value_type& __x) {
        	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) {
        		_GLIBCXX_ASAN_ANNOTATE_GROW(1);
        		_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
        	  ++this->_M_impl._M_finish;
        		_GLIBCXX_ASAN_ANNOTATE_GREW(1);
        	} else _M_realloc_insert(end(), __x);
    }

push_back函数分为以下步骤：

  1. 先检查当前是否还存在可用空间，即_M_finish是否等于_M_end_of_storage，如果成立，则跳到2，不成立跳到3
  2. 构造一个新的元素并插入vector中，并调整_M_finish指针
  3. 调用_M_realloc_insert，另寻他处，重新开辟空间，将原来的vector中的元素都拷贝到新的vector中，并将新元素也插入vector中，并销毁原来的vector以及其中的元素（步骤3开销很大）

注意：如果对vector的任何操作，导致了vector的重新分配行为，那么原有的iterator都会全部失效

5 insert与扩容

vector提供了很多种的insert，以其中一个为例：在指定的iterator之前插入n个初值为x的元素形式的insert

insert是可能触发vector的重新分配行为的

例子中insert的源码如下：

    template<typename _Tp, typename _Alloc>
    void
    vector<_Tp, _Alloc>::
    _M_fill_insert(iterator __position, size_type __n, const value_type& __x) {
        	if (__n != 0) {
        		if (size_type(this->_M_impl._M_end_of_storage	- this->_M_impl._M_finish) >= __n) {
        #if __cplusplus < 201103L
        	    value_type __x_copy = __x;
        #else
        	    _Temporary_value __tmp(this, __x);
        	    value_type& __x_copy = __tmp._M_val();
        #endif
        	    const size_type __elems_after = end() - __position;
        	    pointer __old_finish(this->_M_impl._M_finish);
        	    if (__elems_after > __n) {
        			  _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
        			  std::__uninitialized_move_a(this->_M_impl._M_finish - __n, this->_M_impl._M_finish, this->_M_impl._M_finish, _M_get_Tp_allocator());
        			  this->_M_impl._M_finish += __n;
        			  _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
        			  _GLIBCXX_MOVE_BACKWARD3(__position.base(), __old_finish - __n, __old_finish);
        			  std::fill(__position.base(), __position.base() + __n, __x_copy);
        			} else {
        			  _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
        			  this->_M_impl._M_finish =
        		    std::__uninitialized_fill_n_a(this->_M_impl._M_finish, __n - __elems_after, __x_copy, _M_get_Tp_allocator());
        			  _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
        			  std::__uninitialized_move_a(__position.base(), __old_finish, this->_M_impl._M_finish, _M_get_Tp_allocator());
        			  this->_M_impl._M_finish += __elems_after;
        			  _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
        			  std::fill(__position.base(), __old_finish, __x_copy);
        			}
          } else {
        		const size_type __len = _M_check_len(__n, "vector::_M_fill_insert");
            const size_type __elems_before = __position - begin();
            pointer __new_start(this->_M_allocate(__len));
            pointer __new_finish(__new_start);
            __try {
        		  // See _M_realloc_insert above.
        		  std::__uninitialized_fill_n_a(__new_start + __elems_before, __n, __x, _M_get_Tp_allocator());
        		  __new_finish = pointer();
        		  __new_finish = std::__uninitialized_move_if_noexcept_a(this->_M_impl._M_start, __position.base(), __new_start, _M_get_Tp_allocator());
        		  __new_finish += __n;
        
        		  __new_finish = std::__uninitialized_move_if_noexcept_a(__position.base(), this->_M_impl._M_finish, __new_finish, _M_get_Tp_allocator());
        		} __catch(...) {
        		  if (!__new_finish)
        		    std::_Destroy(__new_start + __elems_before, __new_start + __elems_before + __n, _M_get_Tp_allocator());
        		  else
        		    std::_Destroy(__new_start, __new_finish,
        			  _M_get_Tp_allocator());
        			  _M_deallocate(__new_start, __len);
        		  __throw_exception_again;
        		}
            std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
        	    _M_get_Tp_allocator());
            _GLIBCXX_ASAN_ANNOTATE_REINIT;
            _M_deallocate(this->_M_impl._M_start,
        	    this->_M_impl._M_end_of_storage
        	    - this->_M_impl._M_start);
            this->_M_impl._M_start = __new_start;
            this->_M_impl._M_finish = __new_finish;
            this->_M_impl._M_end_of_storage = __new_start + __len;
        		}
        	}
    }

这个重载的insert源码比较长，但是大致思路如下：

  1. if (__n != 0) 检查插入的元素个数n是否为0

  2. if (size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_finish) >= __n) 检查可用空间是否大于等于n，如果此条成立还需要区分新插入的元素个素n与安插点之后的元素个数__elems_after的大小情况

    2.1 n < __elems_after

    2.2 n ≥ __elems_after

  3. 如果第二条不成立，那么就需要对vector进行扩容，那么新vector的长度取决于max(旧长度 x 2，(旧长度 + n个新增元素) x 2)

    需要注意的是，新的vector不必是在旧的vector上的扩展，图中画在一起，只是为了方便

推荐阅读