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