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