libstdc++
deque.tcc
Go to the documentation of this file.
1 // Deque implementation (out of line) -*- C++ -*-
2 
3 // Copyright (C) 2001-2026 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>::
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(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(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>::
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>::
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 (size_type(__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, _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, typename _Sentinel>
588  void
589  deque<_Tp, _Alloc>::
590  _M_range_prepend(_InputIterator __first, _Sentinel __last,
591  size_type __n)
592  {
593  iterator __new_start = _M_reserve_elements_at_front(__n);
594  __try
595  {
596  std::__uninitialized_copy_a(_GLIBCXX_MOVE(__first), __last,
597  __new_start, _M_get_Tp_allocator());
598  this->_M_impl._M_start = __new_start;
599  }
600  __catch(...)
601  {
602  _M_destroy_nodes(__new_start._M_node,
603  this->_M_impl._M_start._M_node);
604  __throw_exception_again;
605  }
606  }
607 
608  template <typename _Tp, typename _Alloc>
609  template <typename _InputIterator, typename _Sentinel>
610  void
611  deque<_Tp, _Alloc>::
612  _M_range_append(_InputIterator __first, _Sentinel __last,
613  size_type __n)
614  {
615  iterator __new_finish = _M_reserve_elements_at_back(__n);
616  __try
617  {
618  std::__uninitialized_copy_a(_GLIBCXX_MOVE(__first), __last,
619  this->_M_impl._M_finish,
620  _M_get_Tp_allocator());
621  this->_M_impl._M_finish = __new_finish;
622  }
623  __catch(...)
624  {
625  _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
626  __new_finish._M_node + 1);
627  __throw_exception_again;
628  }
629  }
630 
631  template <typename _Tp, typename _Alloc>
632  template <typename _InputIterator>
633  void
634  deque<_Tp, _Alloc>::
635  _M_range_insert_aux(iterator __pos,
636  _InputIterator __first, _InputIterator __last,
637  std::input_iterator_tag)
638  { std::copy(__first, __last, std::inserter(*this, __pos)); }
639 
640  template <typename _Tp, typename _Alloc>
641  template <typename _ForwardIterator>
642  void
643  deque<_Tp, _Alloc>::
644  _M_range_insert_aux(iterator __pos,
645  _ForwardIterator __first, _ForwardIterator __last,
646  std::forward_iterator_tag)
647  {
648  const size_type __n = std::distance(__first, __last);
649  if (__builtin_expect(__n == 0, 0))
650  return;
651 
652  if (__pos._M_cur == this->_M_impl._M_start._M_cur)
653  _M_range_prepend(__first, __last, __n);
654  else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
655  _M_range_append(__first, __last, __n);
656  else
657  _M_insert_aux(__pos, __first, __last, __n);
658  }
659 
660  template<typename _Tp, typename _Alloc>
661 #if __cplusplus >= 201103L
662  template<typename... _Args>
663  typename deque<_Tp, _Alloc>::iterator
664  deque<_Tp, _Alloc>::
665  _M_emplace_aux(iterator __pos, _Args&&... __args)
666  {
667  // We should construct this temporary while the deque is
668  // in its current state in case something in __args...
669  // depends on that state before shuffling elements around.
670  _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
671 #else
672  typename deque<_Tp, _Alloc>::iterator
673  deque<_Tp, _Alloc>::
674  _M_insert_aux(iterator __pos, const value_type& __x)
675  {
676  value_type __x_copy = __x; // XXX copy
677 #endif
678  difference_type __index = __pos - this->_M_impl._M_start;
679  if (static_cast<size_type>(__index) < size() / 2)
680  {
681  push_front(_GLIBCXX_MOVE(front()));
682  iterator __front1 = this->_M_impl._M_start;
683  ++__front1;
684  iterator __front2 = __front1;
685  ++__front2;
686  __pos = this->_M_impl._M_start + __index;
687  iterator __pos1 = __pos;
688  ++__pos1;
689  _GLIBCXX_MOVE3(__front2, __pos1, __front1);
690  }
691  else
692  {
693  push_back(_GLIBCXX_MOVE(back()));
694  iterator __back1 = this->_M_impl._M_finish;
695  --__back1;
696  iterator __back2 = __back1;
697  --__back2;
698  __pos = this->_M_impl._M_start + __index;
699  _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
700  }
701 #if __cplusplus >= 201103L
702  *__pos = std::move(__tmp._M_val());
703 #else
704  *__pos = __x_copy;
705 #endif
706  return __pos;
707  }
708 
709  template <typename _Tp, typename _Alloc>
710  void
711  deque<_Tp, _Alloc>::
712  _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
713  {
714  const difference_type __elems_before = __pos - this->_M_impl._M_start;
715  const size_type __length = this->size();
716  value_type __x_copy = __x;
717  if (__elems_before < difference_type(__length / 2))
718  {
719  iterator __new_start = _M_reserve_elements_at_front(__n);
720  iterator __old_start = this->_M_impl._M_start;
721  __pos = this->_M_impl._M_start + __elems_before;
722  __try
723  {
724  if (__elems_before >= difference_type(__n))
725  {
726  iterator __start_n = (this->_M_impl._M_start
727  + difference_type(__n));
728  std::__uninitialized_move_a(this->_M_impl._M_start,
729  __start_n, __new_start,
730  _M_get_Tp_allocator());
731  this->_M_impl._M_start = __new_start;
732  _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
733  std::fill(__pos - difference_type(__n), __pos, __x_copy);
734  }
735  else
736  {
737  std::__uninitialized_move_fill(this->_M_impl._M_start,
738  __pos, __new_start,
739  this->_M_impl._M_start,
740  __x_copy,
741  _M_get_Tp_allocator());
742  this->_M_impl._M_start = __new_start;
743  std::fill(__old_start, __pos, __x_copy);
744  }
745  }
746  __catch(...)
747  {
748  _M_destroy_nodes(__new_start._M_node,
749  this->_M_impl._M_start._M_node);
750  __throw_exception_again;
751  }
752  }
753  else
754  {
755  iterator __new_finish = _M_reserve_elements_at_back(__n);
756  iterator __old_finish = this->_M_impl._M_finish;
757  const difference_type __elems_after =
758  difference_type(__length) - __elems_before;
759  __pos = this->_M_impl._M_finish - __elems_after;
760  __try
761  {
762  if (__elems_after > difference_type(__n))
763  {
764  iterator __finish_n = (this->_M_impl._M_finish
765  - difference_type(__n));
766  std::__uninitialized_move_a(__finish_n,
767  this->_M_impl._M_finish,
768  this->_M_impl._M_finish,
769  _M_get_Tp_allocator());
770  this->_M_impl._M_finish = __new_finish;
771  _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
772  std::fill(__pos, __pos + difference_type(__n), __x_copy);
773  }
774  else
775  {
776  std::__uninitialized_fill_move(this->_M_impl._M_finish,
777  __pos + difference_type(__n),
778  __x_copy, __pos,
779  this->_M_impl._M_finish,
780  _M_get_Tp_allocator());
781  this->_M_impl._M_finish = __new_finish;
782  std::fill(__pos, __old_finish, __x_copy);
783  }
784  }
785  __catch(...)
786  {
787  _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
788  __new_finish._M_node + 1);
789  __throw_exception_again;
790  }
791  }
792  }
793 
794  template <typename _Tp, typename _Alloc>
795  template <typename _ForwardIterator>
796  void
797  deque<_Tp, _Alloc>::
798  _M_insert_aux(iterator __pos,
799  _ForwardIterator __first, _ForwardIterator __last,
800  size_type __n)
801  {
802  const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
803  const size_type __length = size();
804  if (static_cast<size_type>(__elemsbefore) < __length / 2)
805  {
806  iterator __new_start = _M_reserve_elements_at_front(__n);
807  iterator __old_start = this->_M_impl._M_start;
808  __pos = this->_M_impl._M_start + __elemsbefore;
809  __try
810  {
811  if (__elemsbefore >= difference_type(__n))
812  {
813  iterator __start_n = (this->_M_impl._M_start
814  + difference_type(__n));
815  std::__uninitialized_move_a(this->_M_impl._M_start,
816  __start_n, __new_start,
817  _M_get_Tp_allocator());
818  this->_M_impl._M_start = __new_start;
819  _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
820  std::copy(__first, __last, __pos - difference_type(__n));
821  }
822  else
823  {
824  _ForwardIterator __mid = __first;
825  std::advance(__mid, difference_type(__n) - __elemsbefore);
826  std::__uninitialized_move_copy(this->_M_impl._M_start,
827  __pos, __first, __mid,
828  __new_start,
829  _M_get_Tp_allocator());
830  this->_M_impl._M_start = __new_start;
831  std::copy(__mid, __last, __old_start);
832  }
833  }
834  __catch(...)
835  {
836  _M_destroy_nodes(__new_start._M_node,
837  this->_M_impl._M_start._M_node);
838  __throw_exception_again;
839  }
840  }
841  else
842  {
843  iterator __new_finish = _M_reserve_elements_at_back(__n);
844  iterator __old_finish = this->_M_impl._M_finish;
845  const difference_type __elemsafter =
846  difference_type(__length) - __elemsbefore;
847  __pos = this->_M_impl._M_finish - __elemsafter;
848  __try
849  {
850  if (__elemsafter > difference_type(__n))
851  {
852  iterator __finish_n = (this->_M_impl._M_finish
853  - difference_type(__n));
854  std::__uninitialized_move_a(__finish_n,
855  this->_M_impl._M_finish,
856  this->_M_impl._M_finish,
857  _M_get_Tp_allocator());
858  this->_M_impl._M_finish = __new_finish;
859  _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
860  std::copy(__first, __last, __pos);
861  }
862  else
863  {
864  _ForwardIterator __mid = __first;
865  std::advance(__mid, __elemsafter);
866  std::__uninitialized_copy_move(__mid, __last, __pos,
867  this->_M_impl._M_finish,
868  this->_M_impl._M_finish,
869  _M_get_Tp_allocator());
870  this->_M_impl._M_finish = __new_finish;
871  std::copy(__first, __mid, __pos);
872  }
873  }
874  __catch(...)
875  {
876  _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
877  __new_finish._M_node + 1);
878  __throw_exception_again;
879  }
880  }
881  }
882 
883 #if __glibcxx_containers_ranges // C++ >= 23
884  template<ranges::forward_range _Rg>
885  auto __advance_dist(_Rg& __rg)
886  {
887  struct _Res
888  {
889  ranges::iterator_t<_Rg> __last;
890  ranges::range_difference_t<_Rg> __size;
891  };
892  if constexpr (ranges::common_range<_Rg>)
893  return _Res{ranges::end(__rg), ranges::distance(__rg)};
894  else if constexpr (ranges::sized_range<_Rg>)
895  {
896  auto const __n = ranges::distance(__rg);
897  auto __it = ranges::begin(__rg);
898  if constexpr (ranges::random_access_range<_Rg>)
899  __it += __n;
900  else
901  ranges::advance(__it, ranges::end(__rg));
902  return _Res{__it, __n};
903  }
904  else
905  {
906  auto __it = ranges::begin(__rg);
907  auto const __last = ranges::end(__rg);
908  ranges::range_difference_t<_Rg> __n(0);
909  for (; __it != __last; ++__it)
910  ++__n;
911  return _Res{__it, __n};
912  }
913  }
914 
915  template<typename _Tp, typename _Alloc>
916  template<__detail::__container_compatible_range<_Tp> _Rg>
917  auto
918  deque<_Tp, _Alloc>::
919  insert_range(const_iterator __pos, _Rg&& __rg)
920  -> iterator
921  {
922  if (__pos == cend())
923  {
924  const auto __ins_idx = size();
925  append_range(std::forward<_Rg>(__rg));
926  return begin() + __ins_idx;
927  }
928 
929  if (__pos == cbegin())
930  {
931  prepend_range(std::forward<_Rg>(__rg));
932  return begin();
933  }
934 
935  const auto __ins_idx = __pos - cbegin();
936  if constexpr (ranges::forward_range<_Rg>)
937  {
938  auto [__last, __n] = __advance_dist(__rg);
939  if (__n != 0) [[likely]]
940  _M_insert_aux(__pos._M_const_cast(),
941  ranges::begin(__rg), __last,
942  __n);
943  }
944  else
945  {
946  auto __first = ranges::begin(__rg);
947  const auto __last = ranges::end(__rg);
948  for (auto __it = __pos._M_const_cast(); __first != __last;
949  (void)++__first, ++__it)
950  __it = _M_emplace_aux(__it, *__first);
951  }
952  return begin() + __ins_idx;
953  }
954 
955  template<typename _Tp, typename _Alloc>
956  template<__detail::__container_compatible_range<_Tp> _Rg>
957  void
958  deque<_Tp, _Alloc>::
959  prepend_range(_Rg&& __rg)
960  {
961  if (empty())
962  append_range(std::forward<_Rg>(__rg));
963  else if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
964  {
965  const size_type __n(ranges::distance(__rg));
966  if (__n != 0) [[likely]]
967  _M_range_prepend(ranges::begin(__rg), ranges::end(__rg), __n);
968  }
969  else
970  {
971  struct _Guard_elts_front
972  {
973  deque& __self;
974  size_type __n = 0;
975 
976  ~_Guard_elts_front()
977  {
978  if (__n > 0)
979  __self._M_erase_at_begin(__self.begin() + __n);
980  }
981  };
982 
983  _Guard_elts_front __guard{*this};
984  auto __first = ranges::begin(__rg);
985  const auto __last = ranges::end(__rg);
986  for (; __first != __last; (void)++__first, ++__guard.__n)
987  emplace_front(*__first);
988 
989  for (auto __fins = begin(), __lins = begin() + __guard.__n;
990  __fins != __lins && __fins != --__lins; ++__fins)
991  std::iter_swap(__fins, __lins);
992 
993  __guard.__n = 0;
994  }
995  }
996 
997  template<typename _Tp, typename _Alloc>
998  template<__detail::__container_compatible_range<_Tp> _Rg>
999  void
1000  deque<_Tp, _Alloc>::
1001  append_range(_Rg&& __rg)
1002  {
1003  if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1004  {
1005  const size_type __n(ranges::distance(__rg));
1006  if (__n != 0) [[likely]]
1007  _M_range_append(ranges::begin(__rg), ranges::end(__rg), __n);
1008  }
1009  else
1010  {
1011  struct _Guard_elts_back
1012  {
1013  deque& __self;
1014  size_type __n = __self.size();
1015 
1016  ~_Guard_elts_back()
1017  {
1018  if (__n < __self.size())
1019  __self._M_erase_at_end(__self.begin() + __n);
1020  }
1021  };
1022 
1023  _Guard_elts_back __guard{*this};
1024  auto __first = ranges::begin(__rg);
1025  const auto __last = ranges::end(__rg);
1026  for (; __first != __last; (void)++__first)
1027  emplace_back(*__first);
1028 
1029  __guard.__n = size();
1030  }
1031  }
1032 #endif // containers_ranges
1033 
1034  template<typename _Tp, typename _Alloc>
1035  void
1036  deque<_Tp, _Alloc>::
1037  _M_destroy_data_aux(iterator __first, iterator __last)
1038  {
1039  for (_Map_pointer __node = __first._M_node + 1;
1040  __node < __last._M_node; ++__node)
1041  std::_Destroy(*__node, *__node + _S_buffer_size(),
1042  _M_get_Tp_allocator());
1043 
1044  if (__first._M_node != __last._M_node)
1045  {
1046  std::_Destroy(__first._M_cur, __first._M_last,
1047  _M_get_Tp_allocator());
1048  std::_Destroy(__last._M_first, __last._M_cur,
1049  _M_get_Tp_allocator());
1050  }
1051  else
1052  std::_Destroy(__first._M_cur, __last._M_cur,
1053  _M_get_Tp_allocator());
1054  }
1055 
1056  template <typename _Tp, typename _Alloc>
1057  void
1058  deque<_Tp, _Alloc>::
1059  _M_new_elements_at_front(size_type __new_elems)
1060  {
1061  if (this->max_size() - this->size() < __new_elems)
1062  __throw_length_error(__N("deque::_M_new_elements_at_front"));
1063 
1064  const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
1065  / _S_buffer_size());
1066  _M_reserve_map_at_front(__new_nodes);
1067  size_type __i;
1068  __try
1069  {
1070  for (__i = 1; __i <= __new_nodes; ++__i)
1071  *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
1072  }
1073  __catch(...)
1074  {
1075  for (size_type __j = 1; __j < __i; ++__j)
1076  _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
1077  __throw_exception_again;
1078  }
1079  }
1080 
1081  template <typename _Tp, typename _Alloc>
1082  void
1083  deque<_Tp, _Alloc>::
1084  _M_new_elements_at_back(size_type __new_elems)
1085  {
1086  if (this->max_size() - this->size() < __new_elems)
1087  __throw_length_error(__N("deque::_M_new_elements_at_back"));
1088 
1089  const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
1090  / _S_buffer_size());
1091  _M_reserve_map_at_back(__new_nodes);
1092  size_type __i;
1093  __try
1094  {
1095  for (__i = 1; __i <= __new_nodes; ++__i)
1096  *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
1097  }
1098  __catch(...)
1099  {
1100  for (size_type __j = 1; __j < __i; ++__j)
1101  _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
1102  __throw_exception_again;
1103  }
1104  }
1105 
1106  template <typename _Tp, typename _Alloc>
1107  void
1108  deque<_Tp, _Alloc>::
1109  _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
1110  {
1111  const size_type __old_num_nodes
1112  = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
1113  const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
1114 
1115  _Map_pointer __new_nstart;
1116  if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
1117  {
1118  __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
1119  - __new_num_nodes) / 2
1120  + (__add_at_front ? __nodes_to_add : 0);
1121  if (__new_nstart < this->_M_impl._M_start._M_node)
1122  std::copy(this->_M_impl._M_start._M_node,
1123  this->_M_impl._M_finish._M_node + 1,
1124  __new_nstart);
1125  else
1126  std::copy_backward(this->_M_impl._M_start._M_node,
1127  this->_M_impl._M_finish._M_node + 1,
1128  __new_nstart + __old_num_nodes);
1129  }
1130  else
1131  {
1132  size_type __new_map_size = this->_M_impl._M_map_size
1133  + std::max(this->_M_impl._M_map_size,
1134  __nodes_to_add) + 2;
1135 
1136  const size_t __bufsz = __deque_buf_size(sizeof(_Tp));
1137  if (__new_map_size > ((max_size() + __bufsz - 1) / __bufsz) * 2)
1138  __builtin_unreachable();
1139 
1140  _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
1141  __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
1142  + (__add_at_front ? __nodes_to_add : 0);
1143  std::copy(this->_M_impl._M_start._M_node,
1144  this->_M_impl._M_finish._M_node + 1,
1145  __new_nstart);
1146  _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
1147 
1148  this->_M_impl._M_map = __new_map;
1149  this->_M_impl._M_map_size = __new_map_size;
1150  }
1151 
1152  this->_M_impl._M_start._M_set_node(__new_nstart);
1153  this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
1154  }
1155 
1156 _GLIBCXX_END_NAMESPACE_CONTAINER
1157 
1158  // Overload for deque::iterators, exploiting the "segmented-iterator
1159  // optimization".
1160  template<typename _Tp, typename _VTp>
1161  void
1162  __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
1163  const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last,
1164  const _VTp& __value)
1165  {
1166  typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
1167  if (__first._M_node != __last._M_node)
1168  {
1169  std::__fill_a1(__first._M_cur, __first._M_last, __value);
1170 
1171  for (typename _Iter::_Map_pointer __node = __first._M_node + 1;
1172  __node < __last._M_node; ++__node)
1173  std::__fill_a1(*__node, *__node + _Iter::_S_buffer_size(), __value);
1174 
1175  std::__fill_a1(__last._M_first, __last._M_cur, __value);
1176  }
1177  else
1178  std::__fill_a1(__first._M_cur, __last._M_cur, __value);
1179  }
1180 
1181  template<bool _IsMove,
1182  typename _Tp, typename _Ref, typename _Ptr, typename _OI>
1183  _OI
1184  __copy_move_dit(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1185  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1186  _OI __result)
1187  {
1188  typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1189  if (__first._M_node != __last._M_node)
1190  {
1191  __result
1192  = std::__copy_move_a1<_IsMove>(__first._M_cur, __first._M_last,
1193  __result);
1194 
1195  for (typename _Iter::_Map_pointer __node = __first._M_node + 1;
1196  __node != __last._M_node; ++__node)
1197  __result
1198  = std::__copy_move_a1<_IsMove>(*__node,
1199  *__node + _Iter::_S_buffer_size(),
1200  __result);
1201 
1202  return std::__copy_move_a1<_IsMove>(__last._M_first, __last._M_cur,
1203  __result);
1204  }
1205 
1206  return std::__copy_move_a1<_IsMove>(__first._M_cur, __last._M_cur,
1207  __result);
1208  }
1209 
1210  template<bool _IsMove,
1211  typename _Tp, typename _Ref, typename _Ptr, typename _OI>
1212  _OI
1213  __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1214  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1215  _OI __result)
1216  { return __copy_move_dit<_IsMove>(__first, __last, __result); }
1217 
1218  template<bool _IsMove,
1219  typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
1220  _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
1221  __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first,
1222  _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last,
1223  _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result)
1224  { return __copy_move_dit<_IsMove>(__first, __last, __result); }
1225 
1226  template<bool _IsMove, typename _II, typename _Tp>
1227  typename __gnu_cxx::__enable_if<
1228  __is_any_random_access_iter<_II>::__value,
1229  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
1230  __copy_move_a1(_II __first, _II __last,
1231  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1232  {
1233  typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
1234  typedef typename _Iter::difference_type difference_type;
1235 
1236  difference_type __len = __last - __first;
1237  while (__len > 0)
1238  {
1239  const difference_type __clen
1240  = std::min(__len, __result._M_last - __result._M_cur);
1241  std::__copy_move_a1<_IsMove>(__first, __first + __clen,
1242  __result._M_cur);
1243 
1244  __first += __clen;
1245  __result += __clen;
1246  __len -= __clen;
1247  }
1248 
1249  return __result;
1250  }
1251 
1252  template<bool _IsMove, typename _CharT>
1253  typename __gnu_cxx::__enable_if<
1254  __is_char<_CharT>::__value,
1255  _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
1256  __copy_move_a2(
1257  istreambuf_iterator<_CharT, char_traits<_CharT> > __first,
1258  istreambuf_iterator<_CharT, char_traits<_CharT> > __last,
1259  _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result)
1260  {
1261  if (__first == __last)
1262  return __result;
1263 
1264  for (;;)
1265  {
1266  const std::ptrdiff_t __len = __result._M_last - __result._M_cur;
1267  const std::ptrdiff_t __nb
1268  = std::__copy_n_a(__first, __len, __result._M_cur, false)
1269  - __result._M_cur;
1270  __result += __nb;
1271 
1272  if (__nb != __len)
1273  break;
1274  }
1275 
1276  return __result;
1277  }
1278 
1279  template<typename _CharT, typename _Size>
1280  typename __gnu_cxx::__enable_if<
1281  __is_char<_CharT>::__value,
1282  _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
1283  __copy_n_a(
1284  istreambuf_iterator<_CharT, char_traits<_CharT> > __it, _Size __size,
1285  _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result,
1286  bool __strict)
1287  {
1288  if (__size == 0)
1289  return __result;
1290 
1291  do
1292  {
1293  const _Size __len
1294  = std::min<_Size>(__result._M_last - __result._M_cur, __size);
1295  std::__copy_n_a(__it, __len, __result._M_cur, __strict);
1296  __result += __len;
1297  __size -= __len;
1298  }
1299  while (__size != 0);
1300  return __result;
1301  }
1302 
1303  template<bool _IsMove,
1304  typename _Tp, typename _Ref, typename _Ptr, typename _OI>
1305  _OI
1306  __copy_move_backward_dit(
1307  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1308  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1309  _OI __result)
1310  {
1311  typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1312  if (__first._M_node != __last._M_node)
1313  {
1314  __result = std::__copy_move_backward_a1<_IsMove>(
1315  __last._M_first, __last._M_cur, __result);
1316 
1317  for (typename _Iter::_Map_pointer __node = __last._M_node - 1;
1318  __node != __first._M_node; --__node)
1319  __result = std::__copy_move_backward_a1<_IsMove>(
1320  *__node, *__node + _Iter::_S_buffer_size(), __result);
1321 
1322  return std::__copy_move_backward_a1<_IsMove>(
1323  __first._M_cur, __first._M_last, __result);
1324  }
1325 
1326  return std::__copy_move_backward_a1<_IsMove>(
1327  __first._M_cur, __last._M_cur, __result);
1328  }
1329 
1330  template<bool _IsMove,
1331  typename _Tp, typename _Ref, typename _Ptr, typename _OI>
1332  _OI
1333  __copy_move_backward_a1(
1334  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1335  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1336  _OI __result)
1337  { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); }
1338 
1339  template<bool _IsMove,
1340  typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
1341  _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
1342  __copy_move_backward_a1(
1343  _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first,
1344  _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last,
1345  _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result)
1346  { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); }
1347 
1348  template<bool _IsMove, typename _II, typename _Tp>
1349  typename __gnu_cxx::__enable_if<
1350  __is_any_random_access_iter<_II>::__value,
1351  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
1352  __copy_move_backward_a1(_II __first, _II __last,
1353  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1354  {
1355  typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
1356  typedef typename _Iter::difference_type difference_type;
1357 
1358  difference_type __len = __last - __first;
1359  while (__len > 0)
1360  {
1361  difference_type __rlen = __result._M_cur - __result._M_first;
1362  _Tp* __rend = __result._M_cur;
1363  if (!__rlen)
1364  {
1365  __rlen = _Iter::_S_buffer_size();
1366  __rend = *(__result._M_node - 1) + __rlen;
1367  }
1368 
1369  const difference_type __clen = std::min(__len, __rlen);
1370  std::__copy_move_backward_a1<_IsMove>(__last - __clen, __last, __rend);
1371 
1372  __last -= __clen;
1373  __result -= __clen;
1374  __len -= __clen;
1375  }
1376 
1377  return __result;
1378  }
1379 
1380  template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
1381  bool
1382  __equal_dit(
1383  const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
1384  const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
1385  _II __first2)
1386  {
1387  typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1388  if (__first1._M_node != __last1._M_node)
1389  {
1390  if (!std::__equal_aux1(__first1._M_cur, __first1._M_last, __first2))
1391  return false;
1392 
1393  __first2 += __first1._M_last - __first1._M_cur;
1394  for (typename _Iter::_Map_pointer __node = __first1._M_node + 1;
1395  __node != __last1._M_node;
1396  __first2 += _Iter::_S_buffer_size(), ++__node)
1397  if (!std::__equal_aux1(*__node, *__node + _Iter::_S_buffer_size(),
1398  __first2))
1399  return false;
1400 
1401  return std::__equal_aux1(__last1._M_first, __last1._M_cur, __first2);
1402  }
1403 
1404  return std::__equal_aux1(__first1._M_cur, __last1._M_cur, __first2);
1405  }
1406 
1407  template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
1408  typename __gnu_cxx::__enable_if<
1409  __is_any_random_access_iter<_II>::__value, bool>::__type
1410  __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first1,
1411  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last1,
1412  _II __first2)
1413  { return std::__equal_dit(__first1, __last1, __first2); }
1414 
1415  template<typename _Tp1, typename _Ref1, typename _Ptr1,
1416  typename _Tp2, typename _Ref2, typename _Ptr2>
1417  bool
1418  __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
1419  _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
1420  _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2)
1421  { return std::__equal_dit(__first1, __last1, __first2); }
1422 
1423  template<typename _II, typename _Tp, typename _Ref, typename _Ptr>
1424  typename __gnu_cxx::__enable_if<
1425  __is_any_random_access_iter<_II>::__value, bool>::__type
1426  __equal_aux1(_II __first1, _II __last1,
1427  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first2)
1428  {
1429  typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1430  typedef typename _Iter::difference_type difference_type;
1431 
1432  difference_type __len = __last1 - __first1;
1433  while (__len > 0)
1434  {
1435  const difference_type __clen
1436  = std::min(__len, __first2._M_last - __first2._M_cur);
1437  if (!std::__equal_aux1(__first1, __first1 + __clen, __first2._M_cur))
1438  return false;
1439 
1440  __first1 += __clen;
1441  __len -= __clen;
1442  __first2 += __clen;
1443  }
1444 
1445  return true;
1446  }
1447 
1448  template<typename _Tp1, typename _Ref, typename _Ptr, typename _Tp2>
1449  int
1450  __lex_cmp_dit(
1451  _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __first1,
1452  _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __last1,
1453  const _Tp2* __first2, const _Tp2* __last2)
1454  {
1455 #if _GLIBCXX_USE_BUILTIN_TRAIT(__is_pointer)
1456  const bool __simple =
1457  (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value
1458  && __is_pointer(_Ptr)
1459 #if __cplusplus > 201703L && __cpp_lib_concepts
1460  // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
1461  // so __is_byte<T> could be true, but we can't use memcmp with
1462  // volatile data.
1463  && !is_volatile_v<_Tp1> && !is_volatile_v<_Tp2>
1464 #endif
1465  );
1466  typedef std::__lexicographical_compare<__simple> _Lc;
1467 #else
1468  typedef std::__lexicographical_compare<false> _Lc;
1469 #endif
1470 
1471  while (__first1._M_node != __last1._M_node)
1472  {
1473  const ptrdiff_t __len1 = __first1._M_last - __first1._M_cur;
1474  const ptrdiff_t __len2 = __last2 - __first2;
1475  const ptrdiff_t __len = std::min(__len1, __len2);
1476  // if __len1 > __len2 this will return a positive value:
1477  if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_last,
1478  __first2, __first2 + __len))
1479  return __ret;
1480 
1481  __first1 += __len;
1482  __first2 += __len;
1483  }
1484  return _Lc::__3way(__first1._M_cur, __last1._M_cur,
1485  __first2, __last2);
1486  }
1487 
1488  template<typename _Tp1, typename _Ref1, typename _Ptr1,
1489  typename _Tp2>
1490  inline bool
1491  __lexicographical_compare_aux1(
1492  _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
1493  _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
1494  _Tp2* __first2, _Tp2* __last2)
1495  { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2) < 0; }
1496 
1497  template<typename _Tp1,
1498  typename _Tp2, typename _Ref2, typename _Ptr2>
1499  inline bool
1500  __lexicographical_compare_aux1(_Tp1* __first1, _Tp1* __last1,
1501  _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
1502  _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
1503  { return std::__lex_cmp_dit(__first2, __last2, __first1, __last1) > 0; }
1504 
1505  template<typename _Tp1, typename _Ref1, typename _Ptr1,
1506  typename _Tp2, typename _Ref2, typename _Ptr2>
1507  inline bool
1508  __lexicographical_compare_aux1(
1509  _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
1510  _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
1511  _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
1512  _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
1513  {
1514 #if _GLIBCXX_USE_BUILTIN_TRAIT(__is_pointer)
1515  const bool __simple =
1516  (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value
1517  && __is_pointer(_Ptr1) && __is_pointer(_Ptr2)
1518 #if __cplusplus > 201703L && __cpp_lib_concepts
1519  // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
1520  // so __is_byte<T> could be true, but we can't use memcmp with
1521  // volatile data.
1522  && !is_volatile_v<_Tp1> && !is_volatile_v<_Tp2>
1523 #endif
1524  );
1525  typedef std::__lexicographical_compare<__simple> _Lc;
1526 #else
1527  typedef std::__lexicographical_compare<false> _Lc;
1528 #endif
1529 
1530  while (__first1 != __last1)
1531  {
1532  const ptrdiff_t __len2 = __first2._M_node == __last2._M_node
1533  ? __last2._M_cur - __first2._M_cur
1534  : __first2._M_last - __first2._M_cur;
1535  if (__len2 == 0)
1536  return false;
1537  const ptrdiff_t __len1 = __first1._M_node == __last1._M_node
1538  ? __last1._M_cur - __first1._M_cur
1539  : __first1._M_last - __first1._M_cur;
1540  const ptrdiff_t __len = std::min(__len1, __len2);
1541  if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_cur + __len,
1542  __first2._M_cur, __first2._M_cur + __len))
1543  return __ret < 0;
1544 
1545  __first1 += __len;
1546  __first2 += __len;
1547  }
1548 
1549  return __last2 != __first2;
1550  }
1551 
1552 _GLIBCXX_END_NAMESPACE_VERSION
1553 } // namespace std
1554 
1555 #endif
std::_Deque_iterator
A deque::iterator.
Definition: stl_algobase.h:314
std::size
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:274
std::advance
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:262
std::min
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:233
std::empty
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:294
std::cend
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
Definition: range_access.h:144
std::deque::size
size_type size() const noexcept
Definition: stl_deque.h:1330
std::deque::emplace
iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in deque before specified iterator.
Definition: deque.tcc:188
std::deque::_M_reallocate_map
void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
Memory-handling helpers for the major map.
Definition: deque.tcc:1109
std::input_iterator_tag
Marking input iterators.
Definition: stl_iterator_base_types.h:95
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:138
std::deque::get_allocator
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
Definition: stl_deque.h:1203
std::deque::_M_range_initialize
void _M_range_initialize(_InputIterator __first, _InputIterator __last, std::input_iterator_tag)
Fills the deque with whatever is in [first,last).
Definition: deque.tcc:420
std::deque::_M_pop_back_aux
void _M_pop_back_aux()
Helper functions for push_* and pop_*.
Definition: deque.tcc:561
std::deque::_M_push_front_aux
void _M_push_front_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
Definition: deque.tcc:524
std::_Destroy
constexpr void _Destroy(_ForwardIterator __first, _ForwardIterator __last)
Definition: stl_construct.h:218
std::fill
constexpr void fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__value)
Fills the range [first,last) with copies of value.
Definition: stl_algobase.h:1003
std::deque::operator=
deque & operator=(const deque &__x)
Deque assignment operator.
Definition: deque.tcc:96
std::random_access_iterator_tag
Random-access iterators support a superset of bidirectional iterator operations.
Definition: stl_iterator_base_types.h:109
std::end
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1251
std
ISO C++ entities toplevel namespace is std.
std::deque::_M_push_back_aux
void _M_push_back_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
Definition: deque.tcc:485
std::begin
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1229
std::forward_iterator_tag
Forward iterators support a superset of input iterator operations.
Definition: stl_iterator_base_types.h:101
std::__addressof
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:52
std::deque::_M_fill_initialize
void _M_fill_initialize(const value_type &__value)
Fills the deque with copies of value.
Definition: deque.tcc:394
std::iterator
Common iterator class.
Definition: stl_iterator_base_types.h:129
stl_algobase.h
std::deque::_M_new_elements_at_back
void _M_new_elements_at_back(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
Definition: deque.tcc:1084
std::deque
A standard container using fixed-size memory allocation and constant-time manipulation of elements at...
Definition: stl_deque.h:791
std::distance
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:172
std::inserter
constexpr insert_iterator< _Container > inserter(_Container &__x, std::__detail::__range_iter_t< _Container > __i)
Definition: bits/stl_iterator.h:999
std::copy_backward
constexpr _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Copies the range [first,last) into result.
Definition: stl_algobase.h:836
std::__iterator_category
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
Definition: stl_iterator_base_types.h:241
std::deque::_M_pop_front_aux
void _M_pop_front_aux()
Helper functions for push_* and pop_*.
Definition: deque.tcc:577
std::deque::begin
iterator begin() noexcept
Definition: stl_deque.h:1213
std::iter_swap
constexpr void iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
Swaps the contents of two iterators.
Definition: stl_algobase.h:155
std::max
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:257
std::deque::end
iterator end() noexcept
Definition: stl_deque.h:1232
std::cbegin
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
Definition: range_access.h:132
std::deque::_M_new_elements_at_front
void _M_new_elements_at_front(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
Definition: deque.tcc:1059