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