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