|
成为随机迭代器所做的工作
_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;
}
_Self operator+(difference_type __n) const
{
_Self __tmp = *this;
return __tmp += __n;
}
_Self& operator-=(difference_type __n)
{
return *this += -__n;
}
_Self operator-(difference_type __n) const
{
_Self __tmp = *this;
return __tmp -= __n;
}
reference operator[](difference_type __n) const
{
return *(*this + __n);
}
bool operator==(const _Self& __x) const
{
return _M_cur == __x._M_cur;
}
bool operator!=(const _Self& __x) const
{
return !(*this == __x);
}
///按迭代器所在区段头指针在中控器中的存储位置进行比较
///若在同一区段,再比较迭代器确指指针
bool operator<(const _Self& __x) const
{
return (_M_node == __x._M_node) ?
(_M_cur < __x._M_cur) : (_M_node < __x._M_node);
}
bool operator>(const _Self& __x) const
{
return __x < *this;
}
bool operator<=(const _Self& __x) const
{
return !(__x < *this);
}
bool operator>=(const _Self& __x) const
{
return !(*this < __x);
}
void _M_set_node(_Map_pointer __new_node)
{
///设置迭代器所在区段
_M_node = __new_node;
_M_first = *__new_node;
_M_last = _M_first + difference_type(_S_buffer_size());
}
};
template
inline _Deque_iterator<_Tp, _Ref, _Ptr> operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x) { return __x + __n; } /// Deque base class. Its constructor and destructor allocate /// (but don't initialize) storage. This makes exception safety easier. template
class _Deque_base { public: typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator; typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; typedef _Alloc allocator_type; allocator_type get_allocator() const { return allocator_type(); } _Deque_base(const allocator_type&, size_t __num_elements) : _M_map(0), _M_map_size(0), _M_start(), _M_finish() { _M_initialize_map(__num_elements); } _Deque_base(const allocator_type&) : _M_map(0), _M_map_size(0), _M_start(), _M_finish() {} ~_Deque_base(); protected: void _M_initialize_map(size_t); void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish); void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish); ///默认中控器大小为8,即可创建8个区段 enum { _S_initial_map_size = 8 }; protected: _Tp** _M_map; ///中控器,一个指向_Tp类型数组指针的数组 ///中控器大小,决定了不扩充中控器时最多可容纳的区段数 size_t _M_map_size; iterator _M_start; ///起始迭代器 iterator _M_finish; ///结束迭代器,其实际指向最后一个元素的下一个位置 typedef simple_alloc<_Tp, _Alloc> _Node_alloc_type; typedef simple_alloc<_Tp*, _Alloc> _Map_alloc_type; ///每次分配、回收一个区段 _Tp* _M_allocate_node() { return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); } void _M_deallocate_node(_Tp* __p) { _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); } ///中控器内存的分配与回收,实际是Tp* 类型数组的分配、回收 _Tp** _M_allocate_map(size_t __n) { return _Map_alloc_type::allocate(__n); } void _M_deallocate_map(_Tp** __p, size_t __n) { _Map_alloc_type::deallocate(__p, __n); } }; /// Non-inline member functions from _Deque_base. template
_Deque_base<_Tp,_Alloc>::~_Deque_base() { if (_M_map) { ///回收各个区段的内存 _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1); ///回收中控器的内存 _M_deallocate_map(_M_map, _M_map_size); } } ///初始化中控器 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); ///使用中控器的中间部分,这样可以保证前后都可以继续扩充区段 _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2; _Tp** __nfinish = __nstart + __num_no |