STL源码阅读(四) (SGI STL v3.3)
stl_deque.h (<deque>)
// deque的内存管理，分配一段内存_M_map用来存储指向缓存区域的指针，每当缓存区域buffer不足时，分配一段新的缓存区域，然后// 将指向该区域的指针添加到_M_map中。buffer大小的分配原则是，当sizeof(_Tp) > 512时，分配的缓存大小sizeof(_Tp)；否则，// 分配的缓存大小为sizeof(_Tp) * (512 / sizeof(_Tp))；template class _Deque_alloc_base; // 每个类中保留两个分配器对象，_M_map_allocator, _M_node_allocatortemplate class _Deque_alloc_base<_Tp, _Alloc, true>; // 使用静态内存分配器 {... _Tp** _M_map; // 指向缓存结点的指针 size_T _M_map_size; // map的大小...}
// deque迭代器，迭代器类型随机迭代器random_access_iterator_tag。template struct _Deque_iterator {... // 迭代器中维护四个指针 _Tp* _M_cur; // 指向当前缓存区域已用空间的最后一个元素 _Tp* _M_first; // 指向当前缓存区域的开始 _Tp* _M_last; // 指向当前缓存区域的末尾 _Map_pointer _M_node; // 指向当前正在使用的那一个缓存区域...}// 注意迭代器迭代元素的方式，迭代器所处理的内存空间从整体上看不是连续的，但从局部看是连续的// 计算迭代器的差值difference_type operator-(const _Self& __x) const { return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) + (_M_cur - _M_first) + (__x._M_last - __x._M_cur);}_Self& operator+=(difference_type __n){ difference_type __offset = __n + (_M_cur - _M_first); if (__offset >= 0 && __offset < difference_type(_S_buffer_size())) _M_cur += __n; else { difference_type __node_offset = __offset > 0 ? __offset / difference_type(_S_buffer_size()) : -difference_type((-__offset - 1) / _S_buffer_size()) - 1; _M_set_node(_M_node + __node_offset); _M_cur = _M_first + (__offset - __node_offset * difference_type(_S_buffer_size())); } return *this;}// deque基类template class _Deque_base : public _Deque_alloc_base<_Tp,_Alloc, _Alloc_traits<_Tp, _Alloc>::_S_instanceless> { ... typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator; // 除了从_Deque_alloc_base继承过来的数据成员，还维护两个迭代器，分别指向元素的首部和尾部 iterator _M_first; // 指向第一个元素 iterator _M_finish; // 指向最后一个元素的下一个元素 enum { _S_initial_map_size = 8 }; // _M_map的初始大小为8 ... }// 初始化__num_elements个节点，最小结点数8个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; _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2); _M_map = _M_allocate_map(_M_map_size); // 当多分配两个结点 // 指向_M_map的最中间，向头部和尾部的扩展能力相同 _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 class deque : protected _Deque_base<_Tp, _Alloc>;// 注意swap的实现void swap(deque& __x) { __STD::swap(_M_start, __x._M_start); __STD::swap(_M_finish, __x._M_finish); __STD::swap(_M_map, __x._M_map); __STD::swap(_M_map_size, __x._M_map_size);}// 当push_front, push_back, insert, resize添加元素超出原空间时，需要// 重新分配空间map，将原来的_M_map拷贝到新map中，并没有copy缓冲区的元素template void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add, bool __add_at_front){ size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1; size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; _Map_pointer __new_nstart; if (_M_map_size > 2 * __new_num_nodes) { __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2 + (__add_at_front ? __nodes_to_add : 0); if (__new_nstart < _M_start._M_node) copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart); else copy_backward(_M_start._M_node, _M_finish._M_node + 1, __new_nstart + __old_num_nodes); } else { size_type __new_map_size = _M_map_size + max(_M_map_size, __nodes_to_add) + 2; _Map_pointer __new_map = _M_allocate_map(__new_map_size); __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 + (__add_at_front ? __nodes_to_add : 0); copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart); _M_deallocate_map(_M_map, _M_map_size); _M_map = __new_map; _M_map_size = __new_map_size; } _M_start._M_set_node(__new_nstart); _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);}
参考资料
-
-