1 // Deque implementation (out of line) -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004 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 _DEQUE_TCC 62 #define _DEQUE_TCC 1 63 64 namespace _GLIBCXX_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(std::copy(__x.begin(), __x.end(), this->_M_impl._M_start), 76 this->_M_impl._M_finish); 77 else 78 { 79 const_iterator __mid = __x.begin() + difference_type(__len); 80 std::copy(__x.begin(), __mid, this->_M_impl._M_start); 81 insert(this->_M_impl._M_finish, __mid, __x.end()); 82 } 83 } 84 return *this; 85 } 86 87 template <typename _Tp, typename _Alloc> 88 typename deque<_Tp,_Alloc>::iterator 89 deque<_Tp,_Alloc>:: 90 insert(iterator position, const value_type& __x) 91 { 92 if (position._M_cur == this->_M_impl._M_start._M_cur) 93 { 94 push_front(__x); 95 return this->_M_impl._M_start; 96 } 97 else if (position._M_cur == this->_M_impl._M_finish._M_cur) 98 { 99 push_back(__x); 100 iterator __tmp = this->_M_impl._M_finish; 101 --__tmp; 102 return __tmp; 103 } 104 else 105 return _M_insert_aux(position, __x); 106 } 107 108 template <typename _Tp, typename _Alloc> 109 typename deque<_Tp,_Alloc>::iterator 110 deque<_Tp,_Alloc>:: 111 erase(iterator __position) 112 { 113 iterator __next = __position; 114 ++__next; 115 size_type __index = __position - this->_M_impl._M_start; 116 if (__index < (size() >> 1)) 117 { 118 std::copy_backward(this->_M_impl._M_start, __position, __next); 119 pop_front(); 120 } 121 else 122 { 123 std::copy(__next, this->_M_impl._M_finish, __position); 124 pop_back(); 125 } 126 return this->_M_impl._M_start + __index; 127 } 128 129 template <typename _Tp, typename _Alloc> 130 typename deque<_Tp,_Alloc>::iterator 131 deque<_Tp,_Alloc>:: 132 erase(iterator __first, iterator __last) 133 { 134 if (__first == this->_M_impl._M_start && __last == this->_M_impl._M_finish) 135 { 136 clear(); 137 return this->_M_impl._M_finish; 138 } 139 else 140 { 141 const difference_type __n = __last - __first; 142 const difference_type __elems_before = __first - this->_M_impl._M_start; 143 if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) 144 { 145 std::copy_backward(this->_M_impl._M_start, __first, __last); 146 iterator __new_start = this->_M_impl._M_start + __n; 147 std::_Destroy(this->_M_impl._M_start, __new_start); 148 _M_destroy_nodes(this->_M_impl._M_start._M_node, __new_start._M_node); 149 this->_M_impl._M_start = __new_start; 150 } 151 else 152 { 153 std::copy(__last, this->_M_impl._M_finish, __first); 154 iterator __new_finish = this->_M_impl._M_finish - __n; 155 std::_Destroy(__new_finish, this->_M_impl._M_finish); 156 _M_destroy_nodes(__new_finish._M_node + 1, 157 this->_M_impl._M_finish._M_node + 1); 158 this->_M_impl._M_finish = __new_finish; 159 } 160 return this->_M_impl._M_start + __elems_before; 161 } 162 } 163 164 template <typename _Tp, typename _Alloc> 165 void 166 deque<_Tp,_Alloc>:: 167 clear() 168 { 169 for (_Map_pointer __node = this->_M_impl._M_start._M_node + 1; 170 __node < this->_M_impl._M_finish._M_node; 171 ++__node) 172 { 173 std::_Destroy(*__node, *__node + _S_buffer_size()); 174 _M_deallocate_node(*__node); 175 } 176 177 if (this->_M_impl._M_start._M_node != this->_M_impl._M_finish._M_node) 178 { 179 std::_Destroy(this->_M_impl._M_start._M_cur, this->_M_impl._M_start._M_last); 180 std::_Destroy(this->_M_impl._M_finish._M_first, this->_M_impl._M_finish._M_cur); 181 _M_deallocate_node(this->_M_impl._M_finish._M_first); 182 } 183 else 184 std::_Destroy(this->_M_impl._M_start._M_cur, this->_M_impl._M_finish._M_cur); 185 186 this->_M_impl._M_finish = this->_M_impl._M_start; 187 } 188 189 template <typename _Tp, class _Alloc> 190 template <typename _InputIterator> 191 void 192 deque<_Tp,_Alloc> 193 ::_M_assign_aux(_InputIterator __first, _InputIterator __last, 194 input_iterator_tag) 195 { 196 iterator __cur = begin(); 197 for ( ; __first != __last && __cur != end(); ++__cur, ++__first) 198 *__cur = *__first; 199 if (__first == __last) 200 erase(__cur, end()); 201 else 202 insert(end(), __first, __last); 203 } 204 205 template <typename _Tp, typename _Alloc> 206 void 207 deque<_Tp,_Alloc>:: 208 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) 209 { 210 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 211 { 212 iterator __new_start = _M_reserve_elements_at_front(__n); 213 try 214 { 215 std::uninitialized_fill(__new_start, this->_M_impl._M_start, __x); 216 this->_M_impl._M_start = __new_start; 217 } 218 catch(...) 219 { 220 _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node); 221 __throw_exception_again; 222 } 223 } 224 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 225 { 226 iterator __new_finish = _M_reserve_elements_at_back(__n); 227 try 228 { 229 std::uninitialized_fill(this->_M_impl._M_finish, __new_finish, __x); 230 this->_M_impl._M_finish = __new_finish; 231 } 232 catch(...) 233 { 234 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 235 __new_finish._M_node + 1); 236 __throw_exception_again; 237 } 238 } 239 else 240 _M_insert_aux(__pos, __n, __x); 241 } 242 243 template <typename _Tp, typename _Alloc> 244 void 245 deque<_Tp,_Alloc>:: 246 _M_fill_initialize(const value_type& __value) 247 { 248 _Map_pointer __cur; 249 try 250 { 251 for (__cur = this->_M_impl._M_start._M_node; 252 __cur < this->_M_impl._M_finish._M_node; 253 ++__cur) 254 std::uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value); 255 std::uninitialized_fill(this->_M_impl._M_finish._M_first, 256 this->_M_impl._M_finish._M_cur, 257 __value); 258 } 259 catch(...) 260 { 261 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur)); 262 __throw_exception_again; 263 } 264 } 265 266 template <typename _Tp, typename _Alloc> 267 template <typename _InputIterator> 268 void 269 deque<_Tp,_Alloc>:: 270 _M_range_initialize(_InputIterator __first, _InputIterator __last, 271 input_iterator_tag) 272 { 273 this->_M_initialize_map(0); 274 try 275 { 276 for ( ; __first != __last; ++__first) 277 push_back(*__first); 278 } 279 catch(...) 280 { 281 clear(); 282 __throw_exception_again; 283 } 284 } 285 286 template <typename _Tp, typename _Alloc> 287 template <typename _ForwardIterator> 288 void 289 deque<_Tp,_Alloc>:: 290 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 291 forward_iterator_tag) 292 { 293 const size_type __n = std::distance(__first, __last); 294 this->_M_initialize_map(__n); 295 296 _Map_pointer __cur_node; 297 try 298 { 299 for (__cur_node = this->_M_impl._M_start._M_node; 300 __cur_node < this->_M_impl._M_finish._M_node; 301 ++__cur_node) 302 { 303 _ForwardIterator __mid = __first; 304 std::advance(__mid, _S_buffer_size()); 305 std::uninitialized_copy(__first, __mid, *__cur_node); 306 __first = __mid; 307 } 308 std::uninitialized_copy(__first, __last, this->_M_impl._M_finish._M_first); 309 } 310 catch(...) 311 { 312 std::_Destroy(this->_M_impl._M_start, iterator(*__cur_node, __cur_node)); 313 __throw_exception_again; 314 } 315 } 316 317 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. 318 template <typename _Tp, typename _Alloc> 319 void 320 deque<_Tp,_Alloc>:: 321 _M_push_back_aux(const value_type& __t) 322 { 323 value_type __t_copy = __t; 324 _M_reserve_map_at_back(); 325 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); 326 try 327 { 328 std::_Construct(this->_M_impl._M_finish._M_cur, __t_copy); 329 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node + 1); 330 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; 331 } 332 catch(...) 333 { 334 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); 335 __throw_exception_again; 336 } 337 } 338 339 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. 340 template <typename _Tp, typename _Alloc> 341 void 342 deque<_Tp,_Alloc>:: 343 _M_push_front_aux(const value_type& __t) 344 { 345 value_type __t_copy = __t; 346 _M_reserve_map_at_front(); 347 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); 348 try 349 { 350 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node - 1); 351 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; 352 std::_Construct(this->_M_impl._M_start._M_cur, __t_copy); 353 } 354 catch(...) 355 { 356 ++this->_M_impl._M_start; 357 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); 358 __throw_exception_again; 359 } 360 } 361 362 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. 363 template <typename _Tp, typename _Alloc> 364 void deque<_Tp,_Alloc>:: 365 _M_pop_back_aux() 366 { 367 _M_deallocate_node(this->_M_impl._M_finish._M_first); 368 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); 369 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; 370 std::_Destroy(this->_M_impl._M_finish._M_cur); 371 } 372 373 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. Note that 374 // if the deque has at least one element (a precondition for this member 375 // function), and if _M_impl._M_start._M_cur == _M_impl._M_start._M_last, then the deque 376 // must have at least two nodes. 377 template <typename _Tp, typename _Alloc> 378 void deque<_Tp,_Alloc>:: 379 _M_pop_front_aux() 380 { 381 std::_Destroy(this->_M_impl._M_start._M_cur); 382 _M_deallocate_node(this->_M_impl._M_start._M_first); 383 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); 384 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; 385 } 386 387 template <typename _Tp, typename _Alloc> 388 template <typename _InputIterator> 389 void 390 deque<_Tp,_Alloc>:: 391 _M_range_insert_aux(iterator __pos, 392 _InputIterator __first, _InputIterator __last, 393 input_iterator_tag) 394 { std::copy(__first, __last, std::inserter(*this, __pos)); } 395 396 template <typename _Tp, typename _Alloc> 397 template <typename _ForwardIterator> 398 void 399 deque<_Tp,_Alloc>:: 400 _M_range_insert_aux(iterator __pos, 401 _ForwardIterator __first, _ForwardIterator __last, 402 forward_iterator_tag) 403 { 404 size_type __n = std::distance(__first, __last); 405 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 406 { 407 iterator __new_start = _M_reserve_elements_at_front(__n); 408 try 409 { 410 std::uninitialized_copy(__first, __last, __new_start); 411 this->_M_impl._M_start = __new_start; 412 } 413 catch(...) 414 { 415 _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node); 416 __throw_exception_again; 417 } 418 } 419 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 420 { 421 iterator __new_finish = _M_reserve_elements_at_back(__n); 422 try 423 { 424 std::uninitialized_copy(__first, __last, this->_M_impl._M_finish); 425 this->_M_impl._M_finish = __new_finish; 426 } 427 catch(...) 428 { 429 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 430 __new_finish._M_node + 1); 431 __throw_exception_again; 432 } 433 } 434 else 435 _M_insert_aux(__pos, __first, __last, __n); 436 } 437 438 template <typename _Tp, typename _Alloc> 439 typename deque<_Tp, _Alloc>::iterator 440 deque<_Tp,_Alloc>:: 441 _M_insert_aux(iterator __pos, const value_type& __x) 442 { 443 difference_type __index = __pos - this->_M_impl._M_start; 444 value_type __x_copy = __x; // XXX copy 445 if (static_cast<size_type>(__index) < size() / 2) 446 { 447 push_front(front()); 448 iterator __front1 = this->_M_impl._M_start; 449 ++__front1; 450 iterator __front2 = __front1; 451 ++__front2; 452 __pos = this->_M_impl._M_start + __index; 453 iterator __pos1 = __pos; 454 ++__pos1; 455 std::copy(__front2, __pos1, __front1); 456 } 457 else 458 { 459 push_back(back()); 460 iterator __back1 = this->_M_impl._M_finish; 461 --__back1; 462 iterator __back2 = __back1; 463 --__back2; 464 __pos = this->_M_impl._M_start + __index; 465 std::copy_backward(__pos, __back2, __back1); 466 } 467 *__pos = __x_copy; 468 return __pos; 469 } 470 471 template <typename _Tp, typename _Alloc> 472 void 473 deque<_Tp,_Alloc>:: 474 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) 475 { 476 const difference_type __elems_before = __pos - this->_M_impl._M_start; 477 size_type __length = this->size(); 478 value_type __x_copy = __x; 479 if (__elems_before < difference_type(__length / 2)) 480 { 481 iterator __new_start = _M_reserve_elements_at_front(__n); 482 iterator __old_start = this->_M_impl._M_start; 483 __pos = this->_M_impl._M_start + __elems_before; 484 try 485 { 486 if (__elems_before >= difference_type(__n)) 487 { 488 iterator __start_n = this->_M_impl._M_start + difference_type(__n); 489 std::uninitialized_copy(this->_M_impl._M_start, __start_n, 490 __new_start); 491 this->_M_impl._M_start = __new_start; 492 std::copy(__start_n, __pos, __old_start); 493 fill(__pos - difference_type(__n), __pos, __x_copy); 494 } 495 else 496 { 497 std::__uninitialized_copy_fill(this->_M_impl._M_start, __pos, 498 __new_start, 499 this->_M_impl._M_start, __x_copy); 500 this->_M_impl._M_start = __new_start; 501 std::fill(__old_start, __pos, __x_copy); 502 } 503 } 504 catch(...) 505 { 506 _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node); 507 __throw_exception_again; 508 } 509 } 510 else 511 { 512 iterator __new_finish = _M_reserve_elements_at_back(__n); 513 iterator __old_finish = this->_M_impl._M_finish; 514 const difference_type __elems_after = 515 difference_type(__length) - __elems_before; 516 __pos = this->_M_impl._M_finish - __elems_after; 517 try 518 { 519 if (__elems_after > difference_type(__n)) 520 { 521 iterator __finish_n = this->_M_impl._M_finish - difference_type(__n); 522 std::uninitialized_copy(__finish_n, this->_M_impl._M_finish, 523 this->_M_impl._M_finish); 524 this->_M_impl._M_finish = __new_finish; 525 std::copy_backward(__pos, __finish_n, __old_finish); 526 std::fill(__pos, __pos + difference_type(__n), __x_copy); 527 } 528 else 529 { 530 std::__uninitialized_fill_copy(this->_M_impl._M_finish, 531 __pos + difference_type(__n), 532 __x_copy, __pos, 533 this->_M_impl._M_finish); 534 this->_M_impl._M_finish = __new_finish; 535 std::fill(__pos, __old_finish, __x_copy); 536 } 537 } 538 catch(...) 539 { 540 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 541 __new_finish._M_node + 1); 542 __throw_exception_again; 543 } 544 } 545 } 546 547 template <typename _Tp, typename _Alloc> 548 template <typename _ForwardIterator> 549 void 550 deque<_Tp,_Alloc>:: 551 _M_insert_aux(iterator __pos, 552 _ForwardIterator __first, _ForwardIterator __last, 553 size_type __n) 554 { 555 const difference_type __elemsbefore = __pos - this->_M_impl._M_start; 556 size_type __length = size(); 557 if (static_cast<size_type>(__elemsbefore) < __length / 2) 558 { 559 iterator __new_start = _M_reserve_elements_at_front(__n); 560 iterator __old_start = this->_M_impl._M_start; 561 __pos = this->_M_impl._M_start + __elemsbefore; 562 try 563 { 564 if (__elemsbefore >= difference_type(__n)) 565 { 566 iterator __start_n = this->_M_impl._M_start + difference_type(__n); 567 std::uninitialized_copy(this->_M_impl._M_start, __start_n, 568 __new_start); 569 this->_M_impl._M_start = __new_start; 570 std::copy(__start_n, __pos, __old_start); 571 std::copy(__first, __last, __pos - difference_type(__n)); 572 } 573 else 574 { 575 _ForwardIterator __mid = __first; 576 std::advance(__mid, difference_type(__n) - __elemsbefore); 577 std::__uninitialized_copy_copy(this->_M_impl._M_start, __pos, 578 __first, __mid, __new_start); 579 this->_M_impl._M_start = __new_start; 580 std::copy(__mid, __last, __old_start); 581 } 582 } 583 catch(...) 584 { 585 _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node); 586 __throw_exception_again; 587 } 588 } 589 else 590 { 591 iterator __new_finish = _M_reserve_elements_at_back(__n); 592 iterator __old_finish = this->_M_impl._M_finish; 593 const difference_type __elemsafter = 594 difference_type(__length) - __elemsbefore; 595 __pos = this->_M_impl._M_finish - __elemsafter; 596 try 597 { 598 if (__elemsafter > difference_type(__n)) 599 { 600 iterator __finish_n = this->_M_impl._M_finish - difference_type(__n); 601 std::uninitialized_copy(__finish_n, 602 this->_M_impl._M_finish, 603 this->_M_impl._M_finish); 604 this->_M_impl._M_finish = __new_finish; 605 std::copy_backward(__pos, __finish_n, __old_finish); 606 std::copy(__first, __last, __pos); 607 } 608 else 609 { 610 _ForwardIterator __mid = __first; 611 std::advance(__mid, __elemsafter); 612 std::__uninitialized_copy_copy(__mid, __last, __pos, 613 this->_M_impl._M_finish, 614 this->_M_impl._M_finish); 615 this->_M_impl._M_finish = __new_finish; 616 std::copy(__first, __mid, __pos); 617 } 618 } 619 catch(...) 620 { 621 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 622 __new_finish._M_node + 1); 623 __throw_exception_again; 624 } 625 } 626 } 627 628 template <typename _Tp, typename _Alloc> 629 void 630 deque<_Tp,_Alloc>:: 631 _M_new_elements_at_front(size_type __new_elems) 632 { 633 size_type __new_nodes 634 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); 635 _M_reserve_map_at_front(__new_nodes); 636 size_type __i; 637 try 638 { 639 for (__i = 1; __i <= __new_nodes; ++__i) 640 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); 641 } 642 catch(...) 643 { 644 for (size_type __j = 1; __j < __i; ++__j) 645 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); 646 __throw_exception_again; 647 } 648 } 649 650 template <typename _Tp, typename _Alloc> 651 void 652 deque<_Tp,_Alloc>:: 653 _M_new_elements_at_back(size_type __new_elems) 654 { 655 size_type __new_nodes 656 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); 657 _M_reserve_map_at_back(__new_nodes); 658 size_type __i; 659 try 660 { 661 for (__i = 1; __i <= __new_nodes; ++__i) 662 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); 663 } 664 catch(...) 665 { 666 for (size_type __j = 1; __j < __i; ++__j) 667 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); 668 __throw_exception_again; 669 } 670 } 671 672 template <typename _Tp, typename _Alloc> 673 void 674 deque<_Tp,_Alloc>:: 675 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) 676 { 677 size_type __old_num_nodes 678 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; 679 size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 680 681 _Map_pointer __new_nstart; 682 if (this->_M_impl._M_map_size > 2 * __new_num_nodes) 683 { 684 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size 685 - __new_num_nodes) / 2 686 + (__add_at_front ? __nodes_to_add : 0); 687 if (__new_nstart < this->_M_impl._M_start._M_node) 688 std::copy(this->_M_impl._M_start._M_node, 689 this->_M_impl._M_finish._M_node + 1, 690 __new_nstart); 691 else 692 std::copy_backward(this->_M_impl._M_start._M_node, 693 this->_M_impl._M_finish._M_node + 1, 694 __new_nstart + __old_num_nodes); 695 } 696 else 697 { 698 size_type __new_map_size = this->_M_impl._M_map_size 699 + std::max(this->_M_impl._M_map_size, 700 __nodes_to_add) + 2; 701 702 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); 703 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 704 + (__add_at_front ? __nodes_to_add : 0); 705 std::copy(this->_M_impl._M_start._M_node, 706 this->_M_impl._M_finish._M_node + 1, 707 __new_nstart); 708 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 709 710 this->_M_impl._M_map = __new_map; 711 this->_M_impl._M_map_size = __new_map_size; 712 } 713 714 this->_M_impl._M_start._M_set_node(__new_nstart); 715 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 716 } 717 } // namespace std 718 719 #endif 720