|
finish; } catch(...) { _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); throw; } } else _M_insert_aux(__pos, __first, __last, __n); } template
typename deque<_Tp,_Alloc>::iterator deque<_Tp,_Alloc>::erase(iterator __first, iterator __last) { if (__first == _M_start && __last == _M_finish) { clear(); return _M_finish; } else { difference_type __n = __last - __first; difference_type __elems_before = __first - _M_start; if (__elems_before < difference_type((this->size() - __n) / 2)) { ///位于删除区间之间的元素少于之后的元素 copy_backward(_M_start, __first, __last); iterator __new_start = _M_start + __n; ///析构多余元素 destroy(_M_start, __new_start); ///回收未用区段 _M_destroy_nodes(__new_start._M_node, _M_start._M_node); _M_start = __new_start; } else { copy(__last, _M_finish, __first); iterator __new_finish = _M_finish - __n; destroy(__new_finish, _M_finish); _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1); _M_finish = __new_finish; } return _M_start + __elems_before; } } template
void deque<_Tp,_Alloc>::clear() { ///依次析构每个区段的对象元素,然后回收析构完的区段 for (_Map_pointer __node = _M_start._M_node + 1; __node < _M_finish._M_node; ++__node) ///对完整区段进行统一处理 { destroy(*__node, *__node + _S_buffer_size()); _M_deallocate_node(*__node); } if (_M_start._M_node != _M_finish._M_node) { ///所有元素分布在不少于两个区段上,对尚未处理的第一个和最后一个 ///区段进行处理 destroy(_M_start._M_cur, _M_start._M_last); destroy(_M_finish._M_first, _M_finish._M_cur); _M_deallocate_node(_M_finish._M_first); } else destroy(_M_start._M_cur, _M_finish._M_cur); _M_finish = _M_start; } /// Precondition: _M_start and _M_finish have already been initialized, /// but none of the deque's elements have yet been constructed. template
void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value) { _Map_pointer __cur; try { ///对完整区段统一处理 for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur) uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value); ///处理最后一个区段 uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value); } catch(...) { destroy(_M_start, iterator(*__cur, __cur)); throw; } } template
template
void deque<_Tp,_Alloc>::_M_range_initialize(_InputIterator __first, _InputIterator __last, input_iterator_tag) { _M_initialize_map(0); try { for ( ; __first != __last; ++__first) push_back(*__first); } catch(...) { clear(); throw; } } template
template
void deque<_Tp,_Alloc>::_M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag) { size_type __n = 0; distance(__first, __last, __n); _M_initialize_map(__n); _Map_pointer __cur_node; try { for (__cur_node = _M_start._M_node; __cur_node < _M_finish._M_node; ++__cur_node) { _ForwardIterator __mid = __first; advance(__mid, _S_buffer_size()); uninitialized_copy(__first, __mid, *__cur_node); __first = __mid; } uninitialized_copy(__first, __last, _M_finish._M_first); } catch(...) { destroy(_M_start, iterator(*__cur_node, __cur_node)); throw; } } /// Called only if _M_finish._M_cur == _M_finish._M_last - 1. template
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(); ///在新分配的区段上创建对象,调整deque相关状态 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; } catch(...) { _M_deallocate_node(*(_M_finish._M_node + 1)); throw; } } /// Called only if _M_finish._M_cur == _M_finish._M_last - 1. template
void deque<_Tp,_Alloc>::_M_push_back_aux() { _M_reserve_map_at_back(); *(_M_finish._M_node + 1) = _M_allocate_node(); try { construct(_M_finish._M_cur); _M_finish._M_set_node(_M_finish._M_node + 1); _M_finish._M_cur = _M_finish._M_first; } catch(...) { _M_deallocate_node(*(_M_finish._M_node + 1)); throw; } } ///和_M_push_back_aux实现大同小异 /// Called only if _M_start._M_cur == _M_start._M_first. template
void deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t) { value_type __t_copy = __t; _M_reserve_map_at_front(); *(_M_start._M_node - 1) = _M_allocate_node(); try { _M_start._M_set_node(_M_start._M_node - 1); _M_start._M_cur = _M_start._M_last - 1; construct(_M_start._M_cur, __t_copy); } catch(...) { ++_M_start; _M_deallocate_node(*(_M_start._M_node - 1)); throw; } } /// Called only if _M_start._M_cur == _M_start._M_first. template
void deque<_Tp,_Alloc>::_M_push_front_aux() { _M_reserve_map_at_front(); *(_M_start._M_node - 1) = _M_allocate_node(); try { _M_start._M_set_node(_M_start._M_node - 1); _M_start._M_cur = _M_start._M_last - 1; construct(_M_start._M_cur); } catch(...) { ++_M_start; _M_deallocate_node(*(_M_start._M_node - 1)); throw; } } /// Cal |