1 // Deque implementation (out of line) -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 4 // 2009, 2010, 2011 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 push_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 push_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 #endif 331 332 template <typename _Tp, typename _Alloc> 333 void 334 deque<_Tp, _Alloc>:: 335 _M_fill_initialize(const value_type& __value) 336 { 337 _Map_pointer __cur; 338 __try 339 { 340 for (__cur = this->_M_impl._M_start._M_node; 341 __cur < this->_M_impl._M_finish._M_node; 342 ++__cur) 343 std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(), 344 __value, _M_get_Tp_allocator()); 345 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first, 346 this->_M_impl._M_finish._M_cur, 347 __value, _M_get_Tp_allocator()); 348 } 349 __catch(...) 350 { 351 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), 352 _M_get_Tp_allocator()); 353 __throw_exception_again; 354 } 355 } 356 357 template <typename _Tp, typename _Alloc> 358 template <typename _InputIterator> 359 void 360 deque<_Tp, _Alloc>:: 361 _M_range_initialize(_InputIterator __first, _InputIterator __last, 362 std::input_iterator_tag) 363 { 364 this->_M_initialize_map(0); 365 __try 366 { 367 for (; __first != __last; ++__first) 368 push_back(*__first); 369 } 370 __catch(...) 371 { 372 clear(); 373 __throw_exception_again; 374 } 375 } 376 377 template <typename _Tp, typename _Alloc> 378 template <typename _ForwardIterator> 379 void 380 deque<_Tp, _Alloc>:: 381 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 382 std::forward_iterator_tag) 383 { 384 const size_type __n = std::distance(__first, __last); 385 this->_M_initialize_map(__n); 386 387 _Map_pointer __cur_node; 388 __try 389 { 390 for (__cur_node = this->_M_impl._M_start._M_node; 391 __cur_node < this->_M_impl._M_finish._M_node; 392 ++__cur_node) 393 { 394 _ForwardIterator __mid = __first; 395 std::advance(__mid, _S_buffer_size()); 396 std::__uninitialized_copy_a(__first, __mid, *__cur_node, 397 _M_get_Tp_allocator()); 398 __first = __mid; 399 } 400 std::__uninitialized_copy_a(__first, __last, 401 this->_M_impl._M_finish._M_first, 402 _M_get_Tp_allocator()); 403 } 404 __catch(...) 405 { 406 std::_Destroy(this->_M_impl._M_start, 407 iterator(*__cur_node, __cur_node), 408 _M_get_Tp_allocator()); 409 __throw_exception_again; 410 } 411 } 412 413 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. 414 template<typename _Tp, typename _Alloc> 415 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 416 template<typename... _Args> 417 void 418 deque<_Tp, _Alloc>:: 419 _M_push_back_aux(_Args&&... __args) 420 #else 421 void 422 deque<_Tp, _Alloc>:: 423 _M_push_back_aux(const value_type& __t) 424 #endif 425 { 426 _M_reserve_map_at_back(); 427 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); 428 __try 429 { 430 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 431 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, 432 std::forward<_Args>(__args)...); 433 #else 434 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t); 435 #endif 436 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node 437 + 1); 438 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; 439 } 440 __catch(...) 441 { 442 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); 443 __throw_exception_again; 444 } 445 } 446 447 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. 448 template<typename _Tp, typename _Alloc> 449 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 450 template<typename... _Args> 451 void 452 deque<_Tp, _Alloc>:: 453 _M_push_front_aux(_Args&&... __args) 454 #else 455 void 456 deque<_Tp, _Alloc>:: 457 _M_push_front_aux(const value_type& __t) 458 #endif 459 { 460 _M_reserve_map_at_front(); 461 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); 462 __try 463 { 464 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node 465 - 1); 466 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; 467 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 468 this->_M_impl.construct(this->_M_impl._M_start._M_cur, 469 std::forward<_Args>(__args)...); 470 #else 471 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t); 472 #endif 473 } 474 __catch(...) 475 { 476 ++this->_M_impl._M_start; 477 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); 478 __throw_exception_again; 479 } 480 } 481 482 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. 483 template <typename _Tp, typename _Alloc> 484 void deque<_Tp, _Alloc>:: 485 _M_pop_back_aux() 486 { 487 _M_deallocate_node(this->_M_impl._M_finish._M_first); 488 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); 489 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; 490 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur); 491 } 492 493 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. 494 // Note that if the deque has at least one element (a precondition for this 495 // member function), and if 496 // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, 497 // then the deque must have at least two nodes. 498 template <typename _Tp, typename _Alloc> 499 void deque<_Tp, _Alloc>:: 500 _M_pop_front_aux() 501 { 502 this->_M_impl.destroy(this->_M_impl._M_start._M_cur); 503 _M_deallocate_node(this->_M_impl._M_start._M_first); 504 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); 505 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; 506 } 507 508 template <typename _Tp, typename _Alloc> 509 template <typename _InputIterator> 510 void 511 deque<_Tp, _Alloc>:: 512 _M_range_insert_aux(iterator __pos, 513 _InputIterator __first, _InputIterator __last, 514 std::input_iterator_tag) 515 { std::copy(__first, __last, std::inserter(*this, __pos)); } 516 517 template <typename _Tp, typename _Alloc> 518 template <typename _ForwardIterator> 519 void 520 deque<_Tp, _Alloc>:: 521 _M_range_insert_aux(iterator __pos, 522 _ForwardIterator __first, _ForwardIterator __last, 523 std::forward_iterator_tag) 524 { 525 const size_type __n = std::distance(__first, __last); 526 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 527 { 528 iterator __new_start = _M_reserve_elements_at_front(__n); 529 __try 530 { 531 std::__uninitialized_copy_a(__first, __last, __new_start, 532 _M_get_Tp_allocator()); 533 this->_M_impl._M_start = __new_start; 534 } 535 __catch(...) 536 { 537 _M_destroy_nodes(__new_start._M_node, 538 this->_M_impl._M_start._M_node); 539 __throw_exception_again; 540 } 541 } 542 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 543 { 544 iterator __new_finish = _M_reserve_elements_at_back(__n); 545 __try 546 { 547 std::__uninitialized_copy_a(__first, __last, 548 this->_M_impl._M_finish, 549 _M_get_Tp_allocator()); 550 this->_M_impl._M_finish = __new_finish; 551 } 552 __catch(...) 553 { 554 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 555 __new_finish._M_node + 1); 556 __throw_exception_again; 557 } 558 } 559 else 560 _M_insert_aux(__pos, __first, __last, __n); 561 } 562 563 template<typename _Tp, typename _Alloc> 564 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 565 template<typename... _Args> 566 typename deque<_Tp, _Alloc>::iterator 567 deque<_Tp, _Alloc>:: 568 _M_insert_aux(iterator __pos, _Args&&... __args) 569 { 570 value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy 571 #else 572 typename deque<_Tp, _Alloc>::iterator 573 deque<_Tp, _Alloc>:: 574 _M_insert_aux(iterator __pos, const value_type& __x) 575 { 576 value_type __x_copy = __x; // XXX copy 577 #endif 578 difference_type __index = __pos - this->_M_impl._M_start; 579 if (static_cast<size_type>(__index) < size() / 2) 580 { 581 push_front(_GLIBCXX_MOVE(front())); 582 iterator __front1 = this->_M_impl._M_start; 583 ++__front1; 584 iterator __front2 = __front1; 585 ++__front2; 586 __pos = this->_M_impl._M_start + __index; 587 iterator __pos1 = __pos; 588 ++__pos1; 589 _GLIBCXX_MOVE3(__front2, __pos1, __front1); 590 } 591 else 592 { 593 push_back(_GLIBCXX_MOVE(back())); 594 iterator __back1 = this->_M_impl._M_finish; 595 --__back1; 596 iterator __back2 = __back1; 597 --__back2; 598 __pos = this->_M_impl._M_start + __index; 599 _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1); 600 } 601 *__pos = _GLIBCXX_MOVE(__x_copy); 602 return __pos; 603 } 604 605 template <typename _Tp, typename _Alloc> 606 void 607 deque<_Tp, _Alloc>:: 608 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) 609 { 610 const difference_type __elems_before = __pos - this->_M_impl._M_start; 611 const size_type __length = this->size(); 612 value_type __x_copy = __x; 613 if (__elems_before < difference_type(__length / 2)) 614 { 615 iterator __new_start = _M_reserve_elements_at_front(__n); 616 iterator __old_start = this->_M_impl._M_start; 617 __pos = this->_M_impl._M_start + __elems_before; 618 __try 619 { 620 if (__elems_before >= difference_type(__n)) 621 { 622 iterator __start_n = (this->_M_impl._M_start 623 + difference_type(__n)); 624 std::__uninitialized_move_a(this->_M_impl._M_start, 625 __start_n, __new_start, 626 _M_get_Tp_allocator()); 627 this->_M_impl._M_start = __new_start; 628 _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 629 std::fill(__pos - difference_type(__n), __pos, __x_copy); 630 } 631 else 632 { 633 std::__uninitialized_move_fill(this->_M_impl._M_start, 634 __pos, __new_start, 635 this->_M_impl._M_start, 636 __x_copy, 637 _M_get_Tp_allocator()); 638 this->_M_impl._M_start = __new_start; 639 std::fill(__old_start, __pos, __x_copy); 640 } 641 } 642 __catch(...) 643 { 644 _M_destroy_nodes(__new_start._M_node, 645 this->_M_impl._M_start._M_node); 646 __throw_exception_again; 647 } 648 } 649 else 650 { 651 iterator __new_finish = _M_reserve_elements_at_back(__n); 652 iterator __old_finish = this->_M_impl._M_finish; 653 const difference_type __elems_after = 654 difference_type(__length) - __elems_before; 655 __pos = this->_M_impl._M_finish - __elems_after; 656 __try 657 { 658 if (__elems_after > difference_type(__n)) 659 { 660 iterator __finish_n = (this->_M_impl._M_finish 661 - difference_type(__n)); 662 std::__uninitialized_move_a(__finish_n, 663 this->_M_impl._M_finish, 664 this->_M_impl._M_finish, 665 _M_get_Tp_allocator()); 666 this->_M_impl._M_finish = __new_finish; 667 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 668 std::fill(__pos, __pos + difference_type(__n), __x_copy); 669 } 670 else 671 { 672 std::__uninitialized_fill_move(this->_M_impl._M_finish, 673 __pos + difference_type(__n), 674 __x_copy, __pos, 675 this->_M_impl._M_finish, 676 _M_get_Tp_allocator()); 677 this->_M_impl._M_finish = __new_finish; 678 std::fill(__pos, __old_finish, __x_copy); 679 } 680 } 681 __catch(...) 682 { 683 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 684 __new_finish._M_node + 1); 685 __throw_exception_again; 686 } 687 } 688 } 689 690 template <typename _Tp, typename _Alloc> 691 template <typename _ForwardIterator> 692 void 693 deque<_Tp, _Alloc>:: 694 _M_insert_aux(iterator __pos, 695 _ForwardIterator __first, _ForwardIterator __last, 696 size_type __n) 697 { 698 const difference_type __elemsbefore = __pos - this->_M_impl._M_start; 699 const size_type __length = size(); 700 if (static_cast<size_type>(__elemsbefore) < __length / 2) 701 { 702 iterator __new_start = _M_reserve_elements_at_front(__n); 703 iterator __old_start = this->_M_impl._M_start; 704 __pos = this->_M_impl._M_start + __elemsbefore; 705 __try 706 { 707 if (__elemsbefore >= difference_type(__n)) 708 { 709 iterator __start_n = (this->_M_impl._M_start 710 + difference_type(__n)); 711 std::__uninitialized_move_a(this->_M_impl._M_start, 712 __start_n, __new_start, 713 _M_get_Tp_allocator()); 714 this->_M_impl._M_start = __new_start; 715 _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 716 std::copy(__first, __last, __pos - difference_type(__n)); 717 } 718 else 719 { 720 _ForwardIterator __mid = __first; 721 std::advance(__mid, difference_type(__n) - __elemsbefore); 722 std::__uninitialized_move_copy(this->_M_impl._M_start, 723 __pos, __first, __mid, 724 __new_start, 725 _M_get_Tp_allocator()); 726 this->_M_impl._M_start = __new_start; 727 std::copy(__mid, __last, __old_start); 728 } 729 } 730 __catch(...) 731 { 732 _M_destroy_nodes(__new_start._M_node, 733 this->_M_impl._M_start._M_node); 734 __throw_exception_again; 735 } 736 } 737 else 738 { 739 iterator __new_finish = _M_reserve_elements_at_back(__n); 740 iterator __old_finish = this->_M_impl._M_finish; 741 const difference_type __elemsafter = 742 difference_type(__length) - __elemsbefore; 743 __pos = this->_M_impl._M_finish - __elemsafter; 744 __try 745 { 746 if (__elemsafter > difference_type(__n)) 747 { 748 iterator __finish_n = (this->_M_impl._M_finish 749 - difference_type(__n)); 750 std::__uninitialized_move_a(__finish_n, 751 this->_M_impl._M_finish, 752 this->_M_impl._M_finish, 753 _M_get_Tp_allocator()); 754 this->_M_impl._M_finish = __new_finish; 755 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 756 std::copy(__first, __last, __pos); 757 } 758 else 759 { 760 _ForwardIterator __mid = __first; 761 std::advance(__mid, __elemsafter); 762 std::__uninitialized_copy_move(__mid, __last, __pos, 763 this->_M_impl._M_finish, 764 this->_M_impl._M_finish, 765 _M_get_Tp_allocator()); 766 this->_M_impl._M_finish = __new_finish; 767 std::copy(__first, __mid, __pos); 768 } 769 } 770 __catch(...) 771 { 772 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 773 __new_finish._M_node + 1); 774 __throw_exception_again; 775 } 776 } 777 } 778 779 template<typename _Tp, typename _Alloc> 780 void 781 deque<_Tp, _Alloc>:: 782 _M_destroy_data_aux(iterator __first, iterator __last) 783 { 784 for (_Map_pointer __node = __first._M_node + 1; 785 __node < __last._M_node; ++__node) 786 std::_Destroy(*__node, *__node + _S_buffer_size(), 787 _M_get_Tp_allocator()); 788 789 if (__first._M_node != __last._M_node) 790 { 791 std::_Destroy(__first._M_cur, __first._M_last, 792 _M_get_Tp_allocator()); 793 std::_Destroy(__last._M_first, __last._M_cur, 794 _M_get_Tp_allocator()); 795 } 796 else 797 std::_Destroy(__first._M_cur, __last._M_cur, 798 _M_get_Tp_allocator()); 799 } 800 801 template <typename _Tp, typename _Alloc> 802 void 803 deque<_Tp, _Alloc>:: 804 _M_new_elements_at_front(size_type __new_elems) 805 { 806 if (this->max_size() - this->size() < __new_elems) 807 __throw_length_error(__N("deque::_M_new_elements_at_front")); 808 809 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 810 / _S_buffer_size()); 811 _M_reserve_map_at_front(__new_nodes); 812 size_type __i; 813 __try 814 { 815 for (__i = 1; __i <= __new_nodes; ++__i) 816 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); 817 } 818 __catch(...) 819 { 820 for (size_type __j = 1; __j < __i; ++__j) 821 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); 822 __throw_exception_again; 823 } 824 } 825 826 template <typename _Tp, typename _Alloc> 827 void 828 deque<_Tp, _Alloc>:: 829 _M_new_elements_at_back(size_type __new_elems) 830 { 831 if (this->max_size() - this->size() < __new_elems) 832 __throw_length_error(__N("deque::_M_new_elements_at_back")); 833 834 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 835 / _S_buffer_size()); 836 _M_reserve_map_at_back(__new_nodes); 837 size_type __i; 838 __try 839 { 840 for (__i = 1; __i <= __new_nodes; ++__i) 841 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); 842 } 843 __catch(...) 844 { 845 for (size_type __j = 1; __j < __i; ++__j) 846 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); 847 __throw_exception_again; 848 } 849 } 850 851 template <typename _Tp, typename _Alloc> 852 void 853 deque<_Tp, _Alloc>:: 854 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) 855 { 856 const size_type __old_num_nodes 857 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; 858 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 859 860 _Map_pointer __new_nstart; 861 if (this->_M_impl._M_map_size > 2 * __new_num_nodes) 862 { 863 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size 864 - __new_num_nodes) / 2 865 + (__add_at_front ? __nodes_to_add : 0); 866 if (__new_nstart < this->_M_impl._M_start._M_node) 867 std::copy(this->_M_impl._M_start._M_node, 868 this->_M_impl._M_finish._M_node + 1, 869 __new_nstart); 870 else 871 std::copy_backward(this->_M_impl._M_start._M_node, 872 this->_M_impl._M_finish._M_node + 1, 873 __new_nstart + __old_num_nodes); 874 } 875 else 876 { 877 size_type __new_map_size = this->_M_impl._M_map_size 878 + std::max(this->_M_impl._M_map_size, 879 __nodes_to_add) + 2; 880 881 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); 882 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 883 + (__add_at_front ? __nodes_to_add : 0); 884 std::copy(this->_M_impl._M_start._M_node, 885 this->_M_impl._M_finish._M_node + 1, 886 __new_nstart); 887 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 888 889 this->_M_impl._M_map = __new_map; 890 this->_M_impl._M_map_size = __new_map_size; 891 } 892 893 this->_M_impl._M_start._M_set_node(__new_nstart); 894 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 895 } 896 897 // Overload for deque::iterators, exploiting the "segmented-iterator 898 // optimization". 899 template<typename _Tp> 900 void 901 fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first, 902 const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value) 903 { 904 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 905 906 for (typename _Self::_Map_pointer __node = __first._M_node + 1; 907 __node < __last._M_node; ++__node) 908 std::fill(*__node, *__node + _Self::_S_buffer_size(), __value); 909 910 if (__first._M_node != __last._M_node) 911 { 912 std::fill(__first._M_cur, __first._M_last, __value); 913 std::fill(__last._M_first, __last._M_cur, __value); 914 } 915 else 916 std::fill(__first._M_cur, __last._M_cur, __value); 917 } 918 919 template<typename _Tp> 920 _Deque_iterator<_Tp, _Tp&, _Tp*> 921 copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 922 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 923 _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 924 { 925 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 926 typedef typename _Self::difference_type difference_type; 927 928 difference_type __len = __last - __first; 929 while (__len > 0) 930 { 931 const difference_type __clen 932 = std::min(__len, std::min(__first._M_last - __first._M_cur, 933 __result._M_last - __result._M_cur)); 934 std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur); 935 __first += __clen; 936 __result += __clen; 937 __len -= __clen; 938 } 939 return __result; 940 } 941 942 template<typename _Tp> 943 _Deque_iterator<_Tp, _Tp&, _Tp*> 944 copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 945 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 946 _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 947 { 948 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 949 typedef typename _Self::difference_type difference_type; 950 951 difference_type __len = __last - __first; 952 while (__len > 0) 953 { 954 difference_type __llen = __last._M_cur - __last._M_first; 955 _Tp* __lend = __last._M_cur; 956 957 difference_type __rlen = __result._M_cur - __result._M_first; 958 _Tp* __rend = __result._M_cur; 959 960 if (!__llen) 961 { 962 __llen = _Self::_S_buffer_size(); 963 __lend = *(__last._M_node - 1) + __llen; 964 } 965 if (!__rlen) 966 { 967 __rlen = _Self::_S_buffer_size(); 968 __rend = *(__result._M_node - 1) + __rlen; 969 } 970 971 const difference_type __clen = std::min(__len, 972 std::min(__llen, __rlen)); 973 std::copy_backward(__lend - __clen, __lend, __rend); 974 __last -= __clen; 975 __result -= __clen; 976 __len -= __clen; 977 } 978 return __result; 979 } 980 981 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 982 template<typename _Tp> 983 _Deque_iterator<_Tp, _Tp&, _Tp*> 984 move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 985 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 986 _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 987 { 988 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 989 typedef typename _Self::difference_type difference_type; 990 991 difference_type __len = __last - __first; 992 while (__len > 0) 993 { 994 const difference_type __clen 995 = std::min(__len, std::min(__first._M_last - __first._M_cur, 996 __result._M_last - __result._M_cur)); 997 std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur); 998 __first += __clen; 999 __result += __clen; 1000 __len -= __clen; 1001 } 1002 return __result; 1003 } 1004 1005 template<typename _Tp> 1006 _Deque_iterator<_Tp, _Tp&, _Tp*> 1007 move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 1008 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 1009 _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 1010 { 1011 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 1012 typedef typename _Self::difference_type difference_type; 1013 1014 difference_type __len = __last - __first; 1015 while (__len > 0) 1016 { 1017 difference_type __llen = __last._M_cur - __last._M_first; 1018 _Tp* __lend = __last._M_cur; 1019 1020 difference_type __rlen = __result._M_cur - __result._M_first; 1021 _Tp* __rend = __result._M_cur; 1022 1023 if (!__llen) 1024 { 1025 __llen = _Self::_S_buffer_size(); 1026 __lend = *(__last._M_node - 1) + __llen; 1027 } 1028 if (!__rlen) 1029 { 1030 __rlen = _Self::_S_buffer_size(); 1031 __rend = *(__result._M_node - 1) + __rlen; 1032 } 1033 1034 const difference_type __clen = std::min(__len, 1035 std::min(__llen, __rlen)); 1036 std::move_backward(__lend - __clen, __lend, __rend); 1037 __last -= __clen; 1038 __result -= __clen; 1039 __len -= __clen; 1040 } 1041 return __result; 1042 } 1043 #endif 1044 1045 _GLIBCXX_END_NAMESPACE_CONTAINER 1046 } // namespace std 1047 1048 #endif 1049
