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