本文共 5938 字，大约阅读时间需要 19 分钟。

_Deque_base 用于维护一维的指针

//如果一维数组不够用了，需要动态开辟一个新的的一维数组，	//将原数组中的保存的缓冲区地址的指针全部复制到新的一维数组中	//  _Tp** _M_map;  //一维数组  size_t _M_map_size;  //一位数组的大小  iterator _M_start; // 一位数组的起始迭代器  iterator _M_finish; //一位数组的末尾迭代器

//每次进行分配的时候，只分配一个一维指针指向的数组的大小  _Tp* _M_allocate_node()    {
    return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); }

一维数组的开辟于

//初始化一维的数组template 
   
    void_Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements){
     size_t __num_nodes =     __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;	//计算map大小  _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);  _M_map = _M_allocate_map(_M_map_size);	//获得一维数组的起始地址与终止地址  _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;  _Tp** __nfinish = __nstart + __num_nodes;      __STL_TRY {
     	//开辟第二维的数组，一维数组的每一个元素中存放第二维数组的起始地址    _M_create_nodes(__nstart, __nfinish);  }  __STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size),                 _M_map = 0, _M_map_size = 0));  //设置一维数组的迭代器的指针  _M_start._M_set_node(__nstart);  _M_finish._M_set_node(__nfinish - 1);  _M_start._M_cur = _M_start._M_first;  _M_finish._M_cur = _M_finish._M_first +               __num_elements % __deque_buf_size(sizeof(_Tp));}template 
    
     void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish){
     _Tp** __cur;  __STL_TRY {
     	//循环开辟第二维的数组    for (__cur = __nstart; __cur < __nfinish; ++__cur)      *__cur = _M_allocate_node();  }  __STL_UNWIND(_M_destroy_nodes(__nstart, __cur));}
    
   

deque迭代器的指针

_Tp* _M_cur;  //指向当前节点  _Tp* _M_first; //指向当前节点所在缓冲区起始节点  _Tp* _M_last; //指向当前节点所在缓冲区终止节点  //deque 底层是一个可以动态扩容的二维数组，  _Map_pointer _M_node; //指向当前节点所在缓冲区

push_back

void push_back(const value_type& __t) {
     	//如果deque还有备用节点供插入，则直接在备用节点插入    if (_M_finish._M_cur != _M_finish._M_last - 1) {
         construct(_M_finish._M_cur, __t);      ++_M_finish._M_cur;    }    //否则进行动态扩容后再插入    else      _M_push_back_aux(__t);  }

_M_push_back_aux

void deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t){
     value_type __t_copy = __t;  _M_reserve_map_at_back();  //在一维数组的结尾位置分配一块连续的内存  *(_M_finish._M_node + 1) = _M_allocate_node();  __STL_TRY {
     	//插入元素    construct(_M_finish._M_cur, __t_copy);	//设置一维数组的结尾指针    _M_finish._M_set_node(_M_finish._M_node + 1);	//当前位置设置为新申请的数组的开始位置    _M_finish._M_cur = _M_finish._M_first;  }  __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));}

insert

template 
   
     template 
    
     void deque<_Tp,_Alloc>::insert(iterator __pos,                          _ForwardIterator __first, _ForwardIterator __last,                          forward_iterator_tag) {
     size_type __n = 0;  distance(__first, __last, __n);  //如果在起始位置插入  if (__pos._M_cur == _M_start._M_cur) {
     	//在deque的前面进行扩容    iterator __new_start = _M_reserve_elements_at_front(__n);    __STL_TRY {
       	//用__first 到 __last中的元素填充新扩容的数组      uninitialized_copy(__first, __last, __new_start);      _M_start = __new_start;    }    __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));  }  //如果插入点在末尾位置  else if (__pos._M_cur == _M_finish._M_cur) {
     	//在deque的结尾处进行扩容    iterator __new_finish = _M_reserve_elements_at_back(__n);    __STL_TRY {
       //用__first 到 __last中的元素填充新扩容的数组      uninitialized_copy(__first, __last, _M_finish);      _M_finish = __new_finish;    }    __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,                                   __new_finish._M_node + 1));  }  //在中间位置进行插入  else    _M_insert_aux(__pos, __first, __last, __n);}
    
   

_M_insert_aux

template 
   
     template 
    
     void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,                                      _ForwardIterator __first,                                      _ForwardIterator __last,                                      size_type __n){
   	//__elemsbefore当前位置到起始的元素的个数  const difference_type __elemsbefore = __pos - _M_start;  size_type __length = size();  //如果插入点的位置到起始的位置的元素个数小于deque总元素个数的一半  //则在deque前面进行扩容，移动的元素的个数较少，效率相对较高  if (__elemsbefore < __length / 2) {
     	//新开辟__n个位置    iterator __new_start = _M_reserve_elements_at_front(__n);    iterator __old_start = _M_start;    __pos = _M_start + __elemsbefore;	//先将原来的前半部分元素向前移动，再将__first 到 __last 位置的元素插入到__pos开始的位置处    __STL_TRY {
         if (__elemsbefore >= difference_type(__n)) {
           iterator __start_n = _M_start + difference_type(__n); 		        uninitialized_copy(_M_start, __start_n, __new_start);        _M_start = __new_start;        copy(__start_n, __pos, __old_start);        copy(__first, __last, __pos - difference_type(__n));      }      else {
           _ForwardIterator __mid = __first;        advance(__mid, difference_type(__n) - __elemsbefore);        __uninitialized_copy_copy(_M_start, __pos, __first, __mid,                                  __new_start);        _M_start = __new_start;        copy(__mid, __last, __old_start);      }    }    __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));  }  //从deque的末尾处进行扩容， 过程与上面的一样  else {
       iterator __new_finish = _M_reserve_elements_at_back(__n);    iterator __old_finish = _M_finish;    const difference_type __elemsafter =       difference_type(__length) - __elemsbefore;    __pos = _M_finish - __elemsafter;    __STL_TRY {
         if (__elemsafter > difference_type(__n)) {
           iterator __finish_n = _M_finish - difference_type(__n);        uninitialized_copy(__finish_n, _M_finish, _M_finish);        _M_finish = __new_finish;        copy_backward(__pos, __finish_n, __old_finish);        copy(__first, __last, __pos);      }      else {
           _ForwardIterator __mid = __first;        advance(__mid, __elemsafter);        __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);        _M_finish = __new_finish;        copy(__first, __mid, __pos);      }    }    __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,                                   __new_finish._M_node + 1));  }}
    
   

转载地址：http://konwi.baihongyu.com/