1 // Deque implementation (out of line) -*- C++ -*- 2 3 // Copyright (C) 2001-2022 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 #include <bits/stl_algobase.h> 60 61 namespace std _GLIBCXX_VISIBILITY(default) 62 { 63 _GLIBCXX_BEGIN_NAMESPACE_VERSION 64 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 65 66 #if __cplusplus >= 201103L 67 template <typename _Tp, typename _Alloc> 68 void 69 deque<_Tp, _Alloc>:: _M_default_initialize()70 _M_default_initialize() 71 { 72 _Map_pointer __cur; 73 __try 74 { 75 for (__cur = this->_M_impl._M_start._M_node; 76 __cur < this->_M_impl._M_finish._M_node; 77 ++__cur) 78 std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(), 79 _M_get_Tp_allocator()); 80 std::__uninitialized_default_a(this->_M_impl._M_finish._M_first, 81 this->_M_impl._M_finish._M_cur, 82 _M_get_Tp_allocator()); 83 } 84 __catch(...) 85 { 86 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), 87 _M_get_Tp_allocator()); 88 __throw_exception_again; 89 } 90 } 91 #endif 92 93 template <typename _Tp, typename _Alloc> 94 deque<_Tp, _Alloc>& 95 deque<_Tp, _Alloc>:: operator =(const deque & __x)96 operator=(const deque& __x) 97 { 98 if (std::__addressof(__x) != this) 99 { 100 #if __cplusplus >= 201103L 101 if (_Alloc_traits::_S_propagate_on_copy_assign()) 102 { 103 if (!_Alloc_traits::_S_always_equal() 104 && _M_get_Tp_allocator() != __x._M_get_Tp_allocator()) 105 { 106 // Replacement allocator cannot free existing storage, 107 // so deallocate everything and take copy of __x's data. 108 _M_replace_map(__x, __x.get_allocator()); 109 std::__alloc_on_copy(_M_get_Tp_allocator(), 110 __x._M_get_Tp_allocator()); 111 return *this; 112 } 113 std::__alloc_on_copy(_M_get_Tp_allocator(), 114 __x._M_get_Tp_allocator()); 115 } 116 #endif 117 const size_type __len = size(); 118 if (__len >= __x.size()) 119 _M_erase_at_end(std::copy(__x.begin(), __x.end(), 120 this->_M_impl._M_start)); 121 else 122 { 123 const_iterator __mid = __x.begin() + difference_type(__len); 124 std::copy(__x.begin(), __mid, this->_M_impl._M_start); 125 _M_range_insert_aux(this->_M_impl._M_finish, __mid, __x.end(), 126 std::random_access_iterator_tag()); 127 } 128 } 129 return *this; 130 } 131 132 #if __cplusplus >= 201103L 133 template<typename _Tp, typename _Alloc> 134 template<typename... _Args> 135 #if __cplusplus > 201402L 136 typename deque<_Tp, _Alloc>::reference 137 #else 138 void 139 #endif 140 deque<_Tp, _Alloc>:: emplace_front(_Args &&...__args)141 emplace_front(_Args&&... __args) 142 { 143 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) 144 { 145 _Alloc_traits::construct(this->_M_impl, 146 this->_M_impl._M_start._M_cur - 1, 147 std::forward<_Args>(__args)...); 148 --this->_M_impl._M_start._M_cur; 149 } 150 else 151 _M_push_front_aux(std::forward<_Args>(__args)...); 152 #if __cplusplus > 201402L 153 return front(); 154 #endif 155 } 156 157 template<typename _Tp, typename _Alloc> 158 template<typename... _Args> 159 #if __cplusplus > 201402L 160 typename deque<_Tp, _Alloc>::reference 161 #else 162 void 163 #endif 164 deque<_Tp, _Alloc>:: emplace_back(_Args &&...__args)165 emplace_back(_Args&&... __args) 166 { 167 if (this->_M_impl._M_finish._M_cur 168 != this->_M_impl._M_finish._M_last - 1) 169 { 170 _Alloc_traits::construct(this->_M_impl, 171 this->_M_impl._M_finish._M_cur, 172 std::forward<_Args>(__args)...); 173 ++this->_M_impl._M_finish._M_cur; 174 } 175 else 176 _M_push_back_aux(std::forward<_Args>(__args)...); 177 #if __cplusplus > 201402L 178 return back(); 179 #endif 180 } 181 #endif 182 183 #if __cplusplus >= 201103L 184 template<typename _Tp, typename _Alloc> 185 template<typename... _Args> 186 typename deque<_Tp, _Alloc>::iterator 187 deque<_Tp, _Alloc>:: emplace(const_iterator __position,_Args &&...__args)188 emplace(const_iterator __position, _Args&&... __args) 189 { 190 if (__position._M_cur == this->_M_impl._M_start._M_cur) 191 { 192 emplace_front(std::forward<_Args>(__args)...); 193 return this->_M_impl._M_start; 194 } 195 else if (__position._M_cur == this->_M_impl._M_finish._M_cur) 196 { 197 emplace_back(std::forward<_Args>(__args)...); 198 iterator __tmp = this->_M_impl._M_finish; 199 --__tmp; 200 return __tmp; 201 } 202 else 203 return _M_insert_aux(__position._M_const_cast(), 204 std::forward<_Args>(__args)...); 205 } 206 #endif 207 208 template <typename _Tp, typename _Alloc> 209 typename deque<_Tp, _Alloc>::iterator 210 deque<_Tp, _Alloc>:: 211 #if __cplusplus >= 201103L insert(const_iterator __position,const value_type & __x)212 insert(const_iterator __position, const value_type& __x) 213 #else 214 insert(iterator __position, const value_type& __x) 215 #endif 216 { 217 if (__position._M_cur == this->_M_impl._M_start._M_cur) 218 { 219 push_front(__x); 220 return this->_M_impl._M_start; 221 } 222 else if (__position._M_cur == this->_M_impl._M_finish._M_cur) 223 { 224 push_back(__x); 225 iterator __tmp = this->_M_impl._M_finish; 226 --__tmp; 227 return __tmp; 228 } 229 else 230 return _M_insert_aux(__position._M_const_cast(), __x); 231 } 232 233 template <typename _Tp, typename _Alloc> 234 typename deque<_Tp, _Alloc>::iterator 235 deque<_Tp, _Alloc>:: _M_erase(iterator __position)236 _M_erase(iterator __position) 237 { 238 iterator __next = __position; 239 ++__next; 240 const difference_type __index = __position - begin(); 241 if (static_cast<size_type>(__index) < (size() >> 1)) 242 { 243 if (__position != begin()) 244 _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next); 245 pop_front(); 246 } 247 else 248 { 249 if (__next != end()) 250 _GLIBCXX_MOVE3(__next, end(), __position); 251 pop_back(); 252 } 253 return begin() + __index; 254 } 255 256 template <typename _Tp, typename _Alloc> 257 typename deque<_Tp, _Alloc>::iterator 258 deque<_Tp, _Alloc>:: _M_erase(iterator __first,iterator __last)259 _M_erase(iterator __first, iterator __last) 260 { 261 if (__first == __last) 262 return __first; 263 else if (__first == begin() && __last == end()) 264 { 265 clear(); 266 return end(); 267 } 268 else 269 { 270 const difference_type __n = __last - __first; 271 const difference_type __elems_before = __first - begin(); 272 if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2) 273 { 274 if (__first != begin()) 275 _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last); 276 _M_erase_at_begin(begin() + __n); 277 } 278 else 279 { 280 if (__last != end()) 281 _GLIBCXX_MOVE3(__last, end(), __first); 282 _M_erase_at_end(end() - __n); 283 } 284 return begin() + __elems_before; 285 } 286 } 287 288 template <typename _Tp, class _Alloc> 289 template <typename _InputIterator> 290 void 291 deque<_Tp, _Alloc>:: _M_assign_aux(_InputIterator __first,_InputIterator __last,std::input_iterator_tag)292 _M_assign_aux(_InputIterator __first, _InputIterator __last, 293 std::input_iterator_tag) 294 { 295 iterator __cur = begin(); 296 for (; __first != __last && __cur != end(); ++__cur, (void)++__first) 297 *__cur = *__first; 298 if (__first == __last) 299 _M_erase_at_end(__cur); 300 else 301 _M_range_insert_aux(end(), __first, __last, 302 std::__iterator_category(__first)); 303 } 304 305 template <typename _Tp, typename _Alloc> 306 void 307 deque<_Tp, _Alloc>:: _M_fill_insert(iterator __pos,size_type __n,const value_type & __x)308 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) 309 { 310 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 311 { 312 iterator __new_start = _M_reserve_elements_at_front(__n); 313 __try 314 { 315 std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start, 316 __x, _M_get_Tp_allocator()); 317 this->_M_impl._M_start = __new_start; 318 } 319 __catch(...) 320 { 321 _M_destroy_nodes(__new_start._M_node, 322 this->_M_impl._M_start._M_node); 323 __throw_exception_again; 324 } 325 } 326 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 327 { 328 iterator __new_finish = _M_reserve_elements_at_back(__n); 329 __try 330 { 331 std::__uninitialized_fill_a(this->_M_impl._M_finish, 332 __new_finish, __x, 333 _M_get_Tp_allocator()); 334 this->_M_impl._M_finish = __new_finish; 335 } 336 __catch(...) 337 { 338 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 339 __new_finish._M_node + 1); 340 __throw_exception_again; 341 } 342 } 343 else 344 _M_insert_aux(__pos, __n, __x); 345 } 346 347 #if __cplusplus >= 201103L 348 template <typename _Tp, typename _Alloc> 349 void 350 deque<_Tp, _Alloc>:: _M_default_append(size_type __n)351 _M_default_append(size_type __n) 352 { 353 if (__n) 354 { 355 iterator __new_finish = _M_reserve_elements_at_back(__n); 356 __try 357 { 358 std::__uninitialized_default_a(this->_M_impl._M_finish, 359 __new_finish, 360 _M_get_Tp_allocator()); 361 this->_M_impl._M_finish = __new_finish; 362 } 363 __catch(...) 364 { 365 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 366 __new_finish._M_node + 1); 367 __throw_exception_again; 368 } 369 } 370 } 371 372 template <typename _Tp, typename _Alloc> 373 bool 374 deque<_Tp, _Alloc>:: _M_shrink_to_fit()375 _M_shrink_to_fit() 376 { 377 const difference_type __front_capacity 378 = (this->_M_impl._M_start._M_cur - this->_M_impl._M_start._M_first); 379 if (__front_capacity == 0) 380 return false; 381 382 const difference_type __back_capacity 383 = (this->_M_impl._M_finish._M_last - this->_M_impl._M_finish._M_cur); 384 if (__front_capacity + __back_capacity < _S_buffer_size()) 385 return false; 386 387 return std::__shrink_to_fit_aux<deque>::_S_do_it(*this); 388 } 389 #endif 390 391 template <typename _Tp, typename _Alloc> 392 void 393 deque<_Tp, _Alloc>:: _M_fill_initialize(const value_type & __value)394 _M_fill_initialize(const value_type& __value) 395 { 396 _Map_pointer __cur; 397 __try 398 { 399 for (__cur = this->_M_impl._M_start._M_node; 400 __cur < this->_M_impl._M_finish._M_node; 401 ++__cur) 402 std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(), 403 __value, _M_get_Tp_allocator()); 404 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first, 405 this->_M_impl._M_finish._M_cur, 406 __value, _M_get_Tp_allocator()); 407 } 408 __catch(...) 409 { 410 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), 411 _M_get_Tp_allocator()); 412 __throw_exception_again; 413 } 414 } 415 416 template <typename _Tp, typename _Alloc> 417 template <typename _InputIterator> 418 void 419 deque<_Tp, _Alloc>:: _M_range_initialize(_InputIterator __first,_InputIterator __last,std::input_iterator_tag)420 _M_range_initialize(_InputIterator __first, _InputIterator __last, 421 std::input_iterator_tag) 422 { 423 this->_M_initialize_map(0); 424 __try 425 { 426 for (; __first != __last; ++__first) 427 #if __cplusplus >= 201103L 428 emplace_back(*__first); 429 #else 430 push_back(*__first); 431 #endif 432 } 433 __catch(...) 434 { 435 clear(); 436 __throw_exception_again; 437 } 438 } 439 440 template <typename _Tp, typename _Alloc> 441 template <typename _ForwardIterator> 442 void 443 deque<_Tp, _Alloc>:: _M_range_initialize(_ForwardIterator __first,_ForwardIterator __last,std::forward_iterator_tag)444 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 445 std::forward_iterator_tag) 446 { 447 const size_type __n = std::distance(__first, __last); 448 this->_M_initialize_map(_S_check_init_len(__n, _M_get_Tp_allocator())); 449 450 _Map_pointer __cur_node; 451 __try 452 { 453 for (__cur_node = this->_M_impl._M_start._M_node; 454 __cur_node < this->_M_impl._M_finish._M_node; 455 ++__cur_node) 456 { 457 if (__n < _S_buffer_size()) 458 __builtin_unreachable(); // See PR 100516 459 460 _ForwardIterator __mid = __first; 461 std::advance(__mid, _S_buffer_size()); 462 std::__uninitialized_copy_a(__first, __mid, *__cur_node, 463 _M_get_Tp_allocator()); 464 __first = __mid; 465 } 466 std::__uninitialized_copy_a(__first, __last, 467 this->_M_impl._M_finish._M_first, 468 _M_get_Tp_allocator()); 469 } 470 __catch(...) 471 { 472 std::_Destroy(this->_M_impl._M_start, 473 iterator(*__cur_node, __cur_node), 474 _M_get_Tp_allocator()); 475 __throw_exception_again; 476 } 477 } 478 479 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. 480 template<typename _Tp, typename _Alloc> 481 #if __cplusplus >= 201103L 482 template<typename... _Args> 483 void 484 deque<_Tp, _Alloc>:: _M_push_back_aux(_Args &&...__args)485 _M_push_back_aux(_Args&&... __args) 486 #else 487 void 488 deque<_Tp, _Alloc>:: 489 _M_push_back_aux(const value_type& __t) 490 #endif 491 { 492 if (size() == max_size()) 493 __throw_length_error( 494 __N("cannot create std::deque larger than max_size()")); 495 496 _M_reserve_map_at_back(); 497 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); 498 __try 499 { 500 #if __cplusplus >= 201103L 501 _Alloc_traits::construct(this->_M_impl, 502 this->_M_impl._M_finish._M_cur, 503 std::forward<_Args>(__args)...); 504 #else 505 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t); 506 #endif 507 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node 508 + 1); 509 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; 510 } 511 __catch(...) 512 { 513 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); 514 __throw_exception_again; 515 } 516 } 517 518 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. 519 template<typename _Tp, typename _Alloc> 520 #if __cplusplus >= 201103L 521 template<typename... _Args> 522 void 523 deque<_Tp, _Alloc>:: _M_push_front_aux(_Args &&...__args)524 _M_push_front_aux(_Args&&... __args) 525 #else 526 void 527 deque<_Tp, _Alloc>:: 528 _M_push_front_aux(const value_type& __t) 529 #endif 530 { 531 if (size() == max_size()) 532 __throw_length_error( 533 __N("cannot create std::deque larger than max_size()")); 534 535 _M_reserve_map_at_front(); 536 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); 537 __try 538 { 539 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node 540 - 1); 541 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; 542 #if __cplusplus >= 201103L 543 _Alloc_traits::construct(this->_M_impl, 544 this->_M_impl._M_start._M_cur, 545 std::forward<_Args>(__args)...); 546 #else 547 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t); 548 #endif 549 } 550 __catch(...) 551 { 552 ++this->_M_impl._M_start; 553 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); 554 __throw_exception_again; 555 } 556 } 557 558 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. 559 template <typename _Tp, typename _Alloc> 560 void deque<_Tp, _Alloc>:: _M_pop_back_aux()561 _M_pop_back_aux() 562 { 563 _M_deallocate_node(this->_M_impl._M_finish._M_first); 564 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); 565 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; 566 _Alloc_traits::destroy(_M_get_Tp_allocator(), 567 this->_M_impl._M_finish._M_cur); 568 } 569 570 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. 571 // Note that if the deque has at least one element (a precondition for this 572 // member function), and if 573 // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, 574 // then the deque must have at least two nodes. 575 template <typename _Tp, typename _Alloc> 576 void deque<_Tp, _Alloc>:: _M_pop_front_aux()577 _M_pop_front_aux() 578 { 579 _Alloc_traits::destroy(_M_get_Tp_allocator(), 580 this->_M_impl._M_start._M_cur); 581 _M_deallocate_node(this->_M_impl._M_start._M_first); 582 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); 583 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; 584 } 585 586 template <typename _Tp, typename _Alloc> 587 template <typename _InputIterator> 588 void 589 deque<_Tp, _Alloc>:: _M_range_insert_aux(iterator __pos,_InputIterator __first,_InputIterator __last,std::input_iterator_tag)590 _M_range_insert_aux(iterator __pos, 591 _InputIterator __first, _InputIterator __last, 592 std::input_iterator_tag) 593 { std::copy(__first, __last, std::inserter(*this, __pos)); } 594 595 template <typename _Tp, typename _Alloc> 596 template <typename _ForwardIterator> 597 void 598 deque<_Tp, _Alloc>:: _M_range_insert_aux(iterator __pos,_ForwardIterator __first,_ForwardIterator __last,std::forward_iterator_tag)599 _M_range_insert_aux(iterator __pos, 600 _ForwardIterator __first, _ForwardIterator __last, 601 std::forward_iterator_tag) 602 { 603 const size_type __n = std::distance(__first, __last); 604 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 605 { 606 iterator __new_start = _M_reserve_elements_at_front(__n); 607 __try 608 { 609 std::__uninitialized_copy_a(__first, __last, __new_start, 610 _M_get_Tp_allocator()); 611 this->_M_impl._M_start = __new_start; 612 } 613 __catch(...) 614 { 615 _M_destroy_nodes(__new_start._M_node, 616 this->_M_impl._M_start._M_node); 617 __throw_exception_again; 618 } 619 } 620 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 621 { 622 iterator __new_finish = _M_reserve_elements_at_back(__n); 623 __try 624 { 625 std::__uninitialized_copy_a(__first, __last, 626 this->_M_impl._M_finish, 627 _M_get_Tp_allocator()); 628 this->_M_impl._M_finish = __new_finish; 629 } 630 __catch(...) 631 { 632 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 633 __new_finish._M_node + 1); 634 __throw_exception_again; 635 } 636 } 637 else 638 _M_insert_aux(__pos, __first, __last, __n); 639 } 640 641 template<typename _Tp, typename _Alloc> 642 #if __cplusplus >= 201103L 643 template<typename... _Args> 644 typename deque<_Tp, _Alloc>::iterator 645 deque<_Tp, _Alloc>:: _M_insert_aux(iterator __pos,_Args &&...__args)646 _M_insert_aux(iterator __pos, _Args&&... __args) 647 { 648 value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy 649 #else 650 typename deque<_Tp, _Alloc>::iterator 651 deque<_Tp, _Alloc>:: 652 _M_insert_aux(iterator __pos, const value_type& __x) 653 { 654 value_type __x_copy = __x; // XXX copy 655 #endif 656 difference_type __index = __pos - this->_M_impl._M_start; 657 if (static_cast<size_type>(__index) < size() / 2) 658 { 659 push_front(_GLIBCXX_MOVE(front())); 660 iterator __front1 = this->_M_impl._M_start; 661 ++__front1; 662 iterator __front2 = __front1; 663 ++__front2; 664 __pos = this->_M_impl._M_start + __index; 665 iterator __pos1 = __pos; 666 ++__pos1; 667 _GLIBCXX_MOVE3(__front2, __pos1, __front1); 668 } 669 else 670 { 671 push_back(_GLIBCXX_MOVE(back())); 672 iterator __back1 = this->_M_impl._M_finish; 673 --__back1; 674 iterator __back2 = __back1; 675 --__back2; 676 __pos = this->_M_impl._M_start + __index; 677 _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1); 678 } 679 *__pos = _GLIBCXX_MOVE(__x_copy); 680 return __pos; 681 } 682 683 template <typename _Tp, typename _Alloc> 684 void 685 deque<_Tp, _Alloc>:: 686 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) 687 { 688 const difference_type __elems_before = __pos - this->_M_impl._M_start; 689 const size_type __length = this->size(); 690 value_type __x_copy = __x; 691 if (__elems_before < difference_type(__length / 2)) 692 { 693 iterator __new_start = _M_reserve_elements_at_front(__n); 694 iterator __old_start = this->_M_impl._M_start; 695 __pos = this->_M_impl._M_start + __elems_before; 696 __try 697 { 698 if (__elems_before >= difference_type(__n)) 699 { 700 iterator __start_n = (this->_M_impl._M_start 701 + difference_type(__n)); 702 std::__uninitialized_move_a(this->_M_impl._M_start, 703 __start_n, __new_start, 704 _M_get_Tp_allocator()); 705 this->_M_impl._M_start = __new_start; 706 _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 707 std::fill(__pos - difference_type(__n), __pos, __x_copy); 708 } 709 else 710 { 711 std::__uninitialized_move_fill(this->_M_impl._M_start, 712 __pos, __new_start, 713 this->_M_impl._M_start, 714 __x_copy, 715 _M_get_Tp_allocator()); 716 this->_M_impl._M_start = __new_start; 717 std::fill(__old_start, __pos, __x_copy); 718 } 719 } 720 __catch(...) 721 { 722 _M_destroy_nodes(__new_start._M_node, 723 this->_M_impl._M_start._M_node); 724 __throw_exception_again; 725 } 726 } 727 else 728 { 729 iterator __new_finish = _M_reserve_elements_at_back(__n); 730 iterator __old_finish = this->_M_impl._M_finish; 731 const difference_type __elems_after = 732 difference_type(__length) - __elems_before; 733 __pos = this->_M_impl._M_finish - __elems_after; 734 __try 735 { 736 if (__elems_after > difference_type(__n)) 737 { 738 iterator __finish_n = (this->_M_impl._M_finish 739 - difference_type(__n)); 740 std::__uninitialized_move_a(__finish_n, 741 this->_M_impl._M_finish, 742 this->_M_impl._M_finish, 743 _M_get_Tp_allocator()); 744 this->_M_impl._M_finish = __new_finish; 745 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 746 std::fill(__pos, __pos + difference_type(__n), __x_copy); 747 } 748 else 749 { 750 std::__uninitialized_fill_move(this->_M_impl._M_finish, 751 __pos + difference_type(__n), 752 __x_copy, __pos, 753 this->_M_impl._M_finish, 754 _M_get_Tp_allocator()); 755 this->_M_impl._M_finish = __new_finish; 756 std::fill(__pos, __old_finish, __x_copy); 757 } 758 } 759 __catch(...) 760 { 761 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 762 __new_finish._M_node + 1); 763 __throw_exception_again; 764 } 765 } 766 } 767 768 template <typename _Tp, typename _Alloc> 769 template <typename _ForwardIterator> 770 void 771 deque<_Tp, _Alloc>:: 772 _M_insert_aux(iterator __pos, 773 _ForwardIterator __first, _ForwardIterator __last, 774 size_type __n) 775 { 776 const difference_type __elemsbefore = __pos - this->_M_impl._M_start; 777 const size_type __length = size(); 778 if (static_cast<size_type>(__elemsbefore) < __length / 2) 779 { 780 iterator __new_start = _M_reserve_elements_at_front(__n); 781 iterator __old_start = this->_M_impl._M_start; 782 __pos = this->_M_impl._M_start + __elemsbefore; 783 __try 784 { 785 if (__elemsbefore >= difference_type(__n)) 786 { 787 iterator __start_n = (this->_M_impl._M_start 788 + difference_type(__n)); 789 std::__uninitialized_move_a(this->_M_impl._M_start, 790 __start_n, __new_start, 791 _M_get_Tp_allocator()); 792 this->_M_impl._M_start = __new_start; 793 _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 794 std::copy(__first, __last, __pos - difference_type(__n)); 795 } 796 else 797 { 798 _ForwardIterator __mid = __first; 799 std::advance(__mid, difference_type(__n) - __elemsbefore); 800 std::__uninitialized_move_copy(this->_M_impl._M_start, 801 __pos, __first, __mid, 802 __new_start, 803 _M_get_Tp_allocator()); 804 this->_M_impl._M_start = __new_start; 805 std::copy(__mid, __last, __old_start); 806 } 807 } 808 __catch(...) 809 { 810 _M_destroy_nodes(__new_start._M_node, 811 this->_M_impl._M_start._M_node); 812 __throw_exception_again; 813 } 814 } 815 else 816 { 817 iterator __new_finish = _M_reserve_elements_at_back(__n); 818 iterator __old_finish = this->_M_impl._M_finish; 819 const difference_type __elemsafter = 820 difference_type(__length) - __elemsbefore; 821 __pos = this->_M_impl._M_finish - __elemsafter; 822 __try 823 { 824 if (__elemsafter > difference_type(__n)) 825 { 826 iterator __finish_n = (this->_M_impl._M_finish 827 - difference_type(__n)); 828 std::__uninitialized_move_a(__finish_n, 829 this->_M_impl._M_finish, 830 this->_M_impl._M_finish, 831 _M_get_Tp_allocator()); 832 this->_M_impl._M_finish = __new_finish; 833 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 834 std::copy(__first, __last, __pos); 835 } 836 else 837 { 838 _ForwardIterator __mid = __first; 839 std::advance(__mid, __elemsafter); 840 std::__uninitialized_copy_move(__mid, __last, __pos, 841 this->_M_impl._M_finish, 842 this->_M_impl._M_finish, 843 _M_get_Tp_allocator()); 844 this->_M_impl._M_finish = __new_finish; 845 std::copy(__first, __mid, __pos); 846 } 847 } 848 __catch(...) 849 { 850 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 851 __new_finish._M_node + 1); 852 __throw_exception_again; 853 } 854 } 855 } 856 857 template<typename _Tp, typename _Alloc> 858 void 859 deque<_Tp, _Alloc>:: 860 _M_destroy_data_aux(iterator __first, iterator __last) 861 { 862 for (_Map_pointer __node = __first._M_node + 1; 863 __node < __last._M_node; ++__node) 864 std::_Destroy(*__node, *__node + _S_buffer_size(), 865 _M_get_Tp_allocator()); 866 867 if (__first._M_node != __last._M_node) 868 { 869 std::_Destroy(__first._M_cur, __first._M_last, 870 _M_get_Tp_allocator()); 871 std::_Destroy(__last._M_first, __last._M_cur, 872 _M_get_Tp_allocator()); 873 } 874 else 875 std::_Destroy(__first._M_cur, __last._M_cur, 876 _M_get_Tp_allocator()); 877 } 878 879 template <typename _Tp, typename _Alloc> 880 void 881 deque<_Tp, _Alloc>:: 882 _M_new_elements_at_front(size_type __new_elems) 883 { 884 if (this->max_size() - this->size() < __new_elems) 885 __throw_length_error(__N("deque::_M_new_elements_at_front")); 886 887 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 888 / _S_buffer_size()); 889 _M_reserve_map_at_front(__new_nodes); 890 size_type __i; 891 __try 892 { 893 for (__i = 1; __i <= __new_nodes; ++__i) 894 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); 895 } 896 __catch(...) 897 { 898 for (size_type __j = 1; __j < __i; ++__j) 899 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); 900 __throw_exception_again; 901 } 902 } 903 904 template <typename _Tp, typename _Alloc> 905 void 906 deque<_Tp, _Alloc>:: 907 _M_new_elements_at_back(size_type __new_elems) 908 { 909 if (this->max_size() - this->size() < __new_elems) 910 __throw_length_error(__N("deque::_M_new_elements_at_back")); 911 912 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 913 / _S_buffer_size()); 914 _M_reserve_map_at_back(__new_nodes); 915 size_type __i; 916 __try 917 { 918 for (__i = 1; __i <= __new_nodes; ++__i) 919 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); 920 } 921 __catch(...) 922 { 923 for (size_type __j = 1; __j < __i; ++__j) 924 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); 925 __throw_exception_again; 926 } 927 } 928 929 template <typename _Tp, typename _Alloc> 930 void 931 deque<_Tp, _Alloc>:: 932 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) 933 { 934 const size_type __old_num_nodes 935 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; 936 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 937 938 _Map_pointer __new_nstart; 939 if (this->_M_impl._M_map_size > 2 * __new_num_nodes) 940 { 941 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size 942 - __new_num_nodes) / 2 943 + (__add_at_front ? __nodes_to_add : 0); 944 if (__new_nstart < this->_M_impl._M_start._M_node) 945 std::copy(this->_M_impl._M_start._M_node, 946 this->_M_impl._M_finish._M_node + 1, 947 __new_nstart); 948 else 949 std::copy_backward(this->_M_impl._M_start._M_node, 950 this->_M_impl._M_finish._M_node + 1, 951 __new_nstart + __old_num_nodes); 952 } 953 else 954 { 955 size_type __new_map_size = this->_M_impl._M_map_size 956 + std::max(this->_M_impl._M_map_size, 957 __nodes_to_add) + 2; 958 959 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); 960 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 961 + (__add_at_front ? __nodes_to_add : 0); 962 std::copy(this->_M_impl._M_start._M_node, 963 this->_M_impl._M_finish._M_node + 1, 964 __new_nstart); 965 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 966 967 this->_M_impl._M_map = __new_map; 968 this->_M_impl._M_map_size = __new_map_size; 969 } 970 971 this->_M_impl._M_start._M_set_node(__new_nstart); 972 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 973 } 974 975 _GLIBCXX_END_NAMESPACE_CONTAINER 976 977 // Overload for deque::iterators, exploiting the "segmented-iterator 978 // optimization". 979 template<typename _Tp, typename _VTp> 980 void 981 __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __first, 982 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last, 983 const _VTp& __value) 984 { 985 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; 986 if (__first._M_node != __last._M_node) 987 { 988 std::__fill_a1(__first._M_cur, __first._M_last, __value); 989 990 for (typename _Iter::_Map_pointer __node = __first._M_node + 1; 991 __node < __last._M_node; ++__node) 992 std::__fill_a1(*__node, *__node + _Iter::_S_buffer_size(), __value); 993 994 std::__fill_a1(__last._M_first, __last._M_cur, __value); 995 } 996 else 997 std::__fill_a1(__first._M_cur, __last._M_cur, __value); 998 } 999 1000 template<bool _IsMove, 1001 typename _Tp, typename _Ref, typename _Ptr, typename _OI> 1002 _OI 1003 __copy_move_dit(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, 1004 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, 1005 _OI __result) 1006 { 1007 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; 1008 if (__first._M_node != __last._M_node) 1009 { 1010 __result 1011 = std::__copy_move_a1<_IsMove>(__first._M_cur, __first._M_last, 1012 __result); 1013 1014 for (typename _Iter::_Map_pointer __node = __first._M_node + 1; 1015 __node != __last._M_node; ++__node) 1016 __result 1017 = std::__copy_move_a1<_IsMove>(*__node, 1018 *__node + _Iter::_S_buffer_size(), 1019 __result); 1020 1021 return std::__copy_move_a1<_IsMove>(__last._M_first, __last._M_cur, 1022 __result); 1023 } 1024 1025 return std::__copy_move_a1<_IsMove>(__first._M_cur, __last._M_cur, 1026 __result); 1027 } 1028 1029 template<bool _IsMove, 1030 typename _Tp, typename _Ref, typename _Ptr, typename _OI> 1031 _OI 1032 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, 1033 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, 1034 _OI __result) 1035 { return __copy_move_dit<_IsMove>(__first, __last, __result); } 1036 1037 template<bool _IsMove, 1038 typename _ITp, typename _IRef, typename _IPtr, typename _OTp> 1039 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> 1040 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first, 1041 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last, 1042 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result) 1043 { return __copy_move_dit<_IsMove>(__first, __last, __result); } 1044 1045 template<bool _IsMove, typename _II, typename _Tp> 1046 typename __gnu_cxx::__enable_if< 1047 __is_random_access_iter<_II>::__value, 1048 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type 1049 __copy_move_a1(_II __first, _II __last, 1050 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result) 1051 { 1052 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; 1053 typedef typename _Iter::difference_type difference_type; 1054 1055 difference_type __len = __last - __first; 1056 while (__len > 0) 1057 { 1058 const difference_type __clen 1059 = std::min(__len, __result._M_last - __result._M_cur); 1060 std::__copy_move_a1<_IsMove>(__first, __first + __clen, 1061 __result._M_cur); 1062 1063 __first += __clen; 1064 __result += __clen; 1065 __len -= __clen; 1066 } 1067 1068 return __result; 1069 } 1070 1071 template<bool _IsMove, typename _CharT> 1072 typename __gnu_cxx::__enable_if< 1073 __is_char<_CharT>::__value, 1074 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type 1075 __copy_move_a2( 1076 istreambuf_iterator<_CharT, char_traits<_CharT> > __first, 1077 istreambuf_iterator<_CharT, char_traits<_CharT> > __last, 1078 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result) 1079 { 1080 if (__first == __last) 1081 return __result; 1082 1083 for (;;) 1084 { 1085 const std::ptrdiff_t __len = __result._M_last - __result._M_cur; 1086 const std::ptrdiff_t __nb 1087 = std::__copy_n_a(__first, __len, __result._M_cur, false) 1088 - __result._M_cur; 1089 __result += __nb; 1090 1091 if (__nb != __len) 1092 break; 1093 } 1094 1095 return __result; 1096 } 1097 1098 template<typename _CharT, typename _Size> 1099 typename __gnu_cxx::__enable_if< 1100 __is_char<_CharT>::__value, 1101 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type 1102 __copy_n_a( 1103 istreambuf_iterator<_CharT, char_traits<_CharT> > __it, _Size __size, 1104 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result, 1105 bool __strict) 1106 { 1107 if (__size == 0) 1108 return __result; 1109 1110 do 1111 { 1112 const _Size __len 1113 = std::min<_Size>(__result._M_last - __result._M_cur, __size); 1114 std::__copy_n_a(__it, __len, __result._M_cur, __strict); 1115 __result += __len; 1116 __size -= __len; 1117 } 1118 while (__size != 0); 1119 return __result; 1120 } 1121 1122 template<bool _IsMove, 1123 typename _Tp, typename _Ref, typename _Ptr, typename _OI> 1124 _OI 1125 __copy_move_backward_dit( 1126 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, 1127 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, 1128 _OI __result) 1129 { 1130 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; 1131 if (__first._M_node != __last._M_node) 1132 { 1133 __result = std::__copy_move_backward_a1<_IsMove>( 1134 __last._M_first, __last._M_cur, __result); 1135 1136 for (typename _Iter::_Map_pointer __node = __last._M_node - 1; 1137 __node != __first._M_node; --__node) 1138 __result = std::__copy_move_backward_a1<_IsMove>( 1139 *__node, *__node + _Iter::_S_buffer_size(), __result); 1140 1141 return std::__copy_move_backward_a1<_IsMove>( 1142 __first._M_cur, __first._M_last, __result); 1143 } 1144 1145 return std::__copy_move_backward_a1<_IsMove>( 1146 __first._M_cur, __last._M_cur, __result); 1147 } 1148 1149 template<bool _IsMove, 1150 typename _Tp, typename _Ref, typename _Ptr, typename _OI> 1151 _OI 1152 __copy_move_backward_a1( 1153 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, 1154 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, 1155 _OI __result) 1156 { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); } 1157 1158 template<bool _IsMove, 1159 typename _ITp, typename _IRef, typename _IPtr, typename _OTp> 1160 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> 1161 __copy_move_backward_a1( 1162 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first, 1163 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last, 1164 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result) 1165 { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); } 1166 1167 template<bool _IsMove, typename _II, typename _Tp> 1168 typename __gnu_cxx::__enable_if< 1169 __is_random_access_iter<_II>::__value, 1170 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type 1171 __copy_move_backward_a1(_II __first, _II __last, 1172 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result) 1173 { 1174 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; 1175 typedef typename _Iter::difference_type difference_type; 1176 1177 difference_type __len = __last - __first; 1178 while (__len > 0) 1179 { 1180 difference_type __rlen = __result._M_cur - __result._M_first; 1181 _Tp* __rend = __result._M_cur; 1182 if (!__rlen) 1183 { 1184 __rlen = _Iter::_S_buffer_size(); 1185 __rend = *(__result._M_node - 1) + __rlen; 1186 } 1187 1188 const difference_type __clen = std::min(__len, __rlen); 1189 std::__copy_move_backward_a1<_IsMove>(__last - __clen, __last, __rend); 1190 1191 __last -= __clen; 1192 __result -= __clen; 1193 __len -= __clen; 1194 } 1195 1196 return __result; 1197 } 1198 1199 template<typename _Tp, typename _Ref, typename _Ptr, typename _II> 1200 bool 1201 __equal_dit( 1202 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1, 1203 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1, 1204 _II __first2) 1205 { 1206 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; 1207 if (__first1._M_node != __last1._M_node) 1208 { 1209 if (!std::__equal_aux1(__first1._M_cur, __first1._M_last, __first2)) 1210 return false; 1211 1212 __first2 += __first1._M_last - __first1._M_cur; 1213 for (typename _Iter::_Map_pointer __node = __first1._M_node + 1; 1214 __node != __last1._M_node; 1215 __first2 += _Iter::_S_buffer_size(), ++__node) 1216 if (!std::__equal_aux1(*__node, *__node + _Iter::_S_buffer_size(), 1217 __first2)) 1218 return false; 1219 1220 return std::__equal_aux1(__last1._M_first, __last1._M_cur, __first2); 1221 } 1222 1223 return std::__equal_aux1(__first1._M_cur, __last1._M_cur, __first2); 1224 } 1225 1226 template<typename _Tp, typename _Ref, typename _Ptr, typename _II> 1227 typename __gnu_cxx::__enable_if< 1228 __is_random_access_iter<_II>::__value, bool>::__type 1229 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first1, 1230 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last1, 1231 _II __first2) 1232 { return std::__equal_dit(__first1, __last1, __first2); } 1233 1234 template<typename _Tp1, typename _Ref1, typename _Ptr1, 1235 typename _Tp2, typename _Ref2, typename _Ptr2> 1236 bool 1237 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1, 1238 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1, 1239 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2) 1240 { return std::__equal_dit(__first1, __last1, __first2); } 1241 1242 template<typename _II, typename _Tp, typename _Ref, typename _Ptr> 1243 typename __gnu_cxx::__enable_if< 1244 __is_random_access_iter<_II>::__value, bool>::__type 1245 __equal_aux1(_II __first1, _II __last1, 1246 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first2) 1247 { 1248 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; 1249 typedef typename _Iter::difference_type difference_type; 1250 1251 difference_type __len = __last1 - __first1; 1252 while (__len > 0) 1253 { 1254 const difference_type __clen 1255 = std::min(__len, __first2._M_last - __first2._M_cur); 1256 if (!std::__equal_aux1(__first1, __first1 + __clen, __first2._M_cur)) 1257 return false; 1258 1259 __first1 += __clen; 1260 __len -= __clen; 1261 __first2 += __clen; 1262 } 1263 1264 return true; 1265 } 1266 1267 template<typename _Tp1, typename _Ref, typename _Ptr, typename _Tp2> 1268 int 1269 __lex_cmp_dit( 1270 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __first1, 1271 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __last1, 1272 const _Tp2* __first2, const _Tp2* __last2) 1273 { 1274 const bool __simple = 1275 (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value 1276 && __is_pointer<_Ptr>::__value 1277 #if __cplusplus > 201703L && __cpp_lib_concepts 1278 // For C++20 iterator_traits<volatile T*>::value_type is non-volatile 1279 // so __is_byte<T> could be true, but we can't use memcmp with 1280 // volatile data. 1281 && !is_volatile_v<_Tp1> 1282 && !is_volatile_v<_Tp2> 1283 #endif 1284 ); 1285 typedef std::__lexicographical_compare<__simple> _Lc; 1286 1287 while (__first1._M_node != __last1._M_node) 1288 { 1289 const ptrdiff_t __len1 = __first1._M_last - __first1._M_cur; 1290 const ptrdiff_t __len2 = __last2 - __first2; 1291 const ptrdiff_t __len = std::min(__len1, __len2); 1292 // if __len1 > __len2 this will return a positive value: 1293 if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_last, 1294 __first2, __first2 + __len)) 1295 return __ret; 1296 1297 __first1 += __len; 1298 __first2 += __len; 1299 } 1300 return _Lc::__3way(__first1._M_cur, __last1._M_cur, 1301 __first2, __last2); 1302 } 1303 1304 template<typename _Tp1, typename _Ref1, typename _Ptr1, 1305 typename _Tp2> 1306 inline bool 1307 __lexicographical_compare_aux1( 1308 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1, 1309 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1, 1310 _Tp2* __first2, _Tp2* __last2) 1311 { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2) < 0; } 1312 1313 template<typename _Tp1, 1314 typename _Tp2, typename _Ref2, typename _Ptr2> 1315 inline bool 1316 __lexicographical_compare_aux1(_Tp1* __first1, _Tp1* __last1, 1317 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2, 1318 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2) 1319 { return std::__lex_cmp_dit(__first2, __last2, __first1, __last1) > 0; } 1320 1321 template<typename _Tp1, typename _Ref1, typename _Ptr1, 1322 typename _Tp2, typename _Ref2, typename _Ptr2> 1323 inline bool 1324 __lexicographical_compare_aux1( 1325 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1, 1326 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1, 1327 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2, 1328 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2) 1329 { 1330 const bool __simple = 1331 (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value 1332 && __is_pointer<_Ptr1>::__value 1333 && __is_pointer<_Ptr2>::__value 1334 #if __cplusplus > 201703L && __cpp_lib_concepts 1335 // For C++20 iterator_traits<volatile T*>::value_type is non-volatile 1336 // so __is_byte<T> could be true, but we can't use memcmp with 1337 // volatile data. 1338 && !is_volatile_v<_Tp1> 1339 && !is_volatile_v<_Tp2> 1340 #endif 1341 ); 1342 typedef std::__lexicographical_compare<__simple> _Lc; 1343 1344 while (__first1 != __last1) 1345 { 1346 const ptrdiff_t __len2 = __first2._M_node == __last2._M_node 1347 ? __last2._M_cur - __first2._M_cur 1348 : __first2._M_last - __first2._M_cur; 1349 if (__len2 == 0) 1350 return false; 1351 const ptrdiff_t __len1 = __first1._M_node == __last1._M_node 1352 ? __last1._M_cur - __first1._M_cur 1353 : __first1._M_last - __first1._M_cur; 1354 const ptrdiff_t __len = std::min(__len1, __len2); 1355 if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_cur + __len, 1356 __first2._M_cur, __first2._M_cur + __len)) 1357 return __ret < 0; 1358 1359 __first1 += __len; 1360 __first2 += __len; 1361 } 1362 1363 return __last2 != __first2; 1364 } 1365 1366 _GLIBCXX_END_NAMESPACE_VERSION 1367 } // namespace std 1368 1369 #endif 1370