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
61namespace 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>::
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>::
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(pos: 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>::
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>::
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>::
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
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>::
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>::
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(pos: begin() + __n);
277 }
278 else
279 {
280 if (__last != end())
281 _GLIBCXX_MOVE3(__last, end(), __first);
282 _M_erase_at_end(pos: 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>::
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(pos: __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>::
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>::
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>::
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>::
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>::
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>::
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, a: _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>::
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>::
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>::
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>::
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>::
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>::
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>::
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(nodes_to_add: __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(nodes_to_add: __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(a: __len1, b: __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(a: __len1, b: __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