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