1*38fd1498Szrj // Deque implementation (out of line) -*- C++ -*- 2*38fd1498Szrj 3*38fd1498Szrj // Copyright (C) 2001-2018 Free Software Foundation, Inc. 4*38fd1498Szrj // 5*38fd1498Szrj // This file is part of the GNU ISO C++ Library. This library is free 6*38fd1498Szrj // software; you can redistribute it and/or modify it under the 7*38fd1498Szrj // terms of the GNU General Public License as published by the 8*38fd1498Szrj // Free Software Foundation; either version 3, or (at your option) 9*38fd1498Szrj // any later version. 10*38fd1498Szrj 11*38fd1498Szrj // This library is distributed in the hope that it will be useful, 12*38fd1498Szrj // but WITHOUT ANY WARRANTY; without even the implied warranty of 13*38fd1498Szrj // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14*38fd1498Szrj // GNU General Public License for more details. 15*38fd1498Szrj 16*38fd1498Szrj // Under Section 7 of GPL version 3, you are granted additional 17*38fd1498Szrj // permissions described in the GCC Runtime Library Exception, version 18*38fd1498Szrj // 3.1, as published by the Free Software Foundation. 19*38fd1498Szrj 20*38fd1498Szrj // You should have received a copy of the GNU General Public License and 21*38fd1498Szrj // a copy of the GCC Runtime Library Exception along with this program; 22*38fd1498Szrj // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23*38fd1498Szrj // <http://www.gnu.org/licenses/>. 24*38fd1498Szrj 25*38fd1498Szrj /* 26*38fd1498Szrj * 27*38fd1498Szrj * Copyright (c) 1994 28*38fd1498Szrj * Hewlett-Packard Company 29*38fd1498Szrj * 30*38fd1498Szrj * Permission to use, copy, modify, distribute and sell this software 31*38fd1498Szrj * and its documentation for any purpose is hereby granted without fee, 32*38fd1498Szrj * provided that the above copyright notice appear in all copies and 33*38fd1498Szrj * that both that copyright notice and this permission notice appear 34*38fd1498Szrj * in supporting documentation. Hewlett-Packard Company makes no 35*38fd1498Szrj * representations about the suitability of this software for any 36*38fd1498Szrj * purpose. It is provided "as is" without express or implied warranty. 37*38fd1498Szrj * 38*38fd1498Szrj * 39*38fd1498Szrj * Copyright (c) 1997 40*38fd1498Szrj * Silicon Graphics Computer Systems, Inc. 41*38fd1498Szrj * 42*38fd1498Szrj * Permission to use, copy, modify, distribute and sell this software 43*38fd1498Szrj * and its documentation for any purpose is hereby granted without fee, 44*38fd1498Szrj * provided that the above copyright notice appear in all copies and 45*38fd1498Szrj * that both that copyright notice and this permission notice appear 46*38fd1498Szrj * in supporting documentation. Silicon Graphics makes no 47*38fd1498Szrj * representations about the suitability of this software for any 48*38fd1498Szrj * purpose. It is provided "as is" without express or implied warranty. 49*38fd1498Szrj */ 50*38fd1498Szrj 51*38fd1498Szrj /** @file bits/deque.tcc 52*38fd1498Szrj * This is an internal header file, included by other library headers. 53*38fd1498Szrj * Do not attempt to use it directly. @headername{deque} 54*38fd1498Szrj */ 55*38fd1498Szrj 56*38fd1498Szrj #ifndef _DEQUE_TCC 57*38fd1498Szrj #define _DEQUE_TCC 1 58*38fd1498Szrj 59*38fd1498Szrj namespace std _GLIBCXX_VISIBILITY(default) 60*38fd1498Szrj { 61*38fd1498Szrj _GLIBCXX_BEGIN_NAMESPACE_VERSION 62*38fd1498Szrj _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 63*38fd1498Szrj 64*38fd1498Szrj #if __cplusplus >= 201103L 65*38fd1498Szrj template <typename _Tp, typename _Alloc> 66*38fd1498Szrj void 67*38fd1498Szrj deque<_Tp, _Alloc>:: _M_default_initialize()68*38fd1498Szrj _M_default_initialize() 69*38fd1498Szrj { 70*38fd1498Szrj _Map_pointer __cur; 71*38fd1498Szrj __try 72*38fd1498Szrj { 73*38fd1498Szrj for (__cur = this->_M_impl._M_start._M_node; 74*38fd1498Szrj __cur < this->_M_impl._M_finish._M_node; 75*38fd1498Szrj ++__cur) 76*38fd1498Szrj std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(), 77*38fd1498Szrj _M_get_Tp_allocator()); 78*38fd1498Szrj std::__uninitialized_default_a(this->_M_impl._M_finish._M_first, 79*38fd1498Szrj this->_M_impl._M_finish._M_cur, 80*38fd1498Szrj _M_get_Tp_allocator()); 81*38fd1498Szrj } 82*38fd1498Szrj __catch(...) 83*38fd1498Szrj { 84*38fd1498Szrj std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), 85*38fd1498Szrj _M_get_Tp_allocator()); 86*38fd1498Szrj __throw_exception_again; 87*38fd1498Szrj } 88*38fd1498Szrj } 89*38fd1498Szrj #endif 90*38fd1498Szrj 91*38fd1498Szrj template <typename _Tp, typename _Alloc> 92*38fd1498Szrj deque<_Tp, _Alloc>& 93*38fd1498Szrj deque<_Tp, _Alloc>:: operator =(const deque & __x)94*38fd1498Szrj operator=(const deque& __x) 95*38fd1498Szrj { 96*38fd1498Szrj if (&__x != this) 97*38fd1498Szrj { 98*38fd1498Szrj #if __cplusplus >= 201103L 99*38fd1498Szrj if (_Alloc_traits::_S_propagate_on_copy_assign()) 100*38fd1498Szrj { 101*38fd1498Szrj if (!_Alloc_traits::_S_always_equal() 102*38fd1498Szrj && _M_get_Tp_allocator() != __x._M_get_Tp_allocator()) 103*38fd1498Szrj { 104*38fd1498Szrj // Replacement allocator cannot free existing storage, 105*38fd1498Szrj // so deallocate everything and take copy of __x's data. 106*38fd1498Szrj _M_replace_map(__x, __x.get_allocator()); 107*38fd1498Szrj std::__alloc_on_copy(_M_get_Tp_allocator(), 108*38fd1498Szrj __x._M_get_Tp_allocator()); 109*38fd1498Szrj return *this; 110*38fd1498Szrj } 111*38fd1498Szrj std::__alloc_on_copy(_M_get_Tp_allocator(), 112*38fd1498Szrj __x._M_get_Tp_allocator()); 113*38fd1498Szrj } 114*38fd1498Szrj #endif 115*38fd1498Szrj const size_type __len = size(); 116*38fd1498Szrj if (__len >= __x.size()) 117*38fd1498Szrj _M_erase_at_end(std::copy(__x.begin(), __x.end(), 118*38fd1498Szrj this->_M_impl._M_start)); 119*38fd1498Szrj else 120*38fd1498Szrj { 121*38fd1498Szrj const_iterator __mid = __x.begin() + difference_type(__len); 122*38fd1498Szrj std::copy(__x.begin(), __mid, this->_M_impl._M_start); 123*38fd1498Szrj _M_range_insert_aux(this->_M_impl._M_finish, __mid, __x.end(), 124*38fd1498Szrj std::random_access_iterator_tag()); 125*38fd1498Szrj } 126*38fd1498Szrj } 127*38fd1498Szrj return *this; 128*38fd1498Szrj } 129*38fd1498Szrj 130*38fd1498Szrj #if __cplusplus >= 201103L 131*38fd1498Szrj template<typename _Tp, typename _Alloc> 132*38fd1498Szrj template<typename... _Args> 133*38fd1498Szrj #if __cplusplus > 201402L 134*38fd1498Szrj typename deque<_Tp, _Alloc>::reference 135*38fd1498Szrj #else 136*38fd1498Szrj void 137*38fd1498Szrj #endif 138*38fd1498Szrj deque<_Tp, _Alloc>:: emplace_front(_Args &&...__args)139*38fd1498Szrj emplace_front(_Args&&... __args) 140*38fd1498Szrj { 141*38fd1498Szrj if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) 142*38fd1498Szrj { 143*38fd1498Szrj _Alloc_traits::construct(this->_M_impl, 144*38fd1498Szrj this->_M_impl._M_start._M_cur - 1, 145*38fd1498Szrj std::forward<_Args>(__args)...); 146*38fd1498Szrj --this->_M_impl._M_start._M_cur; 147*38fd1498Szrj } 148*38fd1498Szrj else 149*38fd1498Szrj _M_push_front_aux(std::forward<_Args>(__args)...); 150*38fd1498Szrj #if __cplusplus > 201402L 151*38fd1498Szrj return front(); 152*38fd1498Szrj #endif 153*38fd1498Szrj } 154*38fd1498Szrj 155*38fd1498Szrj template<typename _Tp, typename _Alloc> 156*38fd1498Szrj template<typename... _Args> 157*38fd1498Szrj #if __cplusplus > 201402L 158*38fd1498Szrj typename deque<_Tp, _Alloc>::reference 159*38fd1498Szrj #else 160*38fd1498Szrj void 161*38fd1498Szrj #endif 162*38fd1498Szrj deque<_Tp, _Alloc>:: emplace_back(_Args &&...__args)163*38fd1498Szrj emplace_back(_Args&&... __args) 164*38fd1498Szrj { 165*38fd1498Szrj if (this->_M_impl._M_finish._M_cur 166*38fd1498Szrj != this->_M_impl._M_finish._M_last - 1) 167*38fd1498Szrj { 168*38fd1498Szrj _Alloc_traits::construct(this->_M_impl, 169*38fd1498Szrj this->_M_impl._M_finish._M_cur, 170*38fd1498Szrj std::forward<_Args>(__args)...); 171*38fd1498Szrj ++this->_M_impl._M_finish._M_cur; 172*38fd1498Szrj } 173*38fd1498Szrj else 174*38fd1498Szrj _M_push_back_aux(std::forward<_Args>(__args)...); 175*38fd1498Szrj #if __cplusplus > 201402L 176*38fd1498Szrj return back(); 177*38fd1498Szrj #endif 178*38fd1498Szrj } 179*38fd1498Szrj #endif 180*38fd1498Szrj 181*38fd1498Szrj #if __cplusplus >= 201103L 182*38fd1498Szrj template<typename _Tp, typename _Alloc> 183*38fd1498Szrj template<typename... _Args> 184*38fd1498Szrj typename deque<_Tp, _Alloc>::iterator 185*38fd1498Szrj deque<_Tp, _Alloc>:: emplace(const_iterator __position,_Args &&...__args)186*38fd1498Szrj emplace(const_iterator __position, _Args&&... __args) 187*38fd1498Szrj { 188*38fd1498Szrj if (__position._M_cur == this->_M_impl._M_start._M_cur) 189*38fd1498Szrj { 190*38fd1498Szrj emplace_front(std::forward<_Args>(__args)...); 191*38fd1498Szrj return this->_M_impl._M_start; 192*38fd1498Szrj } 193*38fd1498Szrj else if (__position._M_cur == this->_M_impl._M_finish._M_cur) 194*38fd1498Szrj { 195*38fd1498Szrj emplace_back(std::forward<_Args>(__args)...); 196*38fd1498Szrj iterator __tmp = this->_M_impl._M_finish; 197*38fd1498Szrj --__tmp; 198*38fd1498Szrj return __tmp; 199*38fd1498Szrj } 200*38fd1498Szrj else 201*38fd1498Szrj return _M_insert_aux(__position._M_const_cast(), 202*38fd1498Szrj std::forward<_Args>(__args)...); 203*38fd1498Szrj } 204*38fd1498Szrj #endif 205*38fd1498Szrj 206*38fd1498Szrj template <typename _Tp, typename _Alloc> 207*38fd1498Szrj typename deque<_Tp, _Alloc>::iterator 208*38fd1498Szrj deque<_Tp, _Alloc>:: 209*38fd1498Szrj #if __cplusplus >= 201103L insert(const_iterator __position,const value_type & __x)210*38fd1498Szrj insert(const_iterator __position, const value_type& __x) 211*38fd1498Szrj #else 212*38fd1498Szrj insert(iterator __position, const value_type& __x) 213*38fd1498Szrj #endif 214*38fd1498Szrj { 215*38fd1498Szrj if (__position._M_cur == this->_M_impl._M_start._M_cur) 216*38fd1498Szrj { 217*38fd1498Szrj push_front(__x); 218*38fd1498Szrj return this->_M_impl._M_start; 219*38fd1498Szrj } 220*38fd1498Szrj else if (__position._M_cur == this->_M_impl._M_finish._M_cur) 221*38fd1498Szrj { 222*38fd1498Szrj push_back(__x); 223*38fd1498Szrj iterator __tmp = this->_M_impl._M_finish; 224*38fd1498Szrj --__tmp; 225*38fd1498Szrj return __tmp; 226*38fd1498Szrj } 227*38fd1498Szrj else 228*38fd1498Szrj return _M_insert_aux(__position._M_const_cast(), __x); 229*38fd1498Szrj } 230*38fd1498Szrj 231*38fd1498Szrj template <typename _Tp, typename _Alloc> 232*38fd1498Szrj typename deque<_Tp, _Alloc>::iterator 233*38fd1498Szrj deque<_Tp, _Alloc>:: _M_erase(iterator __position)234*38fd1498Szrj _M_erase(iterator __position) 235*38fd1498Szrj { 236*38fd1498Szrj iterator __next = __position; 237*38fd1498Szrj ++__next; 238*38fd1498Szrj const difference_type __index = __position - begin(); 239*38fd1498Szrj if (static_cast<size_type>(__index) < (size() >> 1)) 240*38fd1498Szrj { 241*38fd1498Szrj if (__position != begin()) 242*38fd1498Szrj _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next); 243*38fd1498Szrj pop_front(); 244*38fd1498Szrj } 245*38fd1498Szrj else 246*38fd1498Szrj { 247*38fd1498Szrj if (__next != end()) 248*38fd1498Szrj _GLIBCXX_MOVE3(__next, end(), __position); 249*38fd1498Szrj pop_back(); 250*38fd1498Szrj } 251*38fd1498Szrj return begin() + __index; 252*38fd1498Szrj } 253*38fd1498Szrj 254*38fd1498Szrj template <typename _Tp, typename _Alloc> 255*38fd1498Szrj typename deque<_Tp, _Alloc>::iterator 256*38fd1498Szrj deque<_Tp, _Alloc>:: _M_erase(iterator __first,iterator __last)257*38fd1498Szrj _M_erase(iterator __first, iterator __last) 258*38fd1498Szrj { 259*38fd1498Szrj if (__first == __last) 260*38fd1498Szrj return __first; 261*38fd1498Szrj else if (__first == begin() && __last == end()) 262*38fd1498Szrj { 263*38fd1498Szrj clear(); 264*38fd1498Szrj return end(); 265*38fd1498Szrj } 266*38fd1498Szrj else 267*38fd1498Szrj { 268*38fd1498Szrj const difference_type __n = __last - __first; 269*38fd1498Szrj const difference_type __elems_before = __first - begin(); 270*38fd1498Szrj if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2) 271*38fd1498Szrj { 272*38fd1498Szrj if (__first != begin()) 273*38fd1498Szrj _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last); 274*38fd1498Szrj _M_erase_at_begin(begin() + __n); 275*38fd1498Szrj } 276*38fd1498Szrj else 277*38fd1498Szrj { 278*38fd1498Szrj if (__last != end()) 279*38fd1498Szrj _GLIBCXX_MOVE3(__last, end(), __first); 280*38fd1498Szrj _M_erase_at_end(end() - __n); 281*38fd1498Szrj } 282*38fd1498Szrj return begin() + __elems_before; 283*38fd1498Szrj } 284*38fd1498Szrj } 285*38fd1498Szrj 286*38fd1498Szrj template <typename _Tp, class _Alloc> 287*38fd1498Szrj template <typename _InputIterator> 288*38fd1498Szrj void 289*38fd1498Szrj deque<_Tp, _Alloc>:: _M_assign_aux(_InputIterator __first,_InputIterator __last,std::input_iterator_tag)290*38fd1498Szrj _M_assign_aux(_InputIterator __first, _InputIterator __last, 291*38fd1498Szrj std::input_iterator_tag) 292*38fd1498Szrj { 293*38fd1498Szrj iterator __cur = begin(); 294*38fd1498Szrj for (; __first != __last && __cur != end(); ++__cur, ++__first) 295*38fd1498Szrj *__cur = *__first; 296*38fd1498Szrj if (__first == __last) 297*38fd1498Szrj _M_erase_at_end(__cur); 298*38fd1498Szrj else 299*38fd1498Szrj _M_range_insert_aux(end(), __first, __last, 300*38fd1498Szrj std::__iterator_category(__first)); 301*38fd1498Szrj } 302*38fd1498Szrj 303*38fd1498Szrj template <typename _Tp, typename _Alloc> 304*38fd1498Szrj void 305*38fd1498Szrj deque<_Tp, _Alloc>:: _M_fill_insert(iterator __pos,size_type __n,const value_type & __x)306*38fd1498Szrj _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) 307*38fd1498Szrj { 308*38fd1498Szrj if (__pos._M_cur == this->_M_impl._M_start._M_cur) 309*38fd1498Szrj { 310*38fd1498Szrj iterator __new_start = _M_reserve_elements_at_front(__n); 311*38fd1498Szrj __try 312*38fd1498Szrj { 313*38fd1498Szrj std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start, 314*38fd1498Szrj __x, _M_get_Tp_allocator()); 315*38fd1498Szrj this->_M_impl._M_start = __new_start; 316*38fd1498Szrj } 317*38fd1498Szrj __catch(...) 318*38fd1498Szrj { 319*38fd1498Szrj _M_destroy_nodes(__new_start._M_node, 320*38fd1498Szrj this->_M_impl._M_start._M_node); 321*38fd1498Szrj __throw_exception_again; 322*38fd1498Szrj } 323*38fd1498Szrj } 324*38fd1498Szrj else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 325*38fd1498Szrj { 326*38fd1498Szrj iterator __new_finish = _M_reserve_elements_at_back(__n); 327*38fd1498Szrj __try 328*38fd1498Szrj { 329*38fd1498Szrj std::__uninitialized_fill_a(this->_M_impl._M_finish, 330*38fd1498Szrj __new_finish, __x, 331*38fd1498Szrj _M_get_Tp_allocator()); 332*38fd1498Szrj this->_M_impl._M_finish = __new_finish; 333*38fd1498Szrj } 334*38fd1498Szrj __catch(...) 335*38fd1498Szrj { 336*38fd1498Szrj _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 337*38fd1498Szrj __new_finish._M_node + 1); 338*38fd1498Szrj __throw_exception_again; 339*38fd1498Szrj } 340*38fd1498Szrj } 341*38fd1498Szrj else 342*38fd1498Szrj _M_insert_aux(__pos, __n, __x); 343*38fd1498Szrj } 344*38fd1498Szrj 345*38fd1498Szrj #if __cplusplus >= 201103L 346*38fd1498Szrj template <typename _Tp, typename _Alloc> 347*38fd1498Szrj void 348*38fd1498Szrj deque<_Tp, _Alloc>:: _M_default_append(size_type __n)349*38fd1498Szrj _M_default_append(size_type __n) 350*38fd1498Szrj { 351*38fd1498Szrj if (__n) 352*38fd1498Szrj { 353*38fd1498Szrj iterator __new_finish = _M_reserve_elements_at_back(__n); 354*38fd1498Szrj __try 355*38fd1498Szrj { 356*38fd1498Szrj std::__uninitialized_default_a(this->_M_impl._M_finish, 357*38fd1498Szrj __new_finish, 358*38fd1498Szrj _M_get_Tp_allocator()); 359*38fd1498Szrj this->_M_impl._M_finish = __new_finish; 360*38fd1498Szrj } 361*38fd1498Szrj __catch(...) 362*38fd1498Szrj { 363*38fd1498Szrj _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 364*38fd1498Szrj __new_finish._M_node + 1); 365*38fd1498Szrj __throw_exception_again; 366*38fd1498Szrj } 367*38fd1498Szrj } 368*38fd1498Szrj } 369*38fd1498Szrj 370*38fd1498Szrj template <typename _Tp, typename _Alloc> 371*38fd1498Szrj bool 372*38fd1498Szrj deque<_Tp, _Alloc>:: _M_shrink_to_fit()373*38fd1498Szrj _M_shrink_to_fit() 374*38fd1498Szrj { 375*38fd1498Szrj const difference_type __front_capacity 376*38fd1498Szrj = (this->_M_impl._M_start._M_cur - this->_M_impl._M_start._M_first); 377*38fd1498Szrj if (__front_capacity == 0) 378*38fd1498Szrj return false; 379*38fd1498Szrj 380*38fd1498Szrj const difference_type __back_capacity 381*38fd1498Szrj = (this->_M_impl._M_finish._M_last - this->_M_impl._M_finish._M_cur); 382*38fd1498Szrj if (__front_capacity + __back_capacity < _S_buffer_size()) 383*38fd1498Szrj return false; 384*38fd1498Szrj 385*38fd1498Szrj return std::__shrink_to_fit_aux<deque>::_S_do_it(*this); 386*38fd1498Szrj } 387*38fd1498Szrj #endif 388*38fd1498Szrj 389*38fd1498Szrj template <typename _Tp, typename _Alloc> 390*38fd1498Szrj void 391*38fd1498Szrj deque<_Tp, _Alloc>:: _M_fill_initialize(const value_type & __value)392*38fd1498Szrj _M_fill_initialize(const value_type& __value) 393*38fd1498Szrj { 394*38fd1498Szrj _Map_pointer __cur; 395*38fd1498Szrj __try 396*38fd1498Szrj { 397*38fd1498Szrj for (__cur = this->_M_impl._M_start._M_node; 398*38fd1498Szrj __cur < this->_M_impl._M_finish._M_node; 399*38fd1498Szrj ++__cur) 400*38fd1498Szrj std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(), 401*38fd1498Szrj __value, _M_get_Tp_allocator()); 402*38fd1498Szrj std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first, 403*38fd1498Szrj this->_M_impl._M_finish._M_cur, 404*38fd1498Szrj __value, _M_get_Tp_allocator()); 405*38fd1498Szrj } 406*38fd1498Szrj __catch(...) 407*38fd1498Szrj { 408*38fd1498Szrj std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), 409*38fd1498Szrj _M_get_Tp_allocator()); 410*38fd1498Szrj __throw_exception_again; 411*38fd1498Szrj } 412*38fd1498Szrj } 413*38fd1498Szrj 414*38fd1498Szrj template <typename _Tp, typename _Alloc> 415*38fd1498Szrj template <typename _InputIterator> 416*38fd1498Szrj void 417*38fd1498Szrj deque<_Tp, _Alloc>:: _M_range_initialize(_InputIterator __first,_InputIterator __last,std::input_iterator_tag)418*38fd1498Szrj _M_range_initialize(_InputIterator __first, _InputIterator __last, 419*38fd1498Szrj std::input_iterator_tag) 420*38fd1498Szrj { 421*38fd1498Szrj this->_M_initialize_map(0); 422*38fd1498Szrj __try 423*38fd1498Szrj { 424*38fd1498Szrj for (; __first != __last; ++__first) 425*38fd1498Szrj #if __cplusplus >= 201103L 426*38fd1498Szrj emplace_back(*__first); 427*38fd1498Szrj #else 428*38fd1498Szrj push_back(*__first); 429*38fd1498Szrj #endif 430*38fd1498Szrj } 431*38fd1498Szrj __catch(...) 432*38fd1498Szrj { 433*38fd1498Szrj clear(); 434*38fd1498Szrj __throw_exception_again; 435*38fd1498Szrj } 436*38fd1498Szrj } 437*38fd1498Szrj 438*38fd1498Szrj template <typename _Tp, typename _Alloc> 439*38fd1498Szrj template <typename _ForwardIterator> 440*38fd1498Szrj void 441*38fd1498Szrj deque<_Tp, _Alloc>:: _M_range_initialize(_ForwardIterator __first,_ForwardIterator __last,std::forward_iterator_tag)442*38fd1498Szrj _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 443*38fd1498Szrj std::forward_iterator_tag) 444*38fd1498Szrj { 445*38fd1498Szrj const size_type __n = std::distance(__first, __last); 446*38fd1498Szrj this->_M_initialize_map(__n); 447*38fd1498Szrj 448*38fd1498Szrj _Map_pointer __cur_node; 449*38fd1498Szrj __try 450*38fd1498Szrj { 451*38fd1498Szrj for (__cur_node = this->_M_impl._M_start._M_node; 452*38fd1498Szrj __cur_node < this->_M_impl._M_finish._M_node; 453*38fd1498Szrj ++__cur_node) 454*38fd1498Szrj { 455*38fd1498Szrj _ForwardIterator __mid = __first; 456*38fd1498Szrj std::advance(__mid, _S_buffer_size()); 457*38fd1498Szrj std::__uninitialized_copy_a(__first, __mid, *__cur_node, 458*38fd1498Szrj _M_get_Tp_allocator()); 459*38fd1498Szrj __first = __mid; 460*38fd1498Szrj } 461*38fd1498Szrj std::__uninitialized_copy_a(__first, __last, 462*38fd1498Szrj this->_M_impl._M_finish._M_first, 463*38fd1498Szrj _M_get_Tp_allocator()); 464*38fd1498Szrj } 465*38fd1498Szrj __catch(...) 466*38fd1498Szrj { 467*38fd1498Szrj std::_Destroy(this->_M_impl._M_start, 468*38fd1498Szrj iterator(*__cur_node, __cur_node), 469*38fd1498Szrj _M_get_Tp_allocator()); 470*38fd1498Szrj __throw_exception_again; 471*38fd1498Szrj } 472*38fd1498Szrj } 473*38fd1498Szrj 474*38fd1498Szrj // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. 475*38fd1498Szrj template<typename _Tp, typename _Alloc> 476*38fd1498Szrj #if __cplusplus >= 201103L 477*38fd1498Szrj template<typename... _Args> 478*38fd1498Szrj void 479*38fd1498Szrj deque<_Tp, _Alloc>:: _M_push_back_aux(_Args &&...__args)480*38fd1498Szrj _M_push_back_aux(_Args&&... __args) 481*38fd1498Szrj #else 482*38fd1498Szrj void 483*38fd1498Szrj deque<_Tp, _Alloc>:: 484*38fd1498Szrj _M_push_back_aux(const value_type& __t) 485*38fd1498Szrj #endif 486*38fd1498Szrj { 487*38fd1498Szrj _M_reserve_map_at_back(); 488*38fd1498Szrj *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); 489*38fd1498Szrj __try 490*38fd1498Szrj { 491*38fd1498Szrj #if __cplusplus >= 201103L 492*38fd1498Szrj _Alloc_traits::construct(this->_M_impl, 493*38fd1498Szrj this->_M_impl._M_finish._M_cur, 494*38fd1498Szrj std::forward<_Args>(__args)...); 495*38fd1498Szrj #else 496*38fd1498Szrj this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t); 497*38fd1498Szrj #endif 498*38fd1498Szrj this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node 499*38fd1498Szrj + 1); 500*38fd1498Szrj this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; 501*38fd1498Szrj } 502*38fd1498Szrj __catch(...) 503*38fd1498Szrj { 504*38fd1498Szrj _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); 505*38fd1498Szrj __throw_exception_again; 506*38fd1498Szrj } 507*38fd1498Szrj } 508*38fd1498Szrj 509*38fd1498Szrj // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. 510*38fd1498Szrj template<typename _Tp, typename _Alloc> 511*38fd1498Szrj #if __cplusplus >= 201103L 512*38fd1498Szrj template<typename... _Args> 513*38fd1498Szrj void 514*38fd1498Szrj deque<_Tp, _Alloc>:: _M_push_front_aux(_Args &&...__args)515*38fd1498Szrj _M_push_front_aux(_Args&&... __args) 516*38fd1498Szrj #else 517*38fd1498Szrj void 518*38fd1498Szrj deque<_Tp, _Alloc>:: 519*38fd1498Szrj _M_push_front_aux(const value_type& __t) 520*38fd1498Szrj #endif 521*38fd1498Szrj { 522*38fd1498Szrj _M_reserve_map_at_front(); 523*38fd1498Szrj *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); 524*38fd1498Szrj __try 525*38fd1498Szrj { 526*38fd1498Szrj this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node 527*38fd1498Szrj - 1); 528*38fd1498Szrj this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; 529*38fd1498Szrj #if __cplusplus >= 201103L 530*38fd1498Szrj _Alloc_traits::construct(this->_M_impl, 531*38fd1498Szrj this->_M_impl._M_start._M_cur, 532*38fd1498Szrj std::forward<_Args>(__args)...); 533*38fd1498Szrj #else 534*38fd1498Szrj this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t); 535*38fd1498Szrj #endif 536*38fd1498Szrj } 537*38fd1498Szrj __catch(...) 538*38fd1498Szrj { 539*38fd1498Szrj ++this->_M_impl._M_start; 540*38fd1498Szrj _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); 541*38fd1498Szrj __throw_exception_again; 542*38fd1498Szrj } 543*38fd1498Szrj } 544*38fd1498Szrj 545*38fd1498Szrj // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. 546*38fd1498Szrj template <typename _Tp, typename _Alloc> 547*38fd1498Szrj void deque<_Tp, _Alloc>:: _M_pop_back_aux()548*38fd1498Szrj _M_pop_back_aux() 549*38fd1498Szrj { 550*38fd1498Szrj _M_deallocate_node(this->_M_impl._M_finish._M_first); 551*38fd1498Szrj this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); 552*38fd1498Szrj this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; 553*38fd1498Szrj _Alloc_traits::destroy(_M_get_Tp_allocator(), 554*38fd1498Szrj this->_M_impl._M_finish._M_cur); 555*38fd1498Szrj } 556*38fd1498Szrj 557*38fd1498Szrj // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. 558*38fd1498Szrj // Note that if the deque has at least one element (a precondition for this 559*38fd1498Szrj // member function), and if 560*38fd1498Szrj // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, 561*38fd1498Szrj // then the deque must have at least two nodes. 562*38fd1498Szrj template <typename _Tp, typename _Alloc> 563*38fd1498Szrj void deque<_Tp, _Alloc>:: _M_pop_front_aux()564*38fd1498Szrj _M_pop_front_aux() 565*38fd1498Szrj { 566*38fd1498Szrj _Alloc_traits::destroy(_M_get_Tp_allocator(), 567*38fd1498Szrj this->_M_impl._M_start._M_cur); 568*38fd1498Szrj _M_deallocate_node(this->_M_impl._M_start._M_first); 569*38fd1498Szrj this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); 570*38fd1498Szrj this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; 571*38fd1498Szrj } 572*38fd1498Szrj 573*38fd1498Szrj template <typename _Tp, typename _Alloc> 574*38fd1498Szrj template <typename _InputIterator> 575*38fd1498Szrj void 576*38fd1498Szrj deque<_Tp, _Alloc>:: _M_range_insert_aux(iterator __pos,_InputIterator __first,_InputIterator __last,std::input_iterator_tag)577*38fd1498Szrj _M_range_insert_aux(iterator __pos, 578*38fd1498Szrj _InputIterator __first, _InputIterator __last, 579*38fd1498Szrj std::input_iterator_tag) 580*38fd1498Szrj { std::copy(__first, __last, std::inserter(*this, __pos)); } 581*38fd1498Szrj 582*38fd1498Szrj template <typename _Tp, typename _Alloc> 583*38fd1498Szrj template <typename _ForwardIterator> 584*38fd1498Szrj void 585*38fd1498Szrj deque<_Tp, _Alloc>:: _M_range_insert_aux(iterator __pos,_ForwardIterator __first,_ForwardIterator __last,std::forward_iterator_tag)586*38fd1498Szrj _M_range_insert_aux(iterator __pos, 587*38fd1498Szrj _ForwardIterator __first, _ForwardIterator __last, 588*38fd1498Szrj std::forward_iterator_tag) 589*38fd1498Szrj { 590*38fd1498Szrj const size_type __n = std::distance(__first, __last); 591*38fd1498Szrj if (__pos._M_cur == this->_M_impl._M_start._M_cur) 592*38fd1498Szrj { 593*38fd1498Szrj iterator __new_start = _M_reserve_elements_at_front(__n); 594*38fd1498Szrj __try 595*38fd1498Szrj { 596*38fd1498Szrj std::__uninitialized_copy_a(__first, __last, __new_start, 597*38fd1498Szrj _M_get_Tp_allocator()); 598*38fd1498Szrj this->_M_impl._M_start = __new_start; 599*38fd1498Szrj } 600*38fd1498Szrj __catch(...) 601*38fd1498Szrj { 602*38fd1498Szrj _M_destroy_nodes(__new_start._M_node, 603*38fd1498Szrj this->_M_impl._M_start._M_node); 604*38fd1498Szrj __throw_exception_again; 605*38fd1498Szrj } 606*38fd1498Szrj } 607*38fd1498Szrj else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 608*38fd1498Szrj { 609*38fd1498Szrj iterator __new_finish = _M_reserve_elements_at_back(__n); 610*38fd1498Szrj __try 611*38fd1498Szrj { 612*38fd1498Szrj std::__uninitialized_copy_a(__first, __last, 613*38fd1498Szrj this->_M_impl._M_finish, 614*38fd1498Szrj _M_get_Tp_allocator()); 615*38fd1498Szrj this->_M_impl._M_finish = __new_finish; 616*38fd1498Szrj } 617*38fd1498Szrj __catch(...) 618*38fd1498Szrj { 619*38fd1498Szrj _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 620*38fd1498Szrj __new_finish._M_node + 1); 621*38fd1498Szrj __throw_exception_again; 622*38fd1498Szrj } 623*38fd1498Szrj } 624*38fd1498Szrj else 625*38fd1498Szrj _M_insert_aux(__pos, __first, __last, __n); 626*38fd1498Szrj } 627*38fd1498Szrj 628*38fd1498Szrj template<typename _Tp, typename _Alloc> 629*38fd1498Szrj #if __cplusplus >= 201103L 630*38fd1498Szrj template<typename... _Args> 631*38fd1498Szrj typename deque<_Tp, _Alloc>::iterator 632*38fd1498Szrj deque<_Tp, _Alloc>:: _M_insert_aux(iterator __pos,_Args &&...__args)633*38fd1498Szrj _M_insert_aux(iterator __pos, _Args&&... __args) 634*38fd1498Szrj { 635*38fd1498Szrj value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy 636*38fd1498Szrj #else 637*38fd1498Szrj typename deque<_Tp, _Alloc>::iterator 638*38fd1498Szrj deque<_Tp, _Alloc>:: 639*38fd1498Szrj _M_insert_aux(iterator __pos, const value_type& __x) 640*38fd1498Szrj { 641*38fd1498Szrj value_type __x_copy = __x; // XXX copy 642*38fd1498Szrj #endif 643*38fd1498Szrj difference_type __index = __pos - this->_M_impl._M_start; 644*38fd1498Szrj if (static_cast<size_type>(__index) < size() / 2) 645*38fd1498Szrj { 646*38fd1498Szrj push_front(_GLIBCXX_MOVE(front())); 647*38fd1498Szrj iterator __front1 = this->_M_impl._M_start; 648*38fd1498Szrj ++__front1; 649*38fd1498Szrj iterator __front2 = __front1; 650*38fd1498Szrj ++__front2; 651*38fd1498Szrj __pos = this->_M_impl._M_start + __index; 652*38fd1498Szrj iterator __pos1 = __pos; 653*38fd1498Szrj ++__pos1; 654*38fd1498Szrj _GLIBCXX_MOVE3(__front2, __pos1, __front1); 655*38fd1498Szrj } 656*38fd1498Szrj else 657*38fd1498Szrj { 658*38fd1498Szrj push_back(_GLIBCXX_MOVE(back())); 659*38fd1498Szrj iterator __back1 = this->_M_impl._M_finish; 660*38fd1498Szrj --__back1; 661*38fd1498Szrj iterator __back2 = __back1; 662*38fd1498Szrj --__back2; 663*38fd1498Szrj __pos = this->_M_impl._M_start + __index; 664*38fd1498Szrj _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1); 665*38fd1498Szrj } 666*38fd1498Szrj *__pos = _GLIBCXX_MOVE(__x_copy); 667*38fd1498Szrj return __pos; 668*38fd1498Szrj } 669*38fd1498Szrj 670*38fd1498Szrj template <typename _Tp, typename _Alloc> 671*38fd1498Szrj void 672*38fd1498Szrj deque<_Tp, _Alloc>:: 673*38fd1498Szrj _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) 674*38fd1498Szrj { 675*38fd1498Szrj const difference_type __elems_before = __pos - this->_M_impl._M_start; 676*38fd1498Szrj const size_type __length = this->size(); 677*38fd1498Szrj value_type __x_copy = __x; 678*38fd1498Szrj if (__elems_before < difference_type(__length / 2)) 679*38fd1498Szrj { 680*38fd1498Szrj iterator __new_start = _M_reserve_elements_at_front(__n); 681*38fd1498Szrj iterator __old_start = this->_M_impl._M_start; 682*38fd1498Szrj __pos = this->_M_impl._M_start + __elems_before; 683*38fd1498Szrj __try 684*38fd1498Szrj { 685*38fd1498Szrj if (__elems_before >= difference_type(__n)) 686*38fd1498Szrj { 687*38fd1498Szrj iterator __start_n = (this->_M_impl._M_start 688*38fd1498Szrj + difference_type(__n)); 689*38fd1498Szrj std::__uninitialized_move_a(this->_M_impl._M_start, 690*38fd1498Szrj __start_n, __new_start, 691*38fd1498Szrj _M_get_Tp_allocator()); 692*38fd1498Szrj this->_M_impl._M_start = __new_start; 693*38fd1498Szrj _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 694*38fd1498Szrj std::fill(__pos - difference_type(__n), __pos, __x_copy); 695*38fd1498Szrj } 696*38fd1498Szrj else 697*38fd1498Szrj { 698*38fd1498Szrj std::__uninitialized_move_fill(this->_M_impl._M_start, 699*38fd1498Szrj __pos, __new_start, 700*38fd1498Szrj this->_M_impl._M_start, 701*38fd1498Szrj __x_copy, 702*38fd1498Szrj _M_get_Tp_allocator()); 703*38fd1498Szrj this->_M_impl._M_start = __new_start; 704*38fd1498Szrj std::fill(__old_start, __pos, __x_copy); 705*38fd1498Szrj } 706*38fd1498Szrj } 707*38fd1498Szrj __catch(...) 708*38fd1498Szrj { 709*38fd1498Szrj _M_destroy_nodes(__new_start._M_node, 710*38fd1498Szrj this->_M_impl._M_start._M_node); 711*38fd1498Szrj __throw_exception_again; 712*38fd1498Szrj } 713*38fd1498Szrj } 714*38fd1498Szrj else 715*38fd1498Szrj { 716*38fd1498Szrj iterator __new_finish = _M_reserve_elements_at_back(__n); 717*38fd1498Szrj iterator __old_finish = this->_M_impl._M_finish; 718*38fd1498Szrj const difference_type __elems_after = 719*38fd1498Szrj difference_type(__length) - __elems_before; 720*38fd1498Szrj __pos = this->_M_impl._M_finish - __elems_after; 721*38fd1498Szrj __try 722*38fd1498Szrj { 723*38fd1498Szrj if (__elems_after > difference_type(__n)) 724*38fd1498Szrj { 725*38fd1498Szrj iterator __finish_n = (this->_M_impl._M_finish 726*38fd1498Szrj - difference_type(__n)); 727*38fd1498Szrj std::__uninitialized_move_a(__finish_n, 728*38fd1498Szrj this->_M_impl._M_finish, 729*38fd1498Szrj this->_M_impl._M_finish, 730*38fd1498Szrj _M_get_Tp_allocator()); 731*38fd1498Szrj this->_M_impl._M_finish = __new_finish; 732*38fd1498Szrj _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 733*38fd1498Szrj std::fill(__pos, __pos + difference_type(__n), __x_copy); 734*38fd1498Szrj } 735*38fd1498Szrj else 736*38fd1498Szrj { 737*38fd1498Szrj std::__uninitialized_fill_move(this->_M_impl._M_finish, 738*38fd1498Szrj __pos + difference_type(__n), 739*38fd1498Szrj __x_copy, __pos, 740*38fd1498Szrj this->_M_impl._M_finish, 741*38fd1498Szrj _M_get_Tp_allocator()); 742*38fd1498Szrj this->_M_impl._M_finish = __new_finish; 743*38fd1498Szrj std::fill(__pos, __old_finish, __x_copy); 744*38fd1498Szrj } 745*38fd1498Szrj } 746*38fd1498Szrj __catch(...) 747*38fd1498Szrj { 748*38fd1498Szrj _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 749*38fd1498Szrj __new_finish._M_node + 1); 750*38fd1498Szrj __throw_exception_again; 751*38fd1498Szrj } 752*38fd1498Szrj } 753*38fd1498Szrj } 754*38fd1498Szrj 755*38fd1498Szrj template <typename _Tp, typename _Alloc> 756*38fd1498Szrj template <typename _ForwardIterator> 757*38fd1498Szrj void 758*38fd1498Szrj deque<_Tp, _Alloc>:: 759*38fd1498Szrj _M_insert_aux(iterator __pos, 760*38fd1498Szrj _ForwardIterator __first, _ForwardIterator __last, 761*38fd1498Szrj size_type __n) 762*38fd1498Szrj { 763*38fd1498Szrj const difference_type __elemsbefore = __pos - this->_M_impl._M_start; 764*38fd1498Szrj const size_type __length = size(); 765*38fd1498Szrj if (static_cast<size_type>(__elemsbefore) < __length / 2) 766*38fd1498Szrj { 767*38fd1498Szrj iterator __new_start = _M_reserve_elements_at_front(__n); 768*38fd1498Szrj iterator __old_start = this->_M_impl._M_start; 769*38fd1498Szrj __pos = this->_M_impl._M_start + __elemsbefore; 770*38fd1498Szrj __try 771*38fd1498Szrj { 772*38fd1498Szrj if (__elemsbefore >= difference_type(__n)) 773*38fd1498Szrj { 774*38fd1498Szrj iterator __start_n = (this->_M_impl._M_start 775*38fd1498Szrj + difference_type(__n)); 776*38fd1498Szrj std::__uninitialized_move_a(this->_M_impl._M_start, 777*38fd1498Szrj __start_n, __new_start, 778*38fd1498Szrj _M_get_Tp_allocator()); 779*38fd1498Szrj this->_M_impl._M_start = __new_start; 780*38fd1498Szrj _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 781*38fd1498Szrj std::copy(__first, __last, __pos - difference_type(__n)); 782*38fd1498Szrj } 783*38fd1498Szrj else 784*38fd1498Szrj { 785*38fd1498Szrj _ForwardIterator __mid = __first; 786*38fd1498Szrj std::advance(__mid, difference_type(__n) - __elemsbefore); 787*38fd1498Szrj std::__uninitialized_move_copy(this->_M_impl._M_start, 788*38fd1498Szrj __pos, __first, __mid, 789*38fd1498Szrj __new_start, 790*38fd1498Szrj _M_get_Tp_allocator()); 791*38fd1498Szrj this->_M_impl._M_start = __new_start; 792*38fd1498Szrj std::copy(__mid, __last, __old_start); 793*38fd1498Szrj } 794*38fd1498Szrj } 795*38fd1498Szrj __catch(...) 796*38fd1498Szrj { 797*38fd1498Szrj _M_destroy_nodes(__new_start._M_node, 798*38fd1498Szrj this->_M_impl._M_start._M_node); 799*38fd1498Szrj __throw_exception_again; 800*38fd1498Szrj } 801*38fd1498Szrj } 802*38fd1498Szrj else 803*38fd1498Szrj { 804*38fd1498Szrj iterator __new_finish = _M_reserve_elements_at_back(__n); 805*38fd1498Szrj iterator __old_finish = this->_M_impl._M_finish; 806*38fd1498Szrj const difference_type __elemsafter = 807*38fd1498Szrj difference_type(__length) - __elemsbefore; 808*38fd1498Szrj __pos = this->_M_impl._M_finish - __elemsafter; 809*38fd1498Szrj __try 810*38fd1498Szrj { 811*38fd1498Szrj if (__elemsafter > difference_type(__n)) 812*38fd1498Szrj { 813*38fd1498Szrj iterator __finish_n = (this->_M_impl._M_finish 814*38fd1498Szrj - difference_type(__n)); 815*38fd1498Szrj std::__uninitialized_move_a(__finish_n, 816*38fd1498Szrj this->_M_impl._M_finish, 817*38fd1498Szrj this->_M_impl._M_finish, 818*38fd1498Szrj _M_get_Tp_allocator()); 819*38fd1498Szrj this->_M_impl._M_finish = __new_finish; 820*38fd1498Szrj _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 821*38fd1498Szrj std::copy(__first, __last, __pos); 822*38fd1498Szrj } 823*38fd1498Szrj else 824*38fd1498Szrj { 825*38fd1498Szrj _ForwardIterator __mid = __first; 826*38fd1498Szrj std::advance(__mid, __elemsafter); 827*38fd1498Szrj std::__uninitialized_copy_move(__mid, __last, __pos, 828*38fd1498Szrj this->_M_impl._M_finish, 829*38fd1498Szrj this->_M_impl._M_finish, 830*38fd1498Szrj _M_get_Tp_allocator()); 831*38fd1498Szrj this->_M_impl._M_finish = __new_finish; 832*38fd1498Szrj std::copy(__first, __mid, __pos); 833*38fd1498Szrj } 834*38fd1498Szrj } 835*38fd1498Szrj __catch(...) 836*38fd1498Szrj { 837*38fd1498Szrj _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 838*38fd1498Szrj __new_finish._M_node + 1); 839*38fd1498Szrj __throw_exception_again; 840*38fd1498Szrj } 841*38fd1498Szrj } 842*38fd1498Szrj } 843*38fd1498Szrj 844*38fd1498Szrj template<typename _Tp, typename _Alloc> 845*38fd1498Szrj void 846*38fd1498Szrj deque<_Tp, _Alloc>:: 847*38fd1498Szrj _M_destroy_data_aux(iterator __first, iterator __last) 848*38fd1498Szrj { 849*38fd1498Szrj for (_Map_pointer __node = __first._M_node + 1; 850*38fd1498Szrj __node < __last._M_node; ++__node) 851*38fd1498Szrj std::_Destroy(*__node, *__node + _S_buffer_size(), 852*38fd1498Szrj _M_get_Tp_allocator()); 853*38fd1498Szrj 854*38fd1498Szrj if (__first._M_node != __last._M_node) 855*38fd1498Szrj { 856*38fd1498Szrj std::_Destroy(__first._M_cur, __first._M_last, 857*38fd1498Szrj _M_get_Tp_allocator()); 858*38fd1498Szrj std::_Destroy(__last._M_first, __last._M_cur, 859*38fd1498Szrj _M_get_Tp_allocator()); 860*38fd1498Szrj } 861*38fd1498Szrj else 862*38fd1498Szrj std::_Destroy(__first._M_cur, __last._M_cur, 863*38fd1498Szrj _M_get_Tp_allocator()); 864*38fd1498Szrj } 865*38fd1498Szrj 866*38fd1498Szrj template <typename _Tp, typename _Alloc> 867*38fd1498Szrj void 868*38fd1498Szrj deque<_Tp, _Alloc>:: 869*38fd1498Szrj _M_new_elements_at_front(size_type __new_elems) 870*38fd1498Szrj { 871*38fd1498Szrj if (this->max_size() - this->size() < __new_elems) 872*38fd1498Szrj __throw_length_error(__N("deque::_M_new_elements_at_front")); 873*38fd1498Szrj 874*38fd1498Szrj const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 875*38fd1498Szrj / _S_buffer_size()); 876*38fd1498Szrj _M_reserve_map_at_front(__new_nodes); 877*38fd1498Szrj size_type __i; 878*38fd1498Szrj __try 879*38fd1498Szrj { 880*38fd1498Szrj for (__i = 1; __i <= __new_nodes; ++__i) 881*38fd1498Szrj *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); 882*38fd1498Szrj } 883*38fd1498Szrj __catch(...) 884*38fd1498Szrj { 885*38fd1498Szrj for (size_type __j = 1; __j < __i; ++__j) 886*38fd1498Szrj _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); 887*38fd1498Szrj __throw_exception_again; 888*38fd1498Szrj } 889*38fd1498Szrj } 890*38fd1498Szrj 891*38fd1498Szrj template <typename _Tp, typename _Alloc> 892*38fd1498Szrj void 893*38fd1498Szrj deque<_Tp, _Alloc>:: 894*38fd1498Szrj _M_new_elements_at_back(size_type __new_elems) 895*38fd1498Szrj { 896*38fd1498Szrj if (this->max_size() - this->size() < __new_elems) 897*38fd1498Szrj __throw_length_error(__N("deque::_M_new_elements_at_back")); 898*38fd1498Szrj 899*38fd1498Szrj const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 900*38fd1498Szrj / _S_buffer_size()); 901*38fd1498Szrj _M_reserve_map_at_back(__new_nodes); 902*38fd1498Szrj size_type __i; 903*38fd1498Szrj __try 904*38fd1498Szrj { 905*38fd1498Szrj for (__i = 1; __i <= __new_nodes; ++__i) 906*38fd1498Szrj *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); 907*38fd1498Szrj } 908*38fd1498Szrj __catch(...) 909*38fd1498Szrj { 910*38fd1498Szrj for (size_type __j = 1; __j < __i; ++__j) 911*38fd1498Szrj _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); 912*38fd1498Szrj __throw_exception_again; 913*38fd1498Szrj } 914*38fd1498Szrj } 915*38fd1498Szrj 916*38fd1498Szrj template <typename _Tp, typename _Alloc> 917*38fd1498Szrj void 918*38fd1498Szrj deque<_Tp, _Alloc>:: 919*38fd1498Szrj _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) 920*38fd1498Szrj { 921*38fd1498Szrj const size_type __old_num_nodes 922*38fd1498Szrj = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; 923*38fd1498Szrj const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 924*38fd1498Szrj 925*38fd1498Szrj _Map_pointer __new_nstart; 926*38fd1498Szrj if (this->_M_impl._M_map_size > 2 * __new_num_nodes) 927*38fd1498Szrj { 928*38fd1498Szrj __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size 929*38fd1498Szrj - __new_num_nodes) / 2 930*38fd1498Szrj + (__add_at_front ? __nodes_to_add : 0); 931*38fd1498Szrj if (__new_nstart < this->_M_impl._M_start._M_node) 932*38fd1498Szrj std::copy(this->_M_impl._M_start._M_node, 933*38fd1498Szrj this->_M_impl._M_finish._M_node + 1, 934*38fd1498Szrj __new_nstart); 935*38fd1498Szrj else 936*38fd1498Szrj std::copy_backward(this->_M_impl._M_start._M_node, 937*38fd1498Szrj this->_M_impl._M_finish._M_node + 1, 938*38fd1498Szrj __new_nstart + __old_num_nodes); 939*38fd1498Szrj } 940*38fd1498Szrj else 941*38fd1498Szrj { 942*38fd1498Szrj size_type __new_map_size = this->_M_impl._M_map_size 943*38fd1498Szrj + std::max(this->_M_impl._M_map_size, 944*38fd1498Szrj __nodes_to_add) + 2; 945*38fd1498Szrj 946*38fd1498Szrj _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); 947*38fd1498Szrj __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 948*38fd1498Szrj + (__add_at_front ? __nodes_to_add : 0); 949*38fd1498Szrj std::copy(this->_M_impl._M_start._M_node, 950*38fd1498Szrj this->_M_impl._M_finish._M_node + 1, 951*38fd1498Szrj __new_nstart); 952*38fd1498Szrj _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 953*38fd1498Szrj 954*38fd1498Szrj this->_M_impl._M_map = __new_map; 955*38fd1498Szrj this->_M_impl._M_map_size = __new_map_size; 956*38fd1498Szrj } 957*38fd1498Szrj 958*38fd1498Szrj this->_M_impl._M_start._M_set_node(__new_nstart); 959*38fd1498Szrj this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 960*38fd1498Szrj } 961*38fd1498Szrj 962*38fd1498Szrj // Overload for deque::iterators, exploiting the "segmented-iterator 963*38fd1498Szrj // optimization". 964*38fd1498Szrj template<typename _Tp> 965*38fd1498Szrj void 966*38fd1498Szrj fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first, 967*38fd1498Szrj const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value) 968*38fd1498Szrj { 969*38fd1498Szrj typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 970*38fd1498Szrj 971*38fd1498Szrj for (typename _Self::_Map_pointer __node = __first._M_node + 1; 972*38fd1498Szrj __node < __last._M_node; ++__node) 973*38fd1498Szrj std::fill(*__node, *__node + _Self::_S_buffer_size(), __value); 974*38fd1498Szrj 975*38fd1498Szrj if (__first._M_node != __last._M_node) 976*38fd1498Szrj { 977*38fd1498Szrj std::fill(__first._M_cur, __first._M_last, __value); 978*38fd1498Szrj std::fill(__last._M_first, __last._M_cur, __value); 979*38fd1498Szrj } 980*38fd1498Szrj else 981*38fd1498Szrj std::fill(__first._M_cur, __last._M_cur, __value); 982*38fd1498Szrj } 983*38fd1498Szrj 984*38fd1498Szrj template<typename _Tp> 985*38fd1498Szrj _Deque_iterator<_Tp, _Tp&, _Tp*> 986*38fd1498Szrj copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 987*38fd1498Szrj _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 988*38fd1498Szrj _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 989*38fd1498Szrj { 990*38fd1498Szrj typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 991*38fd1498Szrj typedef typename _Self::difference_type difference_type; 992*38fd1498Szrj 993*38fd1498Szrj difference_type __len = __last - __first; 994*38fd1498Szrj while (__len > 0) 995*38fd1498Szrj { 996*38fd1498Szrj const difference_type __clen 997*38fd1498Szrj = std::min(__len, std::min(__first._M_last - __first._M_cur, 998*38fd1498Szrj __result._M_last - __result._M_cur)); 999*38fd1498Szrj std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur); 1000*38fd1498Szrj __first += __clen; 1001*38fd1498Szrj __result += __clen; 1002*38fd1498Szrj __len -= __clen; 1003*38fd1498Szrj } 1004*38fd1498Szrj return __result; 1005*38fd1498Szrj } 1006*38fd1498Szrj 1007*38fd1498Szrj template<typename _Tp> 1008*38fd1498Szrj _Deque_iterator<_Tp, _Tp&, _Tp*> 1009*38fd1498Szrj copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 1010*38fd1498Szrj _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 1011*38fd1498Szrj _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 1012*38fd1498Szrj { 1013*38fd1498Szrj typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 1014*38fd1498Szrj typedef typename _Self::difference_type difference_type; 1015*38fd1498Szrj 1016*38fd1498Szrj difference_type __len = __last - __first; 1017*38fd1498Szrj while (__len > 0) 1018*38fd1498Szrj { 1019*38fd1498Szrj difference_type __llen = __last._M_cur - __last._M_first; 1020*38fd1498Szrj _Tp* __lend = __last._M_cur; 1021*38fd1498Szrj 1022*38fd1498Szrj difference_type __rlen = __result._M_cur - __result._M_first; 1023*38fd1498Szrj _Tp* __rend = __result._M_cur; 1024*38fd1498Szrj 1025*38fd1498Szrj if (!__llen) 1026*38fd1498Szrj { 1027*38fd1498Szrj __llen = _Self::_S_buffer_size(); 1028*38fd1498Szrj __lend = *(__last._M_node - 1) + __llen; 1029*38fd1498Szrj } 1030*38fd1498Szrj if (!__rlen) 1031*38fd1498Szrj { 1032*38fd1498Szrj __rlen = _Self::_S_buffer_size(); 1033*38fd1498Szrj __rend = *(__result._M_node - 1) + __rlen; 1034*38fd1498Szrj } 1035*38fd1498Szrj 1036*38fd1498Szrj const difference_type __clen = std::min(__len, 1037*38fd1498Szrj std::min(__llen, __rlen)); 1038*38fd1498Szrj std::copy_backward(__lend - __clen, __lend, __rend); 1039*38fd1498Szrj __last -= __clen; 1040*38fd1498Szrj __result -= __clen; 1041*38fd1498Szrj __len -= __clen; 1042*38fd1498Szrj } 1043*38fd1498Szrj return __result; 1044*38fd1498Szrj } 1045*38fd1498Szrj 1046*38fd1498Szrj #if __cplusplus >= 201103L 1047*38fd1498Szrj template<typename _Tp> 1048*38fd1498Szrj _Deque_iterator<_Tp, _Tp&, _Tp*> 1049*38fd1498Szrj move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 1050*38fd1498Szrj _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 1051*38fd1498Szrj _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 1052*38fd1498Szrj { 1053*38fd1498Szrj typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 1054*38fd1498Szrj typedef typename _Self::difference_type difference_type; 1055*38fd1498Szrj 1056*38fd1498Szrj difference_type __len = __last - __first; 1057*38fd1498Szrj while (__len > 0) 1058*38fd1498Szrj { 1059*38fd1498Szrj const difference_type __clen 1060*38fd1498Szrj = std::min(__len, std::min(__first._M_last - __first._M_cur, 1061*38fd1498Szrj __result._M_last - __result._M_cur)); 1062*38fd1498Szrj std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur); 1063*38fd1498Szrj __first += __clen; 1064*38fd1498Szrj __result += __clen; 1065*38fd1498Szrj __len -= __clen; 1066*38fd1498Szrj } 1067*38fd1498Szrj return __result; 1068*38fd1498Szrj } 1069*38fd1498Szrj 1070*38fd1498Szrj template<typename _Tp> 1071*38fd1498Szrj _Deque_iterator<_Tp, _Tp&, _Tp*> 1072*38fd1498Szrj move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 1073*38fd1498Szrj _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 1074*38fd1498Szrj _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 1075*38fd1498Szrj { 1076*38fd1498Szrj typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 1077*38fd1498Szrj typedef typename _Self::difference_type difference_type; 1078*38fd1498Szrj 1079*38fd1498Szrj difference_type __len = __last - __first; 1080*38fd1498Szrj while (__len > 0) 1081*38fd1498Szrj { 1082*38fd1498Szrj difference_type __llen = __last._M_cur - __last._M_first; 1083*38fd1498Szrj _Tp* __lend = __last._M_cur; 1084*38fd1498Szrj 1085*38fd1498Szrj difference_type __rlen = __result._M_cur - __result._M_first; 1086*38fd1498Szrj _Tp* __rend = __result._M_cur; 1087*38fd1498Szrj 1088*38fd1498Szrj if (!__llen) 1089*38fd1498Szrj { 1090*38fd1498Szrj __llen = _Self::_S_buffer_size(); 1091*38fd1498Szrj __lend = *(__last._M_node - 1) + __llen; 1092*38fd1498Szrj } 1093*38fd1498Szrj if (!__rlen) 1094*38fd1498Szrj { 1095*38fd1498Szrj __rlen = _Self::_S_buffer_size(); 1096*38fd1498Szrj __rend = *(__result._M_node - 1) + __rlen; 1097*38fd1498Szrj } 1098*38fd1498Szrj 1099*38fd1498Szrj const difference_type __clen = std::min(__len, 1100*38fd1498Szrj std::min(__llen, __rlen)); 1101*38fd1498Szrj std::move_backward(__lend - __clen, __lend, __rend); 1102*38fd1498Szrj __last -= __clen; 1103*38fd1498Szrj __result -= __clen; 1104*38fd1498Szrj __len -= __clen; 1105*38fd1498Szrj } 1106*38fd1498Szrj return __result; 1107*38fd1498Szrj } 1108*38fd1498Szrj #endif 1109*38fd1498Szrj 1110*38fd1498Szrj _GLIBCXX_END_NAMESPACE_CONTAINER 1111*38fd1498Szrj _GLIBCXX_END_NAMESPACE_VERSION 1112*38fd1498Szrj } // namespace std 1113*38fd1498Szrj 1114*38fd1498Szrj #endif 1115