|
led only if _M_finish._M_cur == _M_finish._M_first. template
void deque<_Tp,_Alloc>::_M_pop_back_aux() { ///归还不用区段 _M_deallocate_node(_M_finish._M_first); ///调整状态 _M_finish._M_set_node(_M_finish._M_node - 1); _M_finish._M_cur = _M_finish._M_last - 1; ///析构被删除对象 destroy(_M_finish._M_cur); } /// Called only if _M_start._M_cur == _M_start._M_last - 1. Note that /// if the deque has at least one element (a precondition for this member /// function), and if _M_start._M_cur == _M_start._M_last, then the deque /// must have at least two nodes. template
void deque<_Tp,_Alloc>::_M_pop_front_aux() { destroy(_M_start._M_cur); _M_deallocate_node(_M_start._M_first); _M_start._M_set_node(_M_start._M_node + 1); _M_start._M_cur = _M_start._M_first; } template
template
void deque<_Tp,_Alloc>::insert(iterator __pos, _InputIterator __first, _InputIterator __last, input_iterator_tag) { copy(__first, __last, inserter(*this, __pos)); } 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) { iterator __new_start = _M_reserve_elements_at_front(__n); try { uninitialized_copy(__first, __last, __new_start); _M_start = __new_start; } catch(...) { _M_destroy_nodes(__new_start._M_node, _M_start._M_node); throw; } } else if (__pos._M_cur == _M_finish._M_cur) { iterator __new_finish = _M_reserve_elements_at_back(__n); try { uninitialized_copy(__first, __last, _M_finish); _M_finish = __new_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>::_M_insert_aux(iterator __pos, const value_type& __x) { difference_type __index = __pos - _M_start; value_type __x_copy = __x; if (size_type(__index) < this->size() / 2) { push_front(front()); iterator __front1 = _M_start; ++__front1; iterator __front2 = __front1; ++__front2; __pos = _M_start + __index; iterator __pos1 = __pos; ++__pos1; copy(__front2, __pos1, __front1); } else { push_back(back()); iterator __back1 = _M_finish; --__back1; iterator __back2 = __back1; --__back2; __pos = _M_start + __index; copy_backward(__pos, __back2, __back1); } *__pos = __x_copy; return __pos; } template
typename deque<_Tp,_Alloc>::iterator deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos) { difference_type __index = __pos - _M_start; if (__index < size() / 2) { push_front(front()); iterator __front1 = _M_start; ++__front1; iterator __front2 = __front1; ++__front2; __pos = _M_start + __index; iterator __pos1 = __pos; ++__pos1; copy(__front2, __pos1, __front1); } else { push_back(back()); iterator __back1 = _M_finish; --__back1; iterator __back2 = __back1; --__back2; __pos = _M_start + __index; copy_backward(__pos, __back2, __back1); } *__pos = value_type(); return __pos; } template
void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, size_type __n, const value_type& __x) { const difference_type __elems_before = __pos - _M_start; size_type __length = this->size(); value_type __x_copy = __x; if (__elems_before < difference_type(__length / 2)) ///插入位置的前面元素少 { ///在_M_start之前扩容n个元素,将插入位置之前的元素前移 iterator __new_start = _M_reserve_elements_at_front(__n); iterator __old_start = _M_start; __pos = _M_start + __elems_before; try { if (__elems_before >= 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); ///新元素的插入只需一次进行,都是向已有对象赋值 fill(__pos - difference_type(__n), __pos, __x_copy); } else { ///旧有元素移动一次可以完成,而新元素插入需要两次 __uninitialized_copy_fill(_M_start, __pos, __new_start, _M_start, __x_copy); _M_start = __new_start; fill(__old_start, __pos, __x_copy); } } catch(...) { _M_destroy_nodes(__new_start._M_node, _M_start._M_node); throw; } } else { ///在_M_finish之后扩容n个元素,然后将插入位置之后的元素后移 ///其余原理和上一种情况相同 iterator __new_finish = _M_reserve |