1 // Deque implementation (out of line) -*- C++ -*- 2 3 // Copyright (C) 2001-2021 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 (&__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 _ForwardIterator __mid = __first; 458 std::advance(__mid, _S_buffer_size()); 459 std::__uninitialized_copy_a(__first, __mid, *__cur_node, 460 _M_get_Tp_allocator()); 461 __first = __mid; 462 } 463 std::__uninitialized_copy_a(__first, __last, 464 this->_M_impl._M_finish._M_first, 465 _M_get_Tp_allocator()); 466 } 467 __catch(...) 468 { 469 std::_Destroy(this->_M_impl._M_start, 470 iterator(*__cur_node, __cur_node), 471 _M_get_Tp_allocator()); 472 __throw_exception_again; 473 } 474 } 475 476 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. 477 template<typename _Tp, typename _Alloc> 478 #if __cplusplus >= 201103L 479 template<typename... _Args> 480 void 481 deque<_Tp, _Alloc>:: _M_push_back_aux(_Args &&...__args)482 _M_push_back_aux(_Args&&... __args) 483 #else 484 void 485 deque<_Tp, _Alloc>:: 486 _M_push_back_aux(const value_type& __t) 487 #endif 488 { 489 if (size() == max_size()) 490 __throw_length_error( 491 __N("cannot create std::deque larger than max_size()")); 492 493 _M_reserve_map_at_back(); 494 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); 495 __try 496 { 497 #if __cplusplus >= 201103L 498 _Alloc_traits::construct(this->_M_impl, 499 this->_M_impl._M_finish._M_cur, 500 std::forward<_Args>(__args)...); 501 #else 502 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t); 503 #endif 504 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node 505 + 1); 506 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; 507 } 508 __catch(...) 509 { 510 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); 511 __throw_exception_again; 512 } 513 } 514 515 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. 516 template<typename _Tp, typename _Alloc> 517 #if __cplusplus >= 201103L 518 template<typename... _Args> 519 void 520 deque<_Tp, _Alloc>:: _M_push_front_aux(_Args &&...__args)521 _M_push_front_aux(_Args&&... __args) 522 #else 523 void 524 deque<_Tp, _Alloc>:: 525 _M_push_front_aux(const value_type& __t) 526 #endif 527 { 528 if (size() == max_size()) 529 __throw_length_error( 530 __N("cannot create std::deque larger than max_size()")); 531 532 _M_reserve_map_at_front(); 533 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); 534 __try 535 { 536 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node 537 - 1); 538 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; 539 #if __cplusplus >= 201103L 540 _Alloc_traits::construct(this->_M_impl, 541 this->_M_impl._M_start._M_cur, 542 std::forward<_Args>(__args)...); 543 #else 544 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t); 545 #endif 546 } 547 __catch(...) 548 { 549 ++this->_M_impl._M_start; 550 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); 551 __throw_exception_again; 552 } 553 } 554 555 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. 556 template <typename _Tp, typename _Alloc> 557 void deque<_Tp, _Alloc>:: _M_pop_back_aux()558 _M_pop_back_aux() 559 { 560 _M_deallocate_node(this->_M_impl._M_finish._M_first); 561 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); 562 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; 563 _Alloc_traits::destroy(_M_get_Tp_allocator(), 564 this->_M_impl._M_finish._M_cur); 565 } 566 567 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. 568 // Note that if the deque has at least one element (a precondition for this 569 // member function), and if 570 // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, 571 // then the deque must have at least two nodes. 572 template <typename _Tp, typename _Alloc> 573 void deque<_Tp, _Alloc>:: _M_pop_front_aux()574 _M_pop_front_aux() 575 { 576 _Alloc_traits::destroy(_M_get_Tp_allocator(), 577 this->_M_impl._M_start._M_cur); 578 _M_deallocate_node(this->_M_impl._M_start._M_first); 579 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); 580 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; 581 } 582 583 template <typename _Tp, typename _Alloc> 584 template <typename _InputIterator> 585 void 586 deque<_Tp, _Alloc>:: _M_range_insert_aux(iterator __pos,_InputIterator __first,_InputIterator __last,std::input_iterator_tag)587 _M_range_insert_aux(iterator __pos, 588 _InputIterator __first, _InputIterator __last, 589 std::input_iterator_tag) 590 { std::copy(__first, __last, std::inserter(*this, __pos)); } 591 592 template <typename _Tp, typename _Alloc> 593 template <typename _ForwardIterator> 594 void 595 deque<_Tp, _Alloc>:: _M_range_insert_aux(iterator __pos,_ForwardIterator __first,_ForwardIterator __last,std::forward_iterator_tag)596 _M_range_insert_aux(iterator __pos, 597 _ForwardIterator __first, _ForwardIterator __last, 598 std::forward_iterator_tag) 599 { 600 const size_type __n = std::distance(__first, __last); 601 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 602 { 603 iterator __new_start = _M_reserve_elements_at_front(__n); 604 __try 605 { 606 std::__uninitialized_copy_a(__first, __last, __new_start, 607 _M_get_Tp_allocator()); 608 this->_M_impl._M_start = __new_start; 609 } 610 __catch(...) 611 { 612 _M_destroy_nodes(__new_start._M_node, 613 this->_M_impl._M_start._M_node); 614 __throw_exception_again; 615 } 616 } 617 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 618 { 619 iterator __new_finish = _M_reserve_elements_at_back(__n); 620 __try 621 { 622 std::__uninitialized_copy_a(__first, __last, 623 this->_M_impl._M_finish, 624 _M_get_Tp_allocator()); 625 this->_M_impl._M_finish = __new_finish; 626 } 627 __catch(...) 628 { 629 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 630 __new_finish._M_node + 1); 631 __throw_exception_again; 632 } 633 } 634 else 635 _M_insert_aux(__pos, __first, __last, __n); 636 } 637 638 template<typename _Tp, typename _Alloc> 639 #if __cplusplus >= 201103L 640 template<typename... _Args> 641 typename deque<_Tp, _Alloc>::iterator 642 deque<_Tp, _Alloc>:: _M_insert_aux(iterator __pos,_Args &&...__args)643 _M_insert_aux(iterator __pos, _Args&&... __args) 644 { 645 value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy 646 #else 647 typename deque<_Tp, _Alloc>::iterator 648 deque<_Tp, _Alloc>:: 649 _M_insert_aux(iterator __pos, const value_type& __x) 650 { 651 value_type __x_copy = __x; // XXX copy 652 #endif 653 difference_type __index = __pos - this->_M_impl._M_start; 654 if (static_cast<size_type>(__index) < size() / 2) 655 { 656 push_front(_GLIBCXX_MOVE(front())); 657 iterator __front1 = this->_M_impl._M_start; 658 ++__front1; 659 iterator __front2 = __front1; 660 ++__front2; 661 __pos = this->_M_impl._M_start + __index; 662 iterator __pos1 = __pos; 663 ++__pos1; 664 _GLIBCXX_MOVE3(__front2, __pos1, __front1); 665 } 666 else 667 { 668 push_back(_GLIBCXX_MOVE(back())); 669 iterator __back1 = this->_M_impl._M_finish; 670 --__back1; 671 iterator __back2 = __back1; 672 --__back2; 673 __pos = this->_M_impl._M_start + __index; 674 _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1); 675 } 676 *__pos = _GLIBCXX_MOVE(__x_copy); 677 return __pos; 678 } 679 680 template <typename _Tp, typename _Alloc> 681 void 682 deque<_Tp, _Alloc>:: 683 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) 684 { 685 const difference_type __elems_before = __pos - this->_M_impl._M_start; 686 const size_type __length = this->size(); 687 value_type __x_copy = __x; 688 if (__elems_before < difference_type(__length / 2)) 689 { 690 iterator __new_start = _M_reserve_elements_at_front(__n); 691 iterator __old_start = this->_M_impl._M_start; 692 __pos = this->_M_impl._M_start + __elems_before; 693 __try 694 { 695 if (__elems_before >= difference_type(__n)) 696 { 697 iterator __start_n = (this->_M_impl._M_start 698 + difference_type(__n)); 699 std::__uninitialized_move_a(this->_M_impl._M_start, 700 __start_n, __new_start, 701 _M_get_Tp_allocator()); 702 this->_M_impl._M_start = __new_start; 703 _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 704 std::fill(__pos - difference_type(__n), __pos, __x_copy); 705 } 706 else 707 { 708 std::__uninitialized_move_fill(this->_M_impl._M_start, 709 __pos, __new_start, 710 this->_M_impl._M_start, 711 __x_copy, 712 _M_get_Tp_allocator()); 713 this->_M_impl._M_start = __new_start; 714 std::fill(__old_start, __pos, __x_copy); 715 } 716 } 717 __catch(...) 718 { 719 _M_destroy_nodes(__new_start._M_node, 720 this->_M_impl._M_start._M_node); 721 __throw_exception_again; 722 } 723 } 724 else 725 { 726 iterator __new_finish = _M_reserve_elements_at_back(__n); 727 iterator __old_finish = this->_M_impl._M_finish; 728 const difference_type __elems_after = 729 difference_type(__length) - __elems_before; 730 __pos = this->_M_impl._M_finish - __elems_after; 731 __try 732 { 733 if (__elems_after > difference_type(__n)) 734 { 735 iterator __finish_n = (this->_M_impl._M_finish 736 - difference_type(__n)); 737 std::__uninitialized_move_a(__finish_n, 738 this->_M_impl._M_finish, 739 this->_M_impl._M_finish, 740 _M_get_Tp_allocator()); 741 this->_M_impl._M_finish = __new_finish; 742 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 743 std::fill(__pos, __pos + difference_type(__n), __x_copy); 744 } 745 else 746 { 747 std::__uninitialized_fill_move(this->_M_impl._M_finish, 748 __pos + difference_type(__n), 749 __x_copy, __pos, 750 this->_M_impl._M_finish, 751 _M_get_Tp_allocator()); 752 this->_M_impl._M_finish = __new_finish; 753 std::fill(__pos, __old_finish, __x_copy); 754 } 755 } 756 __catch(...) 757 { 758 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 759 __new_finish._M_node + 1); 760 __throw_exception_again; 761 } 762 } 763 } 764 765 template <typename _Tp, typename _Alloc> 766 template <typename _ForwardIterator> 767 void 768 deque<_Tp, _Alloc>:: 769 _M_insert_aux(iterator __pos, 770 _ForwardIterator __first, _ForwardIterator __last, 771 size_type __n) 772 { 773 const difference_type __elemsbefore = __pos - this->_M_impl._M_start; 774 const size_type __length = size(); 775 if (static_cast<size_type>(__elemsbefore) < __length / 2) 776 { 777 iterator __new_start = _M_reserve_elements_at_front(__n); 778 iterator __old_start = this->_M_impl._M_start; 779 __pos = this->_M_impl._M_start + __elemsbefore; 780 __try 781 { 782 if (__elemsbefore >= difference_type(__n)) 783 { 784 iterator __start_n = (this->_M_impl._M_start 785 + difference_type(__n)); 786 std::__uninitialized_move_a(this->_M_impl._M_start, 787 __start_n, __new_start, 788 _M_get_Tp_allocator()); 789 this->_M_impl._M_start = __new_start; 790 _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 791 std::copy(__first, __last, __pos - difference_type(__n)); 792 } 793 else 794 { 795 _ForwardIterator __mid = __first; 796 std::advance(__mid, difference_type(__n) - __elemsbefore); 797 std::__uninitialized_move_copy(this->_M_impl._M_start, 798 __pos, __first, __mid, 799 __new_start, 800 _M_get_Tp_allocator()); 801 this->_M_impl._M_start = __new_start; 802 std::copy(__mid, __last, __old_start); 803 } 804 } 805 __catch(...) 806 { 807 _M_destroy_nodes(__new_start._M_node, 808 this->_M_impl._M_start._M_node); 809 __throw_exception_again; 810 } 811 } 812 else 813 { 814 iterator __new_finish = _M_reserve_elements_at_back(__n); 815 iterator __old_finish = this->_M_impl._M_finish; 816 const difference_type __elemsafter = 817 difference_type(__length) - __elemsbefore; 818 __pos = this->_M_impl._M_finish - __elemsafter; 819 __try 820 { 821 if (__elemsafter > difference_type(__n)) 822 { 823 iterator __finish_n = (this->_M_impl._M_finish 824 - difference_type(__n)); 825 std::__uninitialized_move_a(__finish_n, 826 this->_M_impl._M_finish, 827 this->_M_impl._M_finish, 828 _M_get_Tp_allocator()); 829 this->_M_impl._M_finish = __new_finish; 830 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 831 std::copy(__first, __last, __pos); 832 } 833 else 834 { 835 _ForwardIterator __mid = __first; 836 std::advance(__mid, __elemsafter); 837 std::__uninitialized_copy_move(__mid, __last, __pos, 838 this->_M_impl._M_finish, 839 this->_M_impl._M_finish, 840 _M_get_Tp_allocator()); 841 this->_M_impl._M_finish = __new_finish; 842 std::copy(__first, __mid, __pos); 843 } 844 } 845 __catch(...) 846 { 847 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 848 __new_finish._M_node + 1); 849 __throw_exception_again; 850 } 851 } 852 } 853 854 template<typename _Tp, typename _Alloc> 855 void 856 deque<_Tp, _Alloc>:: 857 _M_destroy_data_aux(iterator __first, iterator __last) 858 { 859 for (_Map_pointer __node = __first._M_node + 1; 860 __node < __last._M_node; ++__node) 861 std::_Destroy(*__node, *__node + _S_buffer_size(), 862 _M_get_Tp_allocator()); 863 864 if (__first._M_node != __last._M_node) 865 { 866 std::_Destroy(__first._M_cur, __first._M_last, 867 _M_get_Tp_allocator()); 868 std::_Destroy(__last._M_first, __last._M_cur, 869 _M_get_Tp_allocator()); 870 } 871 else 872 std::_Destroy(__first._M_cur, __last._M_cur, 873 _M_get_Tp_allocator()); 874 } 875 876 template <typename _Tp, typename _Alloc> 877 void 878 deque<_Tp, _Alloc>:: 879 _M_new_elements_at_front(size_type __new_elems) 880 { 881 if (this->max_size() - this->size() < __new_elems) 882 __throw_length_error(__N("deque::_M_new_elements_at_front")); 883 884 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 885 / _S_buffer_size()); 886 _M_reserve_map_at_front(__new_nodes); 887 size_type __i; 888 __try 889 { 890 for (__i = 1; __i <= __new_nodes; ++__i) 891 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); 892 } 893 __catch(...) 894 { 895 for (size_type __j = 1; __j < __i; ++__j) 896 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); 897 __throw_exception_again; 898 } 899 } 900 901 template <typename _Tp, typename _Alloc> 902 void 903 deque<_Tp, _Alloc>:: 904 _M_new_elements_at_back(size_type __new_elems) 905 { 906 if (this->max_size() - this->size() < __new_elems) 907 __throw_length_error(__N("deque::_M_new_elements_at_back")); 908 909 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 910 / _S_buffer_size()); 911 _M_reserve_map_at_back(__new_nodes); 912 size_type __i; 913 __try 914 { 915 for (__i = 1; __i <= __new_nodes; ++__i) 916 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); 917 } 918 __catch(...) 919 { 920 for (size_type __j = 1; __j < __i; ++__j) 921 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); 922 __throw_exception_again; 923 } 924 } 925 926 template <typename _Tp, typename _Alloc> 927 void 928 deque<_Tp, _Alloc>:: 929 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) 930 { 931 const size_type __old_num_nodes 932 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; 933 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 934 935 _Map_pointer __new_nstart; 936 if (this->_M_impl._M_map_size > 2 * __new_num_nodes) 937 { 938 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size 939 - __new_num_nodes) / 2 940 + (__add_at_front ? __nodes_to_add : 0); 941 if (__new_nstart < this->_M_impl._M_start._M_node) 942 std::copy(this->_M_impl._M_start._M_node, 943 this->_M_impl._M_finish._M_node + 1, 944 __new_nstart); 945 else 946 std::copy_backward(this->_M_impl._M_start._M_node, 947 this->_M_impl._M_finish._M_node + 1, 948 __new_nstart + __old_num_nodes); 949 } 950 else 951 { 952 size_type __new_map_size = this->_M_impl._M_map_size 953 + std::max(this->_M_impl._M_map_size, 954 __nodes_to_add) + 2; 955 956 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); 957 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 958 + (__add_at_front ? __nodes_to_add : 0); 959 std::copy(this->_M_impl._M_start._M_node, 960 this->_M_impl._M_finish._M_node + 1, 961 __new_nstart); 962 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 963 964 this->_M_impl._M_map = __new_map; 965 this->_M_impl._M_map_size = __new_map_size; 966 } 967 968 this->_M_impl._M_start._M_set_node(__new_nstart); 969 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 970 } 971 972 _GLIBCXX_END_NAMESPACE_CONTAINER 973 974 // Overload for deque::iterators, exploiting the "segmented-iterator 975 // optimization". 976 template<typename _Tp, typename _VTp> 977 void 978 __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __first, 979 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last, 980 const _VTp& __value) 981 { 982 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; 983 if (__first._M_node != __last._M_node) 984 { 985 std::__fill_a1(__first._M_cur, __first._M_last, __value); 986 987 for (typename _Iter::_Map_pointer __node = __first._M_node + 1; 988 __node < __last._M_node; ++__node) 989 std::__fill_a1(*__node, *__node + _Iter::_S_buffer_size(), __value); 990 991 std::__fill_a1(__last._M_first, __last._M_cur, __value); 992 } 993 else 994 std::__fill_a1(__first._M_cur, __last._M_cur, __value); 995 } 996 997 template<bool _IsMove, 998 typename _Tp, typename _Ref, typename _Ptr, typename _OI> 999 _OI 1000 __copy_move_dit(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, 1001 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, 1002 _OI __result) 1003 { 1004 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; 1005 if (__first._M_node != __last._M_node) 1006 { 1007 __result 1008 = std::__copy_move_a1<_IsMove>(__first._M_cur, __first._M_last, 1009 __result); 1010 1011 for (typename _Iter::_Map_pointer __node = __first._M_node + 1; 1012 __node != __last._M_node; ++__node) 1013 __result 1014 = std::__copy_move_a1<_IsMove>(*__node, 1015 *__node + _Iter::_S_buffer_size(), 1016 __result); 1017 1018 return std::__copy_move_a1<_IsMove>(__last._M_first, __last._M_cur, 1019 __result); 1020 } 1021 1022 return std::__copy_move_a1<_IsMove>(__first._M_cur, __last._M_cur, 1023 __result); 1024 } 1025 1026 template<bool _IsMove, 1027 typename _Tp, typename _Ref, typename _Ptr, typename _OI> 1028 _OI 1029 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, 1030 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, 1031 _OI __result) 1032 { return __copy_move_dit<_IsMove>(__first, __last, __result); } 1033 1034 template<bool _IsMove, 1035 typename _ITp, typename _IRef, typename _IPtr, typename _OTp> 1036 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> 1037 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first, 1038 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last, 1039 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result) 1040 { return __copy_move_dit<_IsMove>(__first, __last, __result); } 1041 1042 template<bool _IsMove, typename _II, typename _Tp> 1043 typename __gnu_cxx::__enable_if< 1044 __is_random_access_iter<_II>::__value, 1045 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type 1046 __copy_move_a1(_II __first, _II __last, 1047 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result) 1048 { 1049 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; 1050 typedef typename _Iter::difference_type difference_type; 1051 1052 difference_type __len = __last - __first; 1053 while (__len > 0) 1054 { 1055 const difference_type __clen 1056 = std::min(__len, __result._M_last - __result._M_cur); 1057 std::__copy_move_a1<_IsMove>(__first, __first + __clen, 1058 __result._M_cur); 1059 1060 __first += __clen; 1061 __result += __clen; 1062 __len -= __clen; 1063 } 1064 1065 return __result; 1066 } 1067 1068 template<bool _IsMove, typename _CharT> 1069 typename __gnu_cxx::__enable_if< 1070 __is_char<_CharT>::__value, 1071 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type 1072 __copy_move_a2( 1073 istreambuf_iterator<_CharT, char_traits<_CharT> > __first, 1074 istreambuf_iterator<_CharT, char_traits<_CharT> > __last, 1075 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result) 1076 { 1077 if (__first == __last) 1078 return __result; 1079 1080 for (;;) 1081 { 1082 const std::ptrdiff_t __len = __result._M_last - __result._M_cur; 1083 const std::ptrdiff_t __nb 1084 = std::__copy_n_a(__first, __len, __result._M_cur, false) 1085 - __result._M_cur; 1086 __result += __nb; 1087 1088 if (__nb != __len) 1089 break; 1090 } 1091 1092 return __result; 1093 } 1094 1095 template<typename _CharT, typename _Size> 1096 typename __gnu_cxx::__enable_if< 1097 __is_char<_CharT>::__value, 1098 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type 1099 __copy_n_a( 1100 istreambuf_iterator<_CharT, char_traits<_CharT> > __it, _Size __size, 1101 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result, 1102 bool __strict) 1103 { 1104 if (__size == 0) 1105 return __result; 1106 1107 do 1108 { 1109 const _Size __len 1110 = std::min<_Size>(__result._M_last - __result._M_cur, __size); 1111 std::__copy_n_a(__it, __len, __result._M_cur, __strict); 1112 __result += __len; 1113 __size -= __len; 1114 } 1115 while (__size != 0); 1116 return __result; 1117 } 1118 1119 template<bool _IsMove, 1120 typename _Tp, typename _Ref, typename _Ptr, typename _OI> 1121 _OI 1122 __copy_move_backward_dit( 1123 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, 1124 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, 1125 _OI __result) 1126 { 1127 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; 1128 if (__first._M_node != __last._M_node) 1129 { 1130 __result = std::__copy_move_backward_a1<_IsMove>( 1131 __last._M_first, __last._M_cur, __result); 1132 1133 for (typename _Iter::_Map_pointer __node = __last._M_node - 1; 1134 __node != __first._M_node; --__node) 1135 __result = std::__copy_move_backward_a1<_IsMove>( 1136 *__node, *__node + _Iter::_S_buffer_size(), __result); 1137 1138 return std::__copy_move_backward_a1<_IsMove>( 1139 __first._M_cur, __first._M_last, __result); 1140 } 1141 1142 return std::__copy_move_backward_a1<_IsMove>( 1143 __first._M_cur, __last._M_cur, __result); 1144 } 1145 1146 template<bool _IsMove, 1147 typename _Tp, typename _Ref, typename _Ptr, typename _OI> 1148 _OI 1149 __copy_move_backward_a1( 1150 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, 1151 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, 1152 _OI __result) 1153 { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); } 1154 1155 template<bool _IsMove, 1156 typename _ITp, typename _IRef, typename _IPtr, typename _OTp> 1157 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> 1158 __copy_move_backward_a1( 1159 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first, 1160 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last, 1161 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result) 1162 { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); } 1163 1164 template<bool _IsMove, typename _II, typename _Tp> 1165 typename __gnu_cxx::__enable_if< 1166 __is_random_access_iter<_II>::__value, 1167 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type 1168 __copy_move_backward_a1(_II __first, _II __last, 1169 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result) 1170 { 1171 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; 1172 typedef typename _Iter::difference_type difference_type; 1173 1174 difference_type __len = __last - __first; 1175 while (__len > 0) 1176 { 1177 difference_type __rlen = __result._M_cur - __result._M_first; 1178 _Tp* __rend = __result._M_cur; 1179 if (!__rlen) 1180 { 1181 __rlen = _Iter::_S_buffer_size(); 1182 __rend = *(__result._M_node - 1) + __rlen; 1183 } 1184 1185 const difference_type __clen = std::min(__len, __rlen); 1186 std::__copy_move_backward_a1<_IsMove>(__last - __clen, __last, __rend); 1187 1188 __last -= __clen; 1189 __result -= __clen; 1190 __len -= __clen; 1191 } 1192 1193 return __result; 1194 } 1195 1196 template<typename _Tp, typename _Ref, typename _Ptr, typename _II> 1197 bool 1198 __equal_dit( 1199 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1, 1200 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1, 1201 _II __first2) 1202 { 1203 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; 1204 if (__first1._M_node != __last1._M_node) 1205 { 1206 if (!std::__equal_aux1(__first1._M_cur, __first1._M_last, __first2)) 1207 return false; 1208 1209 __first2 += __first1._M_last - __first1._M_cur; 1210 for (typename _Iter::_Map_pointer __node = __first1._M_node + 1; 1211 __node != __last1._M_node; 1212 __first2 += _Iter::_S_buffer_size(), ++__node) 1213 if (!std::__equal_aux1(*__node, *__node + _Iter::_S_buffer_size(), 1214 __first2)) 1215 return false; 1216 1217 return std::__equal_aux1(__last1._M_first, __last1._M_cur, __first2); 1218 } 1219 1220 return std::__equal_aux1(__first1._M_cur, __last1._M_cur, __first2); 1221 } 1222 1223 template<typename _Tp, typename _Ref, typename _Ptr, typename _II> 1224 typename __gnu_cxx::__enable_if< 1225 __is_random_access_iter<_II>::__value, bool>::__type 1226 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first1, 1227 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last1, 1228 _II __first2) 1229 { return std::__equal_dit(__first1, __last1, __first2); } 1230 1231 template<typename _Tp1, typename _Ref1, typename _Ptr1, 1232 typename _Tp2, typename _Ref2, typename _Ptr2> 1233 bool 1234 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1, 1235 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1, 1236 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2) 1237 { return std::__equal_dit(__first1, __last1, __first2); } 1238 1239 template<typename _II, typename _Tp, typename _Ref, typename _Ptr> 1240 typename __gnu_cxx::__enable_if< 1241 __is_random_access_iter<_II>::__value, bool>::__type 1242 __equal_aux1(_II __first1, _II __last1, 1243 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first2) 1244 { 1245 typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; 1246 typedef typename _Iter::difference_type difference_type; 1247 1248 difference_type __len = __last1 - __first1; 1249 while (__len > 0) 1250 { 1251 const difference_type __clen 1252 = std::min(__len, __first2._M_last - __first2._M_cur); 1253 if (!std::__equal_aux1(__first1, __first1 + __clen, __first2._M_cur)) 1254 return false; 1255 1256 __first1 += __clen; 1257 __len -= __clen; 1258 __first2 += __clen; 1259 } 1260 1261 return true; 1262 } 1263 1264 template<typename _Tp1, typename _Ref, typename _Ptr, typename _Tp2> 1265 int 1266 __lex_cmp_dit( 1267 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __first1, 1268 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __last1, 1269 const _Tp2* __first2, const _Tp2* __last2) 1270 { 1271 const bool __simple = 1272 (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value 1273 && __is_pointer<_Ptr>::__value 1274 #if __cplusplus > 201703L && __cpp_lib_concepts 1275 // For C++20 iterator_traits<volatile T*>::value_type is non-volatile 1276 // so __is_byte<T> could be true, but we can't use memcmp with 1277 // volatile data. 1278 && !is_volatile_v<_Tp1> 1279 && !is_volatile_v<_Tp2> 1280 #endif 1281 ); 1282 typedef std::__lexicographical_compare<__simple> _Lc; 1283 1284 while (__first1._M_node != __last1._M_node) 1285 { 1286 const ptrdiff_t __len1 = __first1._M_last - __first1._M_cur; 1287 const ptrdiff_t __len2 = __last2 - __first2; 1288 const ptrdiff_t __len = std::min(__len1, __len2); 1289 // if __len1 > __len2 this will return a positive value: 1290 if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_last, 1291 __first2, __first2 + __len)) 1292 return __ret; 1293 1294 __first1 += __len; 1295 __first2 += __len; 1296 } 1297 return _Lc::__3way(__first1._M_cur, __last1._M_cur, 1298 __first2, __last2); 1299 } 1300 1301 template<typename _Tp1, typename _Ref1, typename _Ptr1, 1302 typename _Tp2> 1303 inline bool 1304 __lexicographical_compare_aux1( 1305 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1, 1306 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1, 1307 _Tp2* __first2, _Tp2* __last2) 1308 { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2) < 0; } 1309 1310 template<typename _Tp1, 1311 typename _Tp2, typename _Ref2, typename _Ptr2> 1312 inline bool 1313 __lexicographical_compare_aux1(_Tp1* __first1, _Tp1* __last1, 1314 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2, 1315 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2) 1316 { return std::__lex_cmp_dit(__first2, __last2, __first1, __last1) > 0; } 1317 1318 template<typename _Tp1, typename _Ref1, typename _Ptr1, 1319 typename _Tp2, typename _Ref2, typename _Ptr2> 1320 inline bool 1321 __lexicographical_compare_aux1( 1322 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1, 1323 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1, 1324 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2, 1325 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2) 1326 { 1327 const bool __simple = 1328 (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value 1329 && __is_pointer<_Ptr1>::__value 1330 && __is_pointer<_Ptr2>::__value 1331 #if __cplusplus > 201703L && __cpp_lib_concepts 1332 // For C++20 iterator_traits<volatile T*>::value_type is non-volatile 1333 // so __is_byte<T> could be true, but we can't use memcmp with 1334 // volatile data. 1335 && !is_volatile_v<_Tp1> 1336 && !is_volatile_v<_Tp2> 1337 #endif 1338 ); 1339 typedef std::__lexicographical_compare<__simple> _Lc; 1340 1341 while (__first1 != __last1) 1342 { 1343 const ptrdiff_t __len2 = __first2._M_node == __last2._M_node 1344 ? __last2._M_cur - __first2._M_cur 1345 : __first2._M_last - __first2._M_cur; 1346 if (__len2 == 0) 1347 return false; 1348 const ptrdiff_t __len1 = __first1._M_node == __last1._M_node 1349 ? __last1._M_cur - __first1._M_cur 1350 : __first1._M_last - __first1._M_cur; 1351 const ptrdiff_t __len = std::min(__len1, __len2); 1352 if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_cur + __len, 1353 __first2._M_cur, __first2._M_cur + __len)) 1354 return __ret < 0; 1355 1356 __first1 += __len; 1357 __first2 += __len; 1358 } 1359 1360 return __last2 != __first2; 1361 } 1362 1363 _GLIBCXX_END_NAMESPACE_VERSION 1364 } // namespace std 1365 1366 #endif 1367