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