|
_elements_at_back(__n); iterator __old_finish = _M_finish; const difference_type __elems_after = difference_type(__length) - __elems_before; __pos = _M_finish - __elems_after; try { if (__elems_after > 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); fill(__pos, __pos + difference_type(__n), __x_copy); } else { __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n), __x_copy, __pos, _M_finish); _M_finish = __new_finish; fill(__pos, __old_finish, __x_copy); } } catch(...) { _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); throw; } } } ///实现和上面的重载函数大同小异 template
template
void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, _ForwardIterator __first, _ForwardIterator __last, size_type __n) { const difference_type __elemsbefore = __pos - _M_start; size_type __length = size(); if (__elemsbefore < __length / 2) { iterator __new_start = _M_reserve_elements_at_front(__n); iterator __old_start = _M_start; __pos = _M_start + __elemsbefore; 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); } } catch(...) { _M_destroy_nodes(__new_start._M_node, _M_start._M_node); } } 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; 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); } } catch(...) { _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); throw; } } } template
void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems) { ///根据需要扩充的元素扩充相应数量的中控器单元 size_type __new_nodes = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); _M_reserve_map_at_front(__new_nodes); ///真正进行每个区段的分配 size_type __i; try { for (__i = 1; __i <= __new_nodes; ++__i) *(_M_start._M_node - __i) = _M_allocate_node(); } catch(...) { for (size_type __j = 1; __j < __i; ++__j) _M_deallocate_node(*(_M_start._M_node - __j)); throw; } } ///和_M_new_elements_at_front原理相同 template
void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems) { size_type __new_nodes = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); _M_reserve_map_at_back(__new_nodes); size_type __i; try { for (__i = 1; __i <= __new_nodes; ++__i) *(_M_finish._M_node + __i) = _M_allocate_node(); } catch(...) { for (size_type __j = 1; __j < __i; ++__j) _M_deallocate_node(*(_M_finish._M_node + __j)); throw; } } ///重新分配中控器 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) { ///中控器现有容量比需要容量的2赔还多,只需要将中控器中的元素 ///向一端挪动以腾出足够容量即可 __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); } /// Nonmember functions. template
inline bool operator==(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y) { return __x.size() == __y.size() && equ |