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