deque.tcc revision 117397
1// Deque implementation (out of line) -*- C++ -*- 2 3// Copyright (C) 2001, 2002 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 2, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30/* 31 * 32 * Copyright (c) 1994 33 * Hewlett-Packard Company 34 * 35 * Permission to use, copy, modify, distribute and sell this software 36 * and its documentation for any purpose is hereby granted without fee, 37 * provided that the above copyright notice appear in all copies and 38 * that both that copyright notice and this permission notice appear 39 * in supporting documentation. Hewlett-Packard Company makes no 40 * representations about the suitability of this software for any 41 * purpose. It is provided "as is" without express or implied warranty. 42 * 43 * 44 * Copyright (c) 1997 45 * Silicon Graphics Computer Systems, Inc. 46 * 47 * Permission to use, copy, modify, distribute and sell this software 48 * and its documentation for any purpose is hereby granted without fee, 49 * provided that the above copyright notice appear in all copies and 50 * that both that copyright notice and this permission notice appear 51 * in supporting documentation. Silicon Graphics makes no 52 * representations about the suitability of this software for any 53 * purpose. It is provided "as is" without express or implied warranty. 54 */ 55 56/** @file deque.tcc 57 * This is an internal header file, included by other library headers. 58 * You should not attempt to use it directly. 59 */ 60 61#ifndef __GLIBCPP_INTERNAL_DEQUE_TCC 62#define __GLIBCPP_INTERNAL_DEQUE_TCC 63 64namespace std 65{ 66 template <typename _Tp, typename _Alloc> 67 deque<_Tp,_Alloc>& 68 deque<_Tp,_Alloc>:: 69 operator=(const deque& __x) 70 { 71 const size_type __len = size(); 72 if (&__x != this) 73 { 74 if (__len >= __x.size()) 75 erase(copy(__x.begin(), __x.end(), _M_start), _M_finish); 76 else 77 { 78 const_iterator __mid = __x.begin() + difference_type(__len); 79 copy(__x.begin(), __mid, _M_start); 80 insert(_M_finish, __mid, __x.end()); 81 } 82 } 83 return *this; 84 } 85 86 template <typename _Tp, typename _Alloc> 87 typename deque<_Tp,_Alloc>::iterator 88 deque<_Tp,_Alloc>:: 89 insert(iterator position, const value_type& __x) 90 { 91 if (position._M_cur == _M_start._M_cur) 92 { 93 push_front(__x); 94 return _M_start; 95 } 96 else if (position._M_cur == _M_finish._M_cur) 97 { 98 push_back(__x); 99 iterator __tmp = _M_finish; 100 --__tmp; 101 return __tmp; 102 } 103 else 104 return _M_insert_aux(position, __x); 105 } 106 107 template <typename _Tp, typename _Alloc> 108 typename deque<_Tp,_Alloc>::iterator 109 deque<_Tp,_Alloc>:: 110 erase(iterator __position) 111 { 112 iterator __next = __position; 113 ++__next; 114 size_type __index = __position - _M_start; 115 if (__index < (size() >> 1)) 116 { 117 copy_backward(_M_start, __position, __next); 118 pop_front(); 119 } 120 else 121 { 122 copy(__next, _M_finish, __position); 123 pop_back(); 124 } 125 return _M_start + __index; 126 } 127 128 template <typename _Tp, typename _Alloc> 129 typename deque<_Tp,_Alloc>::iterator 130 deque<_Tp,_Alloc>:: 131 erase(iterator __first, iterator __last) 132 { 133 if (__first == _M_start && __last == _M_finish) 134 { 135 clear(); 136 return _M_finish; 137 } 138 else 139 { 140 difference_type __n = __last - __first; 141 difference_type __elems_before = __first - _M_start; 142 if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) 143 { 144 copy_backward(_M_start, __first, __last); 145 iterator __new_start = _M_start + __n; 146 _Destroy(_M_start, __new_start); 147 _M_destroy_nodes(_M_start._M_node, __new_start._M_node); 148 _M_start = __new_start; 149 } 150 else 151 { 152 copy(__last, _M_finish, __first); 153 iterator __new_finish = _M_finish - __n; 154 _Destroy(__new_finish, _M_finish); 155 _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1); 156 _M_finish = __new_finish; 157 } 158 return _M_start + __elems_before; 159 } 160 } 161 162 template <typename _Tp, typename _Alloc> 163 void 164 deque<_Tp,_Alloc>:: 165 clear() 166 { 167 for (_Map_pointer __node = _M_start._M_node + 1; 168 __node < _M_finish._M_node; 169 ++__node) 170 { 171 _Destroy(*__node, *__node + _S_buffer_size()); 172 _M_deallocate_node(*__node); 173 } 174 175 if (_M_start._M_node != _M_finish._M_node) 176 { 177 _Destroy(_M_start._M_cur, _M_start._M_last); 178 _Destroy(_M_finish._M_first, _M_finish._M_cur); 179 _M_deallocate_node(_M_finish._M_first); 180 } 181 else 182 _Destroy(_M_start._M_cur, _M_finish._M_cur); 183 184 _M_finish = _M_start; 185 } 186 187 template <typename _Tp, class _Alloc> 188 template <typename _InputIter> 189 void 190 deque<_Tp,_Alloc> 191 ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag) 192 { 193 iterator __cur = begin(); 194 for ( ; __first != __last && __cur != end(); ++__cur, ++__first) 195 *__cur = *__first; 196 if (__first == __last) 197 erase(__cur, end()); 198 else 199 insert(end(), __first, __last); 200 } 201 202 template <typename _Tp, typename _Alloc> 203 void 204 deque<_Tp,_Alloc>:: 205 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) 206 { 207 if (__pos._M_cur == _M_start._M_cur) 208 { 209 iterator __new_start = _M_reserve_elements_at_front(__n); 210 try 211 { 212 uninitialized_fill(__new_start, _M_start, __x); 213 _M_start = __new_start; 214 } 215 catch(...) 216 { 217 _M_destroy_nodes(__new_start._M_node, _M_start._M_node); 218 __throw_exception_again; 219 } 220 } 221 else if (__pos._M_cur == _M_finish._M_cur) 222 { 223 iterator __new_finish = _M_reserve_elements_at_back(__n); 224 try 225 { 226 uninitialized_fill(_M_finish, __new_finish, __x); 227 _M_finish = __new_finish; 228 } 229 catch(...) 230 { 231 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); 232 __throw_exception_again; 233 } 234 } 235 else 236 _M_insert_aux(__pos, __n, __x); 237 } 238 239 template <typename _Tp, typename _Alloc> 240 void 241 deque<_Tp,_Alloc>:: 242 _M_fill_initialize(const value_type& __value) 243 { 244 _Map_pointer __cur; 245 try 246 { 247 for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur) 248 uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value); 249 uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value); 250 } 251 catch(...) 252 { 253 _Destroy(_M_start, iterator(*__cur, __cur)); 254 __throw_exception_again; 255 } 256 } 257 258 template <typename _Tp, typename _Alloc> 259 template <typename _InputIterator> 260 void 261 deque<_Tp,_Alloc>:: 262 _M_range_initialize(_InputIterator __first, _InputIterator __last, 263 input_iterator_tag) 264 { 265 _M_initialize_map(0); 266 try 267 { 268 for ( ; __first != __last; ++__first) 269 push_back(*__first); 270 } 271 catch(...) 272 { 273 clear(); 274 __throw_exception_again; 275 } 276 } 277 278 template <typename _Tp, typename _Alloc> 279 template <typename _ForwardIterator> 280 void 281 deque<_Tp,_Alloc>:: 282 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 283 forward_iterator_tag) 284 { 285 size_type __n = distance(__first, __last); 286 _M_initialize_map(__n); 287 288 _Map_pointer __cur_node; 289 try 290 { 291 for (__cur_node = _M_start._M_node; 292 __cur_node < _M_finish._M_node; 293 ++__cur_node) 294 { 295 _ForwardIterator __mid = __first; 296 advance(__mid, _S_buffer_size()); 297 uninitialized_copy(__first, __mid, *__cur_node); 298 __first = __mid; 299 } 300 uninitialized_copy(__first, __last, _M_finish._M_first); 301 } 302 catch(...) 303 { 304 _Destroy(_M_start, iterator(*__cur_node, __cur_node)); 305 __throw_exception_again; 306 } 307 } 308 309 // Called only if _M_finish._M_cur == _M_finish._M_last - 1. 310 template <typename _Tp, typename _Alloc> 311 void 312 deque<_Tp,_Alloc>:: 313 _M_push_back_aux(const value_type& __t) 314 { 315 value_type __t_copy = __t; 316 _M_reserve_map_at_back(); 317 *(_M_finish._M_node + 1) = _M_allocate_node(); 318 try 319 { 320 _Construct(_M_finish._M_cur, __t_copy); 321 _M_finish._M_set_node(_M_finish._M_node + 1); 322 _M_finish._M_cur = _M_finish._M_first; 323 } 324 catch(...) 325 { 326 _M_deallocate_node(*(_M_finish._M_node + 1)); 327 __throw_exception_again; 328 } 329 } 330 331 #ifdef _GLIBCPP_DEPRECATED 332 // Called only if _M_finish._M_cur == _M_finish._M_last - 1. 333 template <typename _Tp, typename _Alloc> 334 void 335 deque<_Tp,_Alloc>:: 336 _M_push_back_aux() 337 { 338 _M_reserve_map_at_back(); 339 *(_M_finish._M_node + 1) = _M_allocate_node(); 340 try 341 { 342 _Construct(_M_finish._M_cur); 343 _M_finish._M_set_node(_M_finish._M_node + 1); 344 _M_finish._M_cur = _M_finish._M_first; 345 } 346 catch(...) 347 { 348 _M_deallocate_node(*(_M_finish._M_node + 1)); 349 __throw_exception_again; 350 } 351 } 352 #endif 353 354 // Called only if _M_start._M_cur == _M_start._M_first. 355 template <typename _Tp, typename _Alloc> 356 void 357 deque<_Tp,_Alloc>:: 358 _M_push_front_aux(const value_type& __t) 359 { 360 value_type __t_copy = __t; 361 _M_reserve_map_at_front(); 362 *(_M_start._M_node - 1) = _M_allocate_node(); 363 try 364 { 365 _M_start._M_set_node(_M_start._M_node - 1); 366 _M_start._M_cur = _M_start._M_last - 1; 367 _Construct(_M_start._M_cur, __t_copy); 368 } 369 catch(...) 370 { 371 ++_M_start; 372 _M_deallocate_node(*(_M_start._M_node - 1)); 373 __throw_exception_again; 374 } 375 } 376 377 #ifdef _GLIBCPP_DEPRECATED 378 // Called only if _M_start._M_cur == _M_start._M_first. 379 template <typename _Tp, typename _Alloc> 380 void 381 deque<_Tp,_Alloc>:: 382 _M_push_front_aux() 383 { 384 _M_reserve_map_at_front(); 385 *(_M_start._M_node - 1) = _M_allocate_node(); 386 try 387 { 388 _M_start._M_set_node(_M_start._M_node - 1); 389 _M_start._M_cur = _M_start._M_last - 1; 390 _Construct(_M_start._M_cur); 391 } 392 catch(...) 393 { 394 ++_M_start; 395 _M_deallocate_node(*(_M_start._M_node - 1)); 396 __throw_exception_again; 397 } 398 } 399 #endif 400 401 // Called only if _M_finish._M_cur == _M_finish._M_first. 402 template <typename _Tp, typename _Alloc> 403 void deque<_Tp,_Alloc>:: 404 _M_pop_back_aux() 405 { 406 _M_deallocate_node(_M_finish._M_first); 407 _M_finish._M_set_node(_M_finish._M_node - 1); 408 _M_finish._M_cur = _M_finish._M_last - 1; 409 _Destroy(_M_finish._M_cur); 410 } 411 412 // Called only if _M_start._M_cur == _M_start._M_last - 1. Note that 413 // if the deque has at least one element (a precondition for this member 414 // function), and if _M_start._M_cur == _M_start._M_last, then the deque 415 // must have at least two nodes. 416 template <typename _Tp, typename _Alloc> 417 void deque<_Tp,_Alloc>:: 418 _M_pop_front_aux() 419 { 420 _Destroy(_M_start._M_cur); 421 _M_deallocate_node(_M_start._M_first); 422 _M_start._M_set_node(_M_start._M_node + 1); 423 _M_start._M_cur = _M_start._M_first; 424 } 425 426 template <typename _Tp, typename _Alloc> 427 template <typename _InputIterator> 428 void 429 deque<_Tp,_Alloc>:: 430 _M_range_insert_aux(iterator __pos, 431 _InputIterator __first, _InputIterator __last, 432 input_iterator_tag) 433 { 434 copy(__first, __last, inserter(*this, __pos)); 435 } 436 437 template <typename _Tp, typename _Alloc> 438 template <typename _ForwardIterator> 439 void 440 deque<_Tp,_Alloc>:: 441 _M_range_insert_aux(iterator __pos, 442 _ForwardIterator __first, _ForwardIterator __last, 443 forward_iterator_tag) 444 { 445 size_type __n = distance(__first, __last); 446 if (__pos._M_cur == _M_start._M_cur) 447 { 448 iterator __new_start = _M_reserve_elements_at_front(__n); 449 try 450 { 451 uninitialized_copy(__first, __last, __new_start); 452 _M_start = __new_start; 453 } 454 catch(...) 455 { 456 _M_destroy_nodes(__new_start._M_node, _M_start._M_node); 457 __throw_exception_again; 458 } 459 } 460 else if (__pos._M_cur == _M_finish._M_cur) 461 { 462 iterator __new_finish = _M_reserve_elements_at_back(__n); 463 try 464 { 465 uninitialized_copy(__first, __last, _M_finish); 466 _M_finish = __new_finish; 467 } 468 catch(...) 469 { 470 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); 471 __throw_exception_again; 472 } 473 } 474 else 475 _M_insert_aux(__pos, __first, __last, __n); 476 } 477 478 template <typename _Tp, typename _Alloc> 479 typename deque<_Tp, _Alloc>::iterator 480 deque<_Tp,_Alloc>:: 481 _M_insert_aux(iterator __pos, const value_type& __x) 482 { 483 difference_type __index = __pos - _M_start; 484 value_type __x_copy = __x; // XXX copy 485 if (static_cast<size_type>(__index) < size() / 2) 486 { 487 push_front(front()); 488 iterator __front1 = _M_start; 489 ++__front1; 490 iterator __front2 = __front1; 491 ++__front2; 492 __pos = _M_start + __index; 493 iterator __pos1 = __pos; 494 ++__pos1; 495 copy(__front2, __pos1, __front1); 496 } 497 else 498 { 499 push_back(back()); 500 iterator __back1 = _M_finish; 501 --__back1; 502 iterator __back2 = __back1; 503 --__back2; 504 __pos = _M_start + __index; 505 copy_backward(__pos, __back2, __back1); 506 } 507 *__pos = __x_copy; 508 return __pos; 509 } 510 511 #ifdef _GLIBCPP_DEPRECATED 512 // Nothing seems to actually use this. According to the pattern followed by 513 // the rest of the SGI code, it would be called by the deprecated insert(pos) 514 // function, but that has been replaced. We'll take our time removing this 515 // anyhow; mark for 3.4. -pme 516 template <typename _Tp, typename _Alloc> 517 typename deque<_Tp,_Alloc>::iterator 518 deque<_Tp,_Alloc>:: 519 _M_insert_aux(iterator __pos) 520 { 521 difference_type __index = __pos - _M_start; 522 if (static_cast<size_type>(__index) < size() / 2) 523 { 524 push_front(front()); 525 iterator __front1 = _M_start; 526 ++__front1; 527 iterator __front2 = __front1; 528 ++__front2; 529 __pos = _M_start + __index; 530 iterator __pos1 = __pos; 531 ++__pos1; 532 copy(__front2, __pos1, __front1); 533 } 534 else 535 { 536 push_back(back()); 537 iterator __back1 = _M_finish; 538 --__back1; 539 iterator __back2 = __back1; 540 --__back2; 541 __pos = _M_start + __index; 542 copy_backward(__pos, __back2, __back1); 543 } 544 *__pos = value_type(); 545 return __pos; 546 } 547 #endif 548 549 template <typename _Tp, typename _Alloc> 550 void 551 deque<_Tp,_Alloc>:: 552 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) 553 { 554 const difference_type __elems_before = __pos - _M_start; 555 size_type __length = this->size(); 556 value_type __x_copy = __x; 557 if (__elems_before < difference_type(__length / 2)) 558 { 559 iterator __new_start = _M_reserve_elements_at_front(__n); 560 iterator __old_start = _M_start; 561 __pos = _M_start + __elems_before; 562 try 563 { 564 if (__elems_before >= difference_type(__n)) 565 { 566 iterator __start_n = _M_start + difference_type(__n); 567 uninitialized_copy(_M_start, __start_n, __new_start); 568 _M_start = __new_start; 569 copy(__start_n, __pos, __old_start); 570 fill(__pos - difference_type(__n), __pos, __x_copy); 571 } 572 else 573 { 574 __uninitialized_copy_fill(_M_start, __pos, __new_start, 575 _M_start, __x_copy); 576 _M_start = __new_start; 577 fill(__old_start, __pos, __x_copy); 578 } 579 } 580 catch(...) 581 { 582 _M_destroy_nodes(__new_start._M_node, _M_start._M_node); 583 __throw_exception_again; 584 } 585 } 586 else 587 { 588 iterator __new_finish = _M_reserve_elements_at_back(__n); 589 iterator __old_finish = _M_finish; 590 const difference_type __elems_after = 591 difference_type(__length) - __elems_before; 592 __pos = _M_finish - __elems_after; 593 try 594 { 595 if (__elems_after > difference_type(__n)) 596 { 597 iterator __finish_n = _M_finish - difference_type(__n); 598 uninitialized_copy(__finish_n, _M_finish, _M_finish); 599 _M_finish = __new_finish; 600 copy_backward(__pos, __finish_n, __old_finish); 601 fill(__pos, __pos + difference_type(__n), __x_copy); 602 } 603 else 604 { 605 __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n), 606 __x_copy, __pos, _M_finish); 607 _M_finish = __new_finish; 608 fill(__pos, __old_finish, __x_copy); 609 } 610 } 611 catch(...) 612 { 613 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); 614 __throw_exception_again; 615 } 616 } 617 } 618 619 template <typename _Tp, typename _Alloc> 620 template <typename _ForwardIterator> 621 void 622 deque<_Tp,_Alloc>:: 623 _M_insert_aux(iterator __pos, 624 _ForwardIterator __first, _ForwardIterator __last, 625 size_type __n) 626 { 627 const difference_type __elemsbefore = __pos - _M_start; 628 size_type __length = size(); 629 if (static_cast<size_type>(__elemsbefore) < __length / 2) 630 { 631 iterator __new_start = _M_reserve_elements_at_front(__n); 632 iterator __old_start = _M_start; 633 __pos = _M_start + __elemsbefore; 634 try 635 { 636 if (__elemsbefore >= difference_type(__n)) 637 { 638 iterator __start_n = _M_start + difference_type(__n); 639 uninitialized_copy(_M_start, __start_n, __new_start); 640 _M_start = __new_start; 641 copy(__start_n, __pos, __old_start); 642 copy(__first, __last, __pos - difference_type(__n)); 643 } 644 else 645 { 646 _ForwardIterator __mid = __first; 647 advance(__mid, difference_type(__n) - __elemsbefore); 648 __uninitialized_copy_copy(_M_start, __pos, __first, __mid, 649 __new_start); 650 _M_start = __new_start; 651 copy(__mid, __last, __old_start); 652 } 653 } 654 catch(...) 655 { 656 _M_destroy_nodes(__new_start._M_node, _M_start._M_node); 657 __throw_exception_again; 658 } 659 } 660 else 661 { 662 iterator __new_finish = _M_reserve_elements_at_back(__n); 663 iterator __old_finish = _M_finish; 664 const difference_type __elemsafter = 665 difference_type(__length) - __elemsbefore; 666 __pos = _M_finish - __elemsafter; 667 try 668 { 669 if (__elemsafter > difference_type(__n)) 670 { 671 iterator __finish_n = _M_finish - difference_type(__n); 672 uninitialized_copy(__finish_n, _M_finish, _M_finish); 673 _M_finish = __new_finish; 674 copy_backward(__pos, __finish_n, __old_finish); 675 copy(__first, __last, __pos); 676 } 677 else 678 { 679 _ForwardIterator __mid = __first; 680 advance(__mid, __elemsafter); 681 __uninitialized_copy_copy(__mid, __last, __pos, 682 _M_finish, _M_finish); 683 _M_finish = __new_finish; 684 copy(__first, __mid, __pos); 685 } 686 } 687 catch(...) 688 { 689 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); 690 __throw_exception_again; 691 } 692 } 693 } 694 695 template <typename _Tp, typename _Alloc> 696 void 697 deque<_Tp,_Alloc>:: 698 _M_new_elements_at_front(size_type __new_elems) 699 { 700 size_type __new_nodes 701 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); 702 _M_reserve_map_at_front(__new_nodes); 703 size_type __i; 704 try 705 { 706 for (__i = 1; __i <= __new_nodes; ++__i) 707 *(_M_start._M_node - __i) = _M_allocate_node(); 708 } 709 catch(...) 710 { 711 for (size_type __j = 1; __j < __i; ++__j) 712 _M_deallocate_node(*(_M_start._M_node - __j)); 713 __throw_exception_again; 714 } 715 } 716 717 template <typename _Tp, typename _Alloc> 718 void 719 deque<_Tp,_Alloc>:: 720 _M_new_elements_at_back(size_type __new_elems) 721 { 722 size_type __new_nodes 723 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); 724 _M_reserve_map_at_back(__new_nodes); 725 size_type __i; 726 try 727 { 728 for (__i = 1; __i <= __new_nodes; ++__i) 729 *(_M_finish._M_node + __i) = _M_allocate_node(); 730 } 731 catch(...) 732 { 733 for (size_type __j = 1; __j < __i; ++__j) 734 _M_deallocate_node(*(_M_finish._M_node + __j)); 735 __throw_exception_again; 736 } 737 } 738 739 template <typename _Tp, typename _Alloc> 740 void 741 deque<_Tp,_Alloc>:: 742 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) 743 { 744 size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1; 745 size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 746 747 _Map_pointer __new_nstart; 748 if (_M_map_size > 2 * __new_num_nodes) 749 { 750 __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2 751 + (__add_at_front ? __nodes_to_add : 0); 752 if (__new_nstart < _M_start._M_node) 753 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart); 754 else 755 copy_backward(_M_start._M_node, _M_finish._M_node + 1, 756 __new_nstart + __old_num_nodes); 757 } 758 else 759 { 760 size_type __new_map_size = 761 _M_map_size + max(_M_map_size, __nodes_to_add) + 2; 762 763 _Map_pointer __new_map = _M_allocate_map(__new_map_size); 764 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 765 + (__add_at_front ? __nodes_to_add : 0); 766 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart); 767 _M_deallocate_map(_M_map, _M_map_size); 768 769 _M_map = __new_map; 770 _M_map_size = __new_map_size; 771 } 772 773 _M_start._M_set_node(__new_nstart); 774 _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 775 } 776} // namespace std 777 778#endif /* __GLIBCPP_INTERNAL_DEQUE_TCC */ 779 780