libstdc++
stl_deque.h
Go to the documentation of this file.
1// Deque implementation -*- 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/stl_deque.h
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 _STL_DEQUE_H
57#define _STL_DEQUE_H 1
58
59#include <bits/concept_check.h>
60#include <bits/stl_iterator_base_types.h>
61#include <bits/stl_iterator_base_funcs.h>
62#if __cplusplus >= 201103L
63#include <initializer_list>
64#include <bits/stl_uninitialized.h> // for __is_bitwise_relocatable
65#endif
66#if __cplusplus > 201703L
67# include <compare>
68#endif
69#if __cplusplus > 202002L
70# include <bits/ranges_algobase.h> // ranges::copy
71#endif
72
73#include <debug/assertions.h>
74
75namespace std _GLIBCXX_VISIBILITY(default)
76{
77_GLIBCXX_BEGIN_NAMESPACE_VERSION
78_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
79
80 /**
81 * @brief This function controls the size of memory nodes.
82 * @param __size The size of an element.
83 * @return The number (not byte size) of elements per node.
84 *
85 * This function started off as a compiler kludge from SGI, but
86 * seems to be a useful wrapper around a repeated constant
87 * expression. The @b 512 is tunable (and no other code needs to
88 * change), but no investigation has been done since inheriting the
89 * SGI code. Touch _GLIBCXX_DEQUE_BUF_SIZE only if you know what
90 * you are doing, however: changing it breaks the binary
91 * compatibility!!
92 */
93
94#ifndef _GLIBCXX_DEQUE_BUF_SIZE
95#define _GLIBCXX_DEQUE_BUF_SIZE 512
96#endif
97
98 _GLIBCXX_CONSTEXPR inline size_t
99 __deque_buf_size(size_t __size)
100 { return (__size < _GLIBCXX_DEQUE_BUF_SIZE
101 ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }
102
103
104 /**
105 * @brief A deque::iterator.
106 *
107 * Quite a bit of intelligence here. Much of the functionality of
108 * deque is actually passed off to this class. A deque holds two
109 * of these internally, marking its valid range. Access to
110 * elements is done as offsets of either of those two, relying on
111 * operator overloading in this class.
112 *
113 * All the functions are op overloads except for _M_set_node.
114 */
115 template<typename _Tp, typename _Ref, typename _Ptr>
116 struct _Deque_iterator
117 {
118#if __cplusplus < 201103L
119 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
120 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
121 typedef _Tp* _Elt_pointer;
122 typedef _Tp** _Map_pointer;
123#else
124 private:
125 template<typename _CvTp>
126 using __iter = _Deque_iterator<_Tp, _CvTp&, __ptr_rebind<_Ptr, _CvTp>>;
127 public:
128 typedef __iter<_Tp> iterator;
129 typedef __iter<const _Tp> const_iterator;
130 typedef __ptr_rebind<_Ptr, _Tp> _Elt_pointer;
131 typedef __ptr_rebind<_Ptr, _Elt_pointer> _Map_pointer;
132#endif
133
134 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
135 { return __deque_buf_size(sizeof(_Tp)); }
136
137 typedef std::random_access_iterator_tag iterator_category;
138 typedef _Tp value_type;
139 typedef _Ptr pointer;
140 typedef _Ref reference;
141 typedef size_t size_type;
142 typedef ptrdiff_t difference_type;
143 typedef _Deque_iterator _Self;
144
145 _Elt_pointer _M_cur;
146 _Elt_pointer _M_first;
147 _Elt_pointer _M_last;
148 _Map_pointer _M_node;
149
150 _Deque_iterator(_Elt_pointer __x, _Map_pointer __y) _GLIBCXX_NOEXCEPT
151 : _M_cur(__x), _M_first(*__y),
152 _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
153
154 _Deque_iterator() _GLIBCXX_NOEXCEPT
155 : _M_cur(), _M_first(), _M_last(), _M_node() { }
156
157#if __cplusplus < 201103L
158 // Conversion from iterator to const_iterator.
159 _Deque_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT
160 : _M_cur(__x._M_cur), _M_first(__x._M_first),
161 _M_last(__x._M_last), _M_node(__x._M_node) { }
162#else
163 // Conversion from iterator to const_iterator.
164 template<typename _Iter,
165 typename = _Require<is_same<_Self, const_iterator>,
166 is_same<_Iter, iterator>>>
167 _Deque_iterator(const _Iter& __x) noexcept
168 : _M_cur(__x._M_cur), _M_first(__x._M_first),
169 _M_last(__x._M_last), _M_node(__x._M_node) { }
170
171 _Deque_iterator(const _Deque_iterator& __x) noexcept
172 : _M_cur(__x._M_cur), _M_first(__x._M_first),
173 _M_last(__x._M_last), _M_node(__x._M_node) { }
174
175 _Deque_iterator& operator=(const _Deque_iterator&) = default;
176#endif
177
178 iterator
179 _M_const_cast() const _GLIBCXX_NOEXCEPT
180 { return iterator(_M_cur, _M_node); }
181
182 _GLIBCXX_NODISCARD
183 reference
184 operator*() const _GLIBCXX_NOEXCEPT
185 { return *_M_cur; }
186
187 _GLIBCXX_NODISCARD
188 pointer
189 operator->() const _GLIBCXX_NOEXCEPT
190 { return _M_cur; }
191
192 _Self&
193 operator++() _GLIBCXX_NOEXCEPT
194 {
195 ++_M_cur;
196 if (_M_cur == _M_last)
197 {
198 _M_set_node(_M_node + 1);
199 _M_cur = _M_first;
200 }
201 return *this;
202 }
203
204 _Self
205 operator++(int) _GLIBCXX_NOEXCEPT
206 {
207 _Self __tmp = *this;
208 ++*this;
209 return __tmp;
210 }
211
212 _Self&
213 operator--() _GLIBCXX_NOEXCEPT
214 {
215 if (_M_cur == _M_first)
216 {
217 _M_set_node(_M_node - 1);
218 _M_cur = _M_last;
219 }
220 --_M_cur;
221 return *this;
222 }
223
224 _Self
225 operator--(int) _GLIBCXX_NOEXCEPT
226 {
227 _Self __tmp = *this;
228 --*this;
229 return __tmp;
230 }
231
232 _Self&
233 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
234 {
235 const difference_type __offset = __n + (_M_cur - _M_first);
236 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
237 _M_cur += __n;
238 else
239 {
240 const difference_type __node_offset =
241 __offset > 0 ? __offset / difference_type(_S_buffer_size())
242 : -difference_type((-__offset - 1)
243 / _S_buffer_size()) - 1;
244 _M_set_node(_M_node + __node_offset);
245 _M_cur = _M_first + (__offset - __node_offset
246 * difference_type(_S_buffer_size()));
247 }
248 return *this;
249 }
250
251 _Self&
252 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
253 { return *this += -__n; }
254
255 _GLIBCXX_NODISCARD
256 reference
257 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
258 { return *(*this + __n); }
259
260 /**
261 * Prepares to traverse new_node. Sets everything except
262 * _M_cur, which should therefore be set by the caller
263 * immediately afterwards, based on _M_first and _M_last.
264 */
265 void
266 _M_set_node(_Map_pointer __new_node) _GLIBCXX_NOEXCEPT
267 {
268 _M_node = __new_node;
269 _M_first = *__new_node;
270 _M_last = _M_first + difference_type(_S_buffer_size());
271 }
272
273 _GLIBCXX_NODISCARD
274 friend bool
275 operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
276 { return __x._M_cur == __y._M_cur; }
277
278 // Note: we also provide overloads whose operands are of the same type in
279 // order to avoid ambiguous overload resolution when std::rel_ops
280 // operators are in scope (for additional details, see libstdc++/3628)
281 template<typename _RefR, typename _PtrR>
282 _GLIBCXX_NODISCARD
283 friend bool
284 operator==(const _Self& __x,
285 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
286 _GLIBCXX_NOEXCEPT
287 { return __x._M_cur == __y._M_cur; }
288
289#if __cpp_lib_three_way_comparison
290 [[nodiscard]]
291 friend strong_ordering
292 operator<=>(const _Self& __x, const _Self& __y) noexcept
293 {
294 if (const auto __cmp = __x._M_node <=> __y._M_node; __cmp != 0)
295 return __cmp;
296 return __x._M_cur <=> __y._M_cur;
297 }
298#else
299 _GLIBCXX_NODISCARD
300 friend bool
301 operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
302 { return !(__x == __y); }
303
304 template<typename _RefR, typename _PtrR>
305 _GLIBCXX_NODISCARD
306 friend bool
307 operator!=(const _Self& __x,
308 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
309 _GLIBCXX_NOEXCEPT
310 { return !(__x == __y); }
311
312 _GLIBCXX_NODISCARD
313 friend bool
314 operator<(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
315 {
316 return (__x._M_node == __y._M_node)
317 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
318 }
319
320 template<typename _RefR, typename _PtrR>
321 _GLIBCXX_NODISCARD
322 friend bool
323 operator<(const _Self& __x,
324 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
325 _GLIBCXX_NOEXCEPT
326 {
327 return (__x._M_node == __y._M_node)
328 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
329 }
330
331 _GLIBCXX_NODISCARD
332 friend bool
333 operator>(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
334 { return __y < __x; }
335
336 template<typename _RefR, typename _PtrR>
337 _GLIBCXX_NODISCARD
338 friend bool
339 operator>(const _Self& __x,
340 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
341 _GLIBCXX_NOEXCEPT
342 { return __y < __x; }
343
344 _GLIBCXX_NODISCARD
345 friend bool
346 operator<=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
347 { return !(__y < __x); }
348
349 template<typename _RefR, typename _PtrR>
350 _GLIBCXX_NODISCARD
351 friend bool
352 operator<=(const _Self& __x,
353 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
354 _GLIBCXX_NOEXCEPT
355 { return !(__y < __x); }
356
357 _GLIBCXX_NODISCARD
358 friend bool
359 operator>=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
360 { return !(__x < __y); }
361
362 template<typename _RefR, typename _PtrR>
363 _GLIBCXX_NODISCARD
364 friend bool
365 operator>=(const _Self& __x,
366 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
367 _GLIBCXX_NOEXCEPT
368 { return !(__x < __y); }
369#endif // three-way comparison
370
371 _GLIBCXX_NODISCARD
372 friend difference_type
373 operator-(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
374 {
375 return difference_type(_S_buffer_size())
376 * (__x._M_node - __y._M_node - bool(__x._M_node))
377 + (__x._M_cur - __x._M_first)
378 + (__y._M_last - __y._M_cur);
379 }
380
381 // _GLIBCXX_RESOLVE_LIB_DEFECTS
382 // According to the resolution of DR179 not only the various comparison
383 // operators but also operator- must accept mixed iterator/const_iterator
384 // parameters.
385 template<typename _RefR, typename _PtrR>
386 _GLIBCXX_NODISCARD
387 friend difference_type
388 operator-(const _Self& __x,
389 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
390 _GLIBCXX_NOEXCEPT
391 {
392 return difference_type(_S_buffer_size())
393 * (__x._M_node - __y._M_node - bool(__x._M_node))
394 + (__x._M_cur - __x._M_first)
395 + (__y._M_last - __y._M_cur);
396 }
397
398 _GLIBCXX_NODISCARD
399 friend _Self
400 operator+(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
401 {
402 _Self __tmp = __x;
403 __tmp += __n;
404 return __tmp;
405 }
406
407 _GLIBCXX_NODISCARD
408 friend _Self
409 operator-(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
410 {
411 _Self __tmp = __x;
412 __tmp -= __n;
413 return __tmp;
414 }
415
416 _GLIBCXX_NODISCARD
417 friend _Self
418 operator+(difference_type __n, const _Self& __x) _GLIBCXX_NOEXCEPT
419 { return __x + __n; }
420 };
421
422 /**
423 * Deque base class. This class provides the unified face for %deque's
424 * allocation. This class's constructor and destructor allocate and
425 * deallocate (but do not initialize) storage. This makes %exception
426 * safety easier.
427 *
428 * Nothing in this class ever constructs or destroys an actual Tp element.
429 * (Deque handles that itself.) Only/All memory management is performed
430 * here.
431 */
432 template<typename _Tp, typename _Alloc>
433 class _Deque_base
434 {
435 protected:
436 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
437 rebind<_Tp>::other _Tp_alloc_type;
438 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits;
439
440#if __cplusplus < 201103L
441 typedef _Tp* _Ptr;
442 typedef const _Tp* _Ptr_const;
443#else
444 typedef typename _Alloc_traits::pointer _Ptr;
445 typedef typename _Alloc_traits::const_pointer _Ptr_const;
446#endif
447
448 typedef typename _Alloc_traits::template rebind<_Ptr>::other
449 _Map_alloc_type;
450 typedef __gnu_cxx::__alloc_traits<_Map_alloc_type> _Map_alloc_traits;
451
452 typedef _Alloc allocator_type;
453
454 allocator_type
455 get_allocator() const _GLIBCXX_NOEXCEPT
456 { return allocator_type(_M_get_Tp_allocator()); }
457
458 typedef _Deque_iterator<_Tp, _Tp&, _Ptr> iterator;
459 typedef _Deque_iterator<_Tp, const _Tp&, _Ptr_const> const_iterator;
460
461 _Deque_base()
462 : _M_impl()
463 { _M_initialize_map(0); }
464
465 _Deque_base(size_t __num_elements)
466 : _M_impl()
467 { _M_initialize_map(__num_elements); }
468
469 _Deque_base(const allocator_type& __a, size_t __num_elements)
470 : _M_impl(__a)
471 { _M_initialize_map(__num_elements); }
472
473 _Deque_base(const allocator_type& __a)
474 : _M_impl(__a)
475 { /* Caller must initialize map. */ }
476
477#if __cplusplus >= 201103L
478 _Deque_base(_Deque_base&& __x)
479 : _M_impl(std::move(__x._M_get_Tp_allocator()))
480 {
481 _M_initialize_map(0);
482 if (__x._M_impl._M_map)
483 this->_M_impl._M_swap_data(__x._M_impl);
484 }
485
486 _Deque_base(_Deque_base&& __x, const allocator_type& __a)
487 : _M_impl(std::move(__x._M_impl), _Tp_alloc_type(__a))
488 { __x._M_initialize_map(0); }
489
490 _Deque_base(_Deque_base&& __x, const allocator_type& __a, size_t __n)
491 : _M_impl(__a)
492 {
493 if (__x.get_allocator() == __a)
494 {
495 if (__x._M_impl._M_map)
496 {
497 _M_initialize_map(0);
498 this->_M_impl._M_swap_data(__x._M_impl);
499 }
500 }
501 else
502 {
503 _M_initialize_map(__n);
504 }
505 }
506#endif
507
508 ~_Deque_base() _GLIBCXX_NOEXCEPT;
509
510 typedef typename iterator::_Map_pointer _Map_pointer;
511
512 struct _Deque_impl_data
513 {
514 _Map_pointer _M_map;
515 size_t _M_map_size;
516 iterator _M_start;
517 iterator _M_finish;
518
519 _Deque_impl_data() _GLIBCXX_NOEXCEPT
520 : _M_map(), _M_map_size(), _M_start(), _M_finish()
521 { }
522
523#if __cplusplus >= 201103L
524 _Deque_impl_data(const _Deque_impl_data&) = default;
525 _Deque_impl_data&
526 operator=(const _Deque_impl_data&) = default;
527
528 _Deque_impl_data(_Deque_impl_data&& __x) noexcept
529 : _Deque_impl_data(__x)
530 { __x = _Deque_impl_data(); }
531#endif
532
533 void
534 _M_swap_data(_Deque_impl_data& __x) _GLIBCXX_NOEXCEPT
535 {
536 // Do not use std::swap(_M_start, __x._M_start), etc as it loses
537 // information used by TBAA.
538 std::swap(*this, __x);
539 }
540 };
541
542 // This struct encapsulates the implementation of the std::deque
543 // standard container and at the same time makes use of the EBO
544 // for empty allocators.
545 struct _Deque_impl
546 : public _Tp_alloc_type, public _Deque_impl_data
547 {
548 _Deque_impl() _GLIBCXX_NOEXCEPT_IF(
549 is_nothrow_default_constructible<_Tp_alloc_type>::value)
550 : _Tp_alloc_type()
551 { }
552
553 _Deque_impl(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
554 : _Tp_alloc_type(__a)
555 { }
556
557#if __cplusplus >= 201103L
558 _Deque_impl(_Deque_impl&&) = default;
559
560 _Deque_impl(_Tp_alloc_type&& __a) noexcept
561 : _Tp_alloc_type(std::move(__a))
562 { }
563
564 _Deque_impl(_Deque_impl&& __d, _Tp_alloc_type&& __a)
565 : _Tp_alloc_type(std::move(__a)), _Deque_impl_data(std::move(__d))
566 { }
567#endif
568 };
569
570 _Tp_alloc_type&
571 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
572 { return this->_M_impl; }
573
574 const _Tp_alloc_type&
575 _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
576 { return this->_M_impl; }
577
578 _Map_alloc_type
579 _M_get_map_allocator() const _GLIBCXX_NOEXCEPT
580 { return _Map_alloc_type(_M_get_Tp_allocator()); }
581
582 _Ptr
583 _M_allocate_node()
584 {
585 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;
586 return _Traits::allocate(_M_impl, __deque_buf_size(sizeof(_Tp)));
587 }
588
589 void
590 _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
591 {
592 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;
593 _Traits::deallocate(_M_impl, __p, __deque_buf_size(sizeof(_Tp)));
594 }
595
596 _Map_pointer
597 _M_allocate_map(size_t __n)
598 {
599 _Map_alloc_type __map_alloc = _M_get_map_allocator();
600 return _Map_alloc_traits::allocate(__map_alloc, __n);
601 }
602
603 void
604 _M_deallocate_map(_Map_pointer __p, size_t __n) _GLIBCXX_NOEXCEPT
605 {
606 _Map_alloc_type __map_alloc = _M_get_map_allocator();
607 _Map_alloc_traits::deallocate(__map_alloc, __p, __n);
608 }
609
610 void _M_initialize_map(size_t);
611 void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
612 void _M_destroy_nodes(_Map_pointer __nstart,
613 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT;
614 enum { _S_initial_map_size = 8 };
615
616 _Deque_impl _M_impl;
617 };
618
619 template<typename _Tp, typename _Alloc>
620 _Deque_base<_Tp, _Alloc>::
621 ~_Deque_base() _GLIBCXX_NOEXCEPT
622 {
623 if (this->_M_impl._M_map)
624 {
625 _M_destroy_nodes(this->_M_impl._M_start._M_node,
626 this->_M_impl._M_finish._M_node + 1);
627 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
628 }
629 }
630
631 /**
632 * @brief Layout storage.
633 * @param __num_elements The count of T's for which to allocate space
634 * at first.
635 *
636 * The initial underlying memory layout is a bit complicated...
637 */
638 template<typename _Tp, typename _Alloc>
639 void
640 _Deque_base<_Tp, _Alloc>::
641 _M_initialize_map(size_t __num_elements)
642 {
643 const size_t __num_nodes = (__num_elements / __deque_buf_size(sizeof(_Tp))
644 + 1);
645
646 this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
647 size_t(__num_nodes + 2));
648 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
649
650 // For "small" maps (needing less than _M_map_size nodes), allocation
651 // starts in the middle elements and grows outwards. So nstart may be
652 // the beginning of _M_map, but for small maps it may be as far in as
653 // _M_map+3.
654
655 _Map_pointer __nstart = (this->_M_impl._M_map
656 + (this->_M_impl._M_map_size - __num_nodes) / 2);
657 _Map_pointer __nfinish = __nstart + __num_nodes;
658
659 __try
660 { _M_create_nodes(__nstart, __nfinish); }
661 __catch(...)
662 {
663 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
664 this->_M_impl._M_map = _Map_pointer();
665 this->_M_impl._M_map_size = 0;
666 __throw_exception_again;
667 }
668
669 this->_M_impl._M_start._M_set_node(__nstart);
670 this->_M_impl._M_finish._M_set_node(__nfinish - 1);
671 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
672 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
673 + __num_elements
674 % __deque_buf_size(sizeof(_Tp)));
675 }
676
677 template<typename _Tp, typename _Alloc>
678 void
679 _Deque_base<_Tp, _Alloc>::
680 _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish)
681 {
682 _Map_pointer __cur;
683 __try
684 {
685 for (__cur = __nstart; __cur < __nfinish; ++__cur)
686 *__cur = this->_M_allocate_node();
687 }
688 __catch(...)
689 {
690 _M_destroy_nodes(__nstart, __cur);
691 __throw_exception_again;
692 }
693 }
694
695 template<typename _Tp, typename _Alloc>
696 void
697 _Deque_base<_Tp, _Alloc>::
698 _M_destroy_nodes(_Map_pointer __nstart,
699 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
700 {
701 for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
702 _M_deallocate_node(*__n);
703 }
704
705 /**
706 * @brief A standard container using fixed-size memory allocation and
707 * constant-time manipulation of elements at either end.
708 *
709 * @ingroup sequences
710 *
711 * @tparam _Tp Type of element.
712 * @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
713 *
714 * Meets the requirements of a <a href="tables.html#65">container</a>, a
715 * <a href="tables.html#66">reversible container</a>, and a
716 * <a href="tables.html#67">sequence</a>, including the
717 * <a href="tables.html#68">optional sequence requirements</a>.
718 *
719 * In previous HP/SGI versions of deque, there was an extra template
720 * parameter so users could control the node size. This extension turned
721 * out to violate the C++ standard (it can be detected using template
722 * template parameters), and it was removed.
723 *
724 * Here's how a deque<Tp> manages memory. Each deque has 4 members:
725 *
726 * - Tp** _M_map
727 * - size_t _M_map_size
728 * - iterator _M_start, _M_finish
729 *
730 * map_size is at least 8. %map is an array of map_size
731 * pointers-to-@a nodes. (The name %map has nothing to do with the
732 * std::map class, and @b nodes should not be confused with
733 * std::list's usage of @a node.)
734 *
735 * A @a node has no specific type name as such, but it is referred
736 * to as @a node in this file. It is a simple array-of-Tp. If Tp
737 * is very large, there will be one Tp element per node (i.e., an
738 * @a array of one). For non-huge Tp's, node size is inversely
739 * related to Tp size: the larger the Tp, the fewer Tp's will fit
740 * in a node. The goal here is to keep the total size of a node
741 * relatively small and constant over different Tp's, to improve
742 * allocator efficiency.
743 *
744 * Not every pointer in the %map array will point to a node. If
745 * the initial number of elements in the deque is small, the
746 * /middle/ %map pointers will be valid, and the ones at the edges
747 * will be unused. This same situation will arise as the %map
748 * grows: available %map pointers, if any, will be on the ends. As
749 * new nodes are created, only a subset of the %map's pointers need
750 * to be copied @a outward.
751 *
752 * Class invariants:
753 * - For any nonsingular iterator i:
754 * - i.node points to a member of the %map array. (Yes, you read that
755 * correctly: i.node does not actually point to a node.) The member of
756 * the %map array is what actually points to the node.
757 * - i.first == *(i.node) (This points to the node (first Tp element).)
758 * - i.last == i.first + node_size
759 * - i.cur is a pointer in the range [i.first, i.last). NOTE:
760 * the implication of this is that i.cur is always a dereferenceable
761 * pointer, even if i is a past-the-end iterator.
762 * - Start and Finish are always nonsingular iterators. NOTE: this
763 * means that an empty deque must have one node, a deque with <N
764 * elements (where N is the node buffer size) must have one node, a
765 * deque with N through (2N-1) elements must have two nodes, etc.
766 * - For every node other than start.node and finish.node, every
767 * element in the node is an initialized object. If start.node ==
768 * finish.node, then [start.cur, finish.cur) are initialized
769 * objects, and the elements outside that range are uninitialized
770 * storage. Otherwise, [start.cur, start.last) and [finish.first,
771 * finish.cur) are initialized objects, and [start.first, start.cur)
772 * and [finish.cur, finish.last) are uninitialized storage.
773 * - [%map, %map + map_size) is a valid, non-empty range.
774 * - [start.node, finish.node] is a valid range contained within
775 * [%map, %map + map_size).
776 * - A pointer in the range [%map, %map + map_size) points to an allocated
777 * node if and only if the pointer is in the range
778 * [start.node, finish.node].
779 *
780 * Here's the magic: nothing in deque is @b aware of the discontiguous
781 * storage!
782 *
783 * The memory setup and layout occurs in the parent, _Base, and the iterator
784 * class is entirely responsible for @a leaping from one node to the next.
785 * All the implementation routines for deque itself work only through the
786 * start and finish iterators. This keeps the routines simple and sane,
787 * and we can use other standard algorithms as well.
788 */
789 template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
790 class deque : protected _Deque_base<_Tp, _Alloc>
791 {
792#ifdef _GLIBCXX_CONCEPT_CHECKS
793 // concept requirements
794 typedef typename _Alloc::value_type _Alloc_value_type;
795# if __cplusplus < 201103L
796 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
797# endif
798 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
799#endif
800
801#if __cplusplus >= 201103L
802 static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value,
803 "std::deque must have a non-const, non-volatile value_type");
804# if __cplusplus > 201703L || defined __STRICT_ANSI__
805 static_assert(is_same<typename _Alloc::value_type, _Tp>::value,
806 "std::deque must have the same value_type as its allocator");
807# endif
808#endif
809
810 typedef _Deque_base<_Tp, _Alloc> _Base;
811 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
812 typedef typename _Base::_Alloc_traits _Alloc_traits;
813 typedef typename _Base::_Map_pointer _Map_pointer;
814
815 public:
816 typedef _Tp value_type;
817 typedef typename _Alloc_traits::pointer pointer;
818 typedef typename _Alloc_traits::const_pointer const_pointer;
819 typedef typename _Alloc_traits::reference reference;
820 typedef typename _Alloc_traits::const_reference const_reference;
821 typedef typename _Base::iterator iterator;
822 typedef typename _Base::const_iterator const_iterator;
823 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
824 typedef std::reverse_iterator<iterator> reverse_iterator;
825 typedef size_t size_type;
826 typedef ptrdiff_t difference_type;
827 typedef _Alloc allocator_type;
828
829 private:
830 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
831 { return __deque_buf_size(sizeof(_Tp)); }
832
833 // Functions controlling memory layout, and nothing else.
834 using _Base::_M_initialize_map;
835 using _Base::_M_create_nodes;
836 using _Base::_M_destroy_nodes;
837 using _Base::_M_allocate_node;
838 using _Base::_M_deallocate_node;
839 using _Base::_M_allocate_map;
840 using _Base::_M_deallocate_map;
841 using _Base::_M_get_Tp_allocator;
842
843 /**
844 * A total of four data members accumulated down the hierarchy.
845 * May be accessed via _M_impl.*
846 */
847 using _Base::_M_impl;
848
849 public:
850 // [23.2.1.1] construct/copy/destroy
851 // (assign() and get_allocator() are also listed in this section)
852
853 /**
854 * @brief Creates a %deque with no elements.
855 */
856#if __cplusplus >= 201103L
857 deque() = default;
858#else
859 deque() { }
860#endif
861
862 /**
863 * @brief Creates a %deque with no elements.
864 * @param __a An allocator object.
865 */
866 explicit
867 deque(const allocator_type& __a)
868 : _Base(__a, 0) { }
869
870#if __cplusplus >= 201103L
871 /**
872 * @brief Creates a %deque with default constructed elements.
873 * @param __n The number of elements to initially create.
874 * @param __a An allocator.
875 *
876 * This constructor fills the %deque with @a n default
877 * constructed elements.
878 */
879 explicit
880 deque(size_type __n, const allocator_type& __a = allocator_type())
881 : _Base(__a, _S_check_init_len(__n, __a))
882 { _M_default_initialize(); }
883
884 /**
885 * @brief Creates a %deque with copies of an exemplar element.
886 * @param __n The number of elements to initially create.
887 * @param __value An element to copy.
888 * @param __a An allocator.
889 *
890 * This constructor fills the %deque with @a __n copies of @a __value.
891 */
892 deque(size_type __n, const value_type& __value,
893 const allocator_type& __a = allocator_type())
894 : _Base(__a, _S_check_init_len(__n, __a))
895 { _M_fill_initialize(__value); }
896#else
897 /**
898 * @brief Creates a %deque with copies of an exemplar element.
899 * @param __n The number of elements to initially create.
900 * @param __value An element to copy.
901 * @param __a An allocator.
902 *
903 * This constructor fills the %deque with @a __n copies of @a __value.
904 */
905 explicit
906 deque(size_type __n, const value_type& __value = value_type(),
907 const allocator_type& __a = allocator_type())
908 : _Base(__a, _S_check_init_len(__n, __a))
909 { _M_fill_initialize(__value); }
910#endif
911
912 /**
913 * @brief %Deque copy constructor.
914 * @param __x A %deque of identical element and allocator types.
915 *
916 * The newly-created %deque uses a copy of the allocator object used
917 * by @a __x (unless the allocator traits dictate a different object).
918 */
919 deque(const deque& __x)
920 : _Base(_Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()),
921 __x.size())
922 { std::__uninitialized_copy_a(__x.begin(), __x.end(),
923 this->_M_impl._M_start,
924 _M_get_Tp_allocator()); }
925
926#if __cplusplus >= 201103L
927 /**
928 * @brief %Deque move constructor.
929 *
930 * The newly-created %deque contains the exact contents of the
931 * moved instance.
932 * The contents of the moved instance are a valid, but unspecified
933 * %deque.
934 */
935 deque(deque&&) = default;
936
937 /// Copy constructor with alternative allocator
938 deque(const deque& __x, const __type_identity_t<allocator_type>& __a)
939 : _Base(__a, __x.size())
940 { std::__uninitialized_copy_a(__x.begin(), __x.end(),
941 this->_M_impl._M_start,
942 _M_get_Tp_allocator()); }
943
944 /// Move constructor with alternative allocator
945 deque(deque&& __x, const __type_identity_t<allocator_type>& __a)
946 : deque(std::move(__x), __a, typename _Alloc_traits::is_always_equal{})
947 { }
948
949 private:
950 deque(deque&& __x, const allocator_type& __a, true_type)
951 : _Base(std::move(__x), __a)
952 { }
953
954 deque(deque&& __x, const allocator_type& __a, false_type)
955 : _Base(std::move(__x), __a, __x.size())
956 {
957 if (__x.get_allocator() != __a && !__x.empty())
958 {
959 std::__uninitialized_move_a(__x.begin(), __x.end(),
960 this->_M_impl._M_start,
961 _M_get_Tp_allocator());
962 __x.clear();
963 }
964 }
965
966 public:
967 /**
968 * @brief Builds a %deque from an initializer list.
969 * @param __l An initializer_list.
970 * @param __a An allocator object.
971 *
972 * Create a %deque consisting of copies of the elements in the
973 * initializer_list @a __l.
974 *
975 * This will call the element type's copy constructor N times
976 * (where N is __l.size()) and do no memory reallocation.
977 */
978 deque(initializer_list<value_type> __l,
979 const allocator_type& __a = allocator_type())
980 : _Base(__a)
981 {
982 _M_range_initialize(__l.begin(), __l.end(),
983 random_access_iterator_tag());
984 }
985#endif
986
987 /**
988 * @brief Builds a %deque from a range.
989 * @param __first An input iterator.
990 * @param __last An input iterator.
991 * @param __a An allocator object.
992 *
993 * Create a %deque consisting of copies of the elements from [__first,
994 * __last).
995 *
996 * If the iterators are forward, bidirectional, or random-access, then
997 * this will call the elements' copy constructor N times (where N is
998 * distance(__first,__last)) and do no memory reallocation. But if only
999 * input iterators are used, then this will do at most 2N calls to the
1000 * copy constructor, and logN memory reallocations.
1001 */
1002#if __cplusplus >= 201103L
1003 template<typename _InputIterator,
1004 typename = std::_RequireInputIter<_InputIterator>>
1005 deque(_InputIterator __first, _InputIterator __last,
1006 const allocator_type& __a = allocator_type())
1007 : _Base(__a)
1008 {
1009 _M_range_initialize(__first, __last,
1010 std::__iterator_category(__first));
1011 }
1012#else
1013 template<typename _InputIterator>
1014 deque(_InputIterator __first, _InputIterator __last,
1015 const allocator_type& __a = allocator_type())
1016 : _Base(__a)
1017 {
1018 // Check whether it's an integral type. If so, it's not an iterator.
1019 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1020 _M_initialize_dispatch(__first, __last, _Integral());
1021 }
1022#endif
1023
1024#if __glibcxx_containers_ranges // C++ >= 23
1025 /**
1026 * @brief Construct a deque from a range.
1027 * @param __rg A range of values that are convertible to `value_type`.
1028 * @since C++23
1029 */
1030 template<__detail::__container_compatible_range<_Tp> _Rg>
1031 deque(from_range_t, _Rg&& __rg, const allocator_type& __a = _Alloc())
1032 : deque(__a)
1033 { append_range(std::forward<_Rg>(__rg)); }
1034#endif
1035
1036 /**
1037 * The dtor only erases the elements, and note that if the elements
1038 * themselves are pointers, the pointed-to memory is not touched in any
1039 * way. Managing the pointer is the user's responsibility.
1040 */
1041 ~deque()
1042 { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); }
1043
1044 /**
1045 * @brief %Deque assignment operator.
1046 * @param __x A %deque of identical element and allocator types.
1047 *
1048 * All the elements of @a x are copied.
1049 *
1050 * The newly-created %deque uses a copy of the allocator object used
1051 * by @a __x (unless the allocator traits dictate a different object).
1052 */
1053 deque&
1054 operator=(const deque& __x);
1055
1056#if __cplusplus >= 201103L
1057 /**
1058 * @brief %Deque move assignment operator.
1059 * @param __x A %deque of identical element and allocator types.
1060 *
1061 * The contents of @a __x are moved into this deque (without copying,
1062 * if the allocators permit it).
1063 * @a __x is a valid, but unspecified %deque.
1064 */
1065 deque&
1066 operator=(deque&& __x) noexcept(_Alloc_traits::_S_always_equal())
1067 {
1068 using __always_equal = typename _Alloc_traits::is_always_equal;
1069 _M_move_assign1(std::move(__x), __always_equal{});
1070 return *this;
1071 }
1072
1073 /**
1074 * @brief Assigns an initializer list to a %deque.
1075 * @param __l An initializer_list.
1076 *
1077 * This function fills a %deque with copies of the elements in the
1078 * initializer_list @a __l.
1079 *
1080 * Note that the assignment completely changes the %deque and that the
1081 * resulting %deque's size is the same as the number of elements
1082 * assigned.
1083 */
1084 deque&
1085 operator=(initializer_list<value_type> __l)
1086 {
1087 _M_assign_aux(__l.begin(), __l.end(),
1088 random_access_iterator_tag());
1089 return *this;
1090 }
1091#endif
1092
1093 /**
1094 * @brief Assigns a given value to a %deque.
1095 * @param __n Number of elements to be assigned.
1096 * @param __val Value to be assigned.
1097 *
1098 * This function fills a %deque with @a n copies of the given
1099 * value. Note that the assignment completely changes the
1100 * %deque and that the resulting %deque's size is the same as
1101 * the number of elements assigned.
1102 */
1103 void
1104 assign(size_type __n, const value_type& __val)
1105 { _M_fill_assign(__n, __val); }
1106
1107 /**
1108 * @brief Assigns a range to a %deque.
1109 * @param __first An input iterator.
1110 * @param __last An input iterator.
1111 *
1112 * This function fills a %deque with copies of the elements in the
1113 * range [__first,__last).
1114 *
1115 * Note that the assignment completely changes the %deque and that the
1116 * resulting %deque's size is the same as the number of elements
1117 * assigned.
1118 */
1119#if __cplusplus >= 201103L
1120 template<typename _InputIterator,
1121 typename = std::_RequireInputIter<_InputIterator>>
1122 void
1123 assign(_InputIterator __first, _InputIterator __last)
1124 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1125#else
1126 template<typename _InputIterator>
1127 void
1128 assign(_InputIterator __first, _InputIterator __last)
1129 {
1130 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1131 _M_assign_dispatch(__first, __last, _Integral());
1132 }
1133#endif
1134
1135#if __cplusplus >= 201103L
1136 /**
1137 * @brief Assigns an initializer list to a %deque.
1138 * @param __l An initializer_list.
1139 *
1140 * This function fills a %deque with copies of the elements in the
1141 * initializer_list @a __l.
1142 *
1143 * Note that the assignment completely changes the %deque and that the
1144 * resulting %deque's size is the same as the number of elements
1145 * assigned.
1146 */
1147 void
1148 assign(initializer_list<value_type> __l)
1149 { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); }
1150#endif
1151
1152#if __glibcxx_containers_ranges // C++ >= 23
1153 /**
1154 * @brief Assign a range to the deque.
1155 * @param __rg A range of values that are convertible to `value_type`.
1156 * @pre `__rg` and `*this` do not overlap.
1157 * @since C++23
1158 */
1159 template<__detail::__container_compatible_range<_Tp> _Rg>
1160 constexpr void
1161 assign_range(_Rg&& __rg)
1162 {
1163 static_assert(assignable_from<_Tp&, ranges::range_reference_t<_Rg>>);
1164
1165 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1166 {
1167 const size_type __n(ranges::distance(__rg));
1168 if (__n <= size())
1169 {
1170 auto __res = ranges::copy(__rg, begin());
1171 return _M_erase_at_end(__res.out);
1172 }
1173
1174 auto __rest = ranges::copy_n(ranges::begin(__rg), size(),
1175 begin()).in;
1176 _M_range_append(std::move(__rest), ranges::end(__rg),
1177 __n - size());
1178 }
1179 else
1180 {
1181 auto __first = ranges::begin(__rg);
1182 const auto __last = ranges::end(__rg);
1183 for (iterator __it = begin(), __end = end();
1184 __it != __end; (void)++__first, ++__it)
1185 {
1186 if (__first == __last)
1187 return _M_erase_at_end(__it);
1188
1189 *__it = *__first;
1190 }
1191
1192 for (; __first != __last; ++__first)
1193 emplace_back(*__first);
1194 }
1195 }
1196#endif // containers_ranges
1197
1198
1199 /// Get a copy of the memory allocation object.
1200 _GLIBCXX_NODISCARD
1201 allocator_type
1202 get_allocator() const _GLIBCXX_NOEXCEPT
1203 { return _Base::get_allocator(); }
1204
1205 // iterators
1206 /**
1207 * Returns a read/write iterator that points to the first element in the
1208 * %deque. Iteration is done in ordinary element order.
1209 */
1210 _GLIBCXX_NODISCARD
1211 iterator
1212 begin() _GLIBCXX_NOEXCEPT
1213 { return this->_M_impl._M_start; }
1214
1215 /**
1216 * Returns a read-only (constant) iterator that points to the first
1217 * element in the %deque. Iteration is done in ordinary element order.
1218 */
1219 _GLIBCXX_NODISCARD
1220 const_iterator
1221 begin() const _GLIBCXX_NOEXCEPT
1222 { return this->_M_impl._M_start; }
1223
1224 /**
1225 * Returns a read/write iterator that points one past the last
1226 * element in the %deque. Iteration is done in ordinary
1227 * element order.
1228 */
1229 _GLIBCXX_NODISCARD
1230 iterator
1231 end() _GLIBCXX_NOEXCEPT
1232 { return this->_M_impl._M_finish; }
1233
1234 /**
1235 * Returns a read-only (constant) iterator that points one past
1236 * the last element in the %deque. Iteration is done in
1237 * ordinary element order.
1238 */
1239 _GLIBCXX_NODISCARD
1240 const_iterator
1241 end() const _GLIBCXX_NOEXCEPT
1242 { return this->_M_impl._M_finish; }
1243
1244 /**
1245 * Returns a read/write reverse iterator that points to the
1246 * last element in the %deque. Iteration is done in reverse
1247 * element order.
1248 */
1249 _GLIBCXX_NODISCARD
1250 reverse_iterator
1251 rbegin() _GLIBCXX_NOEXCEPT
1252 { return reverse_iterator(this->_M_impl._M_finish); }
1253
1254 /**
1255 * Returns a read-only (constant) reverse iterator that points
1256 * to the last element in the %deque. Iteration is done in
1257 * reverse element order.
1258 */
1259 _GLIBCXX_NODISCARD
1260 const_reverse_iterator
1261 rbegin() const _GLIBCXX_NOEXCEPT
1262 { return const_reverse_iterator(this->_M_impl._M_finish); }
1263
1264 /**
1265 * Returns a read/write reverse iterator that points to one
1266 * before the first element in the %deque. Iteration is done
1267 * in reverse element order.
1268 */
1269 _GLIBCXX_NODISCARD
1270 reverse_iterator
1271 rend() _GLIBCXX_NOEXCEPT
1272 { return reverse_iterator(this->_M_impl._M_start); }
1273
1274 /**
1275 * Returns a read-only (constant) reverse iterator that points
1276 * to one before the first element in the %deque. Iteration is
1277 * done in reverse element order.
1278 */
1279 _GLIBCXX_NODISCARD
1280 const_reverse_iterator
1281 rend() const _GLIBCXX_NOEXCEPT
1282 { return const_reverse_iterator(this->_M_impl._M_start); }
1283
1284#if __cplusplus >= 201103L
1285 /**
1286 * Returns a read-only (constant) iterator that points to the first
1287 * element in the %deque. Iteration is done in ordinary element order.
1288 */
1289 [[__nodiscard__]]
1290 const_iterator
1291 cbegin() const noexcept
1292 { return this->_M_impl._M_start; }
1293
1294 /**
1295 * Returns a read-only (constant) iterator that points one past
1296 * the last element in the %deque. Iteration is done in
1297 * ordinary element order.
1298 */
1299 [[__nodiscard__]]
1300 const_iterator
1301 cend() const noexcept
1302 { return this->_M_impl._M_finish; }
1303
1304 /**
1305 * Returns a read-only (constant) reverse iterator that points
1306 * to the last element in the %deque. Iteration is done in
1307 * reverse element order.
1308 */
1309 [[__nodiscard__]]
1310 const_reverse_iterator
1311 crbegin() const noexcept
1312 { return const_reverse_iterator(this->_M_impl._M_finish); }
1313
1314 /**
1315 * Returns a read-only (constant) reverse iterator that points
1316 * to one before the first element in the %deque. Iteration is
1317 * done in reverse element order.
1318 */
1319 [[__nodiscard__]]
1320 const_reverse_iterator
1321 crend() const noexcept
1322 { return const_reverse_iterator(this->_M_impl._M_start); }
1323#endif
1324
1325 // [23.2.1.2] capacity
1326 /** Returns the number of elements in the %deque. */
1327 _GLIBCXX_NODISCARD
1328 size_type
1329 size() const _GLIBCXX_NOEXCEPT
1330 {
1331 size_type __sz = this->_M_impl._M_finish - this->_M_impl._M_start;
1332 if (__sz > max_size ())
1333 __builtin_unreachable();
1334 return __sz;
1335 }
1336
1337 /** Returns the size() of the largest possible %deque. */
1338 _GLIBCXX_NODISCARD
1339 size_type
1340 max_size() const _GLIBCXX_NOEXCEPT
1341 { return _S_max_size(_M_get_Tp_allocator()); }
1342
1343#if __cplusplus >= 201103L
1344 /**
1345 * @brief Resizes the %deque to the specified number of elements.
1346 * @param __new_size Number of elements the %deque should contain.
1347 *
1348 * This function will %resize the %deque to the specified
1349 * number of elements. If the number is smaller than the
1350 * %deque's current size the %deque is truncated, otherwise
1351 * default constructed elements are appended.
1352 */
1353 void
1354 resize(size_type __new_size)
1355 {
1356 const size_type __len = size();
1357 if (__new_size > __len)
1358 _M_default_append(__new_size - __len);
1359 else if (__new_size < __len)
1360 _M_erase_at_end(this->_M_impl._M_start
1361 + difference_type(__new_size));
1362 }
1363
1364 /**
1365 * @brief Resizes the %deque to the specified number of elements.
1366 * @param __new_size Number of elements the %deque should contain.
1367 * @param __x Data with which new elements should be populated.
1368 *
1369 * This function will %resize the %deque to the specified
1370 * number of elements. If the number is smaller than the
1371 * %deque's current size the %deque is truncated, otherwise the
1372 * %deque is extended and new elements are populated with given
1373 * data.
1374 */
1375 void
1376 resize(size_type __new_size, const value_type& __x)
1377#else
1378 /**
1379 * @brief Resizes the %deque to the specified number of elements.
1380 * @param __new_size Number of elements the %deque should contain.
1381 * @param __x Data with which new elements should be populated.
1382 *
1383 * This function will %resize the %deque to the specified
1384 * number of elements. If the number is smaller than the
1385 * %deque's current size the %deque is truncated, otherwise the
1386 * %deque is extended and new elements are populated with given
1387 * data.
1388 */
1389 void
1390 resize(size_type __new_size, value_type __x = value_type())
1391#endif
1392 {
1393 const size_type __len = size();
1394 if (__new_size > __len)
1395 _M_fill_insert(this->_M_impl._M_finish, __new_size - __len, __x);
1396 else if (__new_size < __len)
1397 _M_erase_at_end(this->_M_impl._M_start
1398 + difference_type(__new_size));
1399 }
1400
1401#if __cplusplus >= 201103L
1402 /** A non-binding request to reduce memory use. */
1403 void
1404 shrink_to_fit() noexcept
1405 { _M_shrink_to_fit(); }
1406#endif
1407
1408 /**
1409 * Returns true if the %deque is empty. (Thus begin() would
1410 * equal end().)
1411 */
1412 _GLIBCXX_NODISCARD bool
1413 empty() const _GLIBCXX_NOEXCEPT
1414 { return this->_M_impl._M_finish == this->_M_impl._M_start; }
1415
1416 // element access
1417 /**
1418 * @brief Subscript access to the data contained in the %deque.
1419 * @param __n The index of the element for which data should be
1420 * accessed.
1421 * @return Read/write reference to data.
1422 *
1423 * This operator allows for easy, array-style, data access.
1424 * Note that data access with this operator is unchecked and
1425 * out_of_range lookups are not defined. (For checked lookups
1426 * see at().)
1427 */
1428 _GLIBCXX_NODISCARD
1429 reference
1430 operator[](size_type __n) _GLIBCXX_NOEXCEPT
1431 {
1432 __glibcxx_requires_subscript(__n);
1433 return this->_M_impl._M_start[difference_type(__n)];
1434 }
1435
1436 /**
1437 * @brief Subscript access to the data contained in the %deque.
1438 * @param __n The index of the element for which data should be
1439 * accessed.
1440 * @return Read-only (constant) reference to data.
1441 *
1442 * This operator allows for easy, array-style, data access.
1443 * Note that data access with this operator is unchecked and
1444 * out_of_range lookups are not defined. (For checked lookups
1445 * see at().)
1446 */
1447 _GLIBCXX_NODISCARD
1448 const_reference
1449 operator[](size_type __n) const _GLIBCXX_NOEXCEPT
1450 {
1451 __glibcxx_requires_subscript(__n);
1452 return this->_M_impl._M_start[difference_type(__n)];
1453 }
1454
1455 protected:
1456 /// Safety check used only from at().
1457 void
1458 _M_range_check(size_type __n) const
1459 {
1460 if (__n >= this->size())
1461 __throw_out_of_range_fmt(__N("deque::_M_range_check: __n "
1462 "(which is %zu)>= this->size() "
1463 "(which is %zu)"),
1464 __n, this->size());
1465 }
1466
1467 public:
1468 /**
1469 * @brief Provides access to the data contained in the %deque.
1470 * @param __n The index of the element for which data should be
1471 * accessed.
1472 * @return Read/write reference to data.
1473 * @throw std::out_of_range If @a __n is an invalid index.
1474 *
1475 * This function provides for safer data access. The parameter
1476 * is first checked that it is in the range of the deque. The
1477 * function throws out_of_range if the check fails.
1478 */
1479 reference
1480 at(size_type __n)
1481 {
1482 _M_range_check(__n);
1483 return (*this)[__n];
1484 }
1485
1486 /**
1487 * @brief Provides access to the data contained in the %deque.
1488 * @param __n The index of the element for which data should be
1489 * accessed.
1490 * @return Read-only (constant) reference to data.
1491 * @throw std::out_of_range If @a __n is an invalid index.
1492 *
1493 * This function provides for safer data access. The parameter is first
1494 * checked that it is in the range of the deque. The function throws
1495 * out_of_range if the check fails.
1496 */
1497 const_reference
1498 at(size_type __n) const
1499 {
1500 _M_range_check(__n);
1501 return (*this)[__n];
1502 }
1503
1504 /**
1505 * Returns a read/write reference to the data at the first
1506 * element of the %deque.
1507 */
1508 _GLIBCXX_NODISCARD
1509 reference
1510 front() _GLIBCXX_NOEXCEPT
1511 {
1512 __glibcxx_requires_nonempty();
1513 return *begin();
1514 }
1515
1516 /**
1517 * Returns a read-only (constant) reference to the data at the first
1518 * element of the %deque.
1519 */
1520 _GLIBCXX_NODISCARD
1521 const_reference
1522 front() const _GLIBCXX_NOEXCEPT
1523 {
1524 __glibcxx_requires_nonempty();
1525 return *begin();
1526 }
1527
1528 /**
1529 * Returns a read/write reference to the data at the last element of the
1530 * %deque.
1531 */
1532 _GLIBCXX_NODISCARD
1533 reference
1534 back() _GLIBCXX_NOEXCEPT
1535 {
1536 __glibcxx_requires_nonempty();
1537 iterator __tmp = end();
1538 --__tmp;
1539 return *__tmp;
1540 }
1541
1542 /**
1543 * Returns a read-only (constant) reference to the data at the last
1544 * element of the %deque.
1545 */
1546 _GLIBCXX_NODISCARD
1547 const_reference
1548 back() const _GLIBCXX_NOEXCEPT
1549 {
1550 __glibcxx_requires_nonempty();
1551 const_iterator __tmp = end();
1552 --__tmp;
1553 return *__tmp;
1554 }
1555
1556 // [23.2.1.2] modifiers
1557 /**
1558 * @brief Add data to the front of the %deque.
1559 * @param __x Data to be added.
1560 *
1561 * This is a typical stack operation. The function creates an
1562 * element at the front of the %deque and assigns the given
1563 * data to it. Due to the nature of a %deque this operation
1564 * can be done in constant time.
1565 */
1566 void
1567 push_front(const value_type& __x)
1568 {
1569 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1570 {
1571 _Alloc_traits::construct(this->_M_impl,
1572 this->_M_impl._M_start._M_cur - 1,
1573 __x);
1574 --this->_M_impl._M_start._M_cur;
1575 }
1576 else
1577 _M_push_front_aux(__x);
1578 }
1579
1580#if __cplusplus >= 201103L
1581 void
1582 push_front(value_type&& __x)
1583 { emplace_front(std::move(__x)); }
1584
1585 template<typename... _Args>
1586#if __cplusplus > 201402L
1587 reference
1588#else
1589 void
1590#endif
1591 emplace_front(_Args&&... __args);
1592#endif
1593
1594 /**
1595 * @brief Add data to the end of the %deque.
1596 * @param __x Data to be added.
1597 *
1598 * This is a typical stack operation. The function creates an
1599 * element at the end of the %deque and assigns the given data
1600 * to it. Due to the nature of a %deque this operation can be
1601 * done in constant time.
1602 */
1603 void
1604 push_back(const value_type& __x)
1605 {
1606 if (this->_M_impl._M_finish._M_cur
1607 != this->_M_impl._M_finish._M_last - 1)
1608 {
1609 _Alloc_traits::construct(this->_M_impl,
1610 this->_M_impl._M_finish._M_cur, __x);
1611 ++this->_M_impl._M_finish._M_cur;
1612 }
1613 else
1614 _M_push_back_aux(__x);
1615 }
1616
1617#if __cplusplus >= 201103L
1618 void
1619 push_back(value_type&& __x)
1620 { emplace_back(std::move(__x)); }
1621
1622 template<typename... _Args>
1623#if __cplusplus > 201402L
1624 reference
1625#else
1626 void
1627#endif
1628 emplace_back(_Args&&... __args);
1629#endif
1630
1631 /**
1632 * @brief Removes first element.
1633 *
1634 * This is a typical stack operation. It shrinks the %deque by one.
1635 *
1636 * Note that no data is returned, and if the first element's data is
1637 * needed, it should be retrieved before pop_front() is called.
1638 */
1639 void
1640 pop_front() _GLIBCXX_NOEXCEPT
1641 {
1642 __glibcxx_requires_nonempty();
1643 if (this->_M_impl._M_start._M_cur
1644 != this->_M_impl._M_start._M_last - 1)
1645 {
1646 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1647 this->_M_impl._M_start._M_cur);
1648 ++this->_M_impl._M_start._M_cur;
1649 }
1650 else
1651 _M_pop_front_aux();
1652 }
1653
1654 /**
1655 * @brief Removes last element.
1656 *
1657 * This is a typical stack operation. It shrinks the %deque by one.
1658 *
1659 * Note that no data is returned, and if the last element's data is
1660 * needed, it should be retrieved before pop_back() is called.
1661 */
1662 void
1663 pop_back() _GLIBCXX_NOEXCEPT
1664 {
1665 __glibcxx_requires_nonempty();
1666 if (this->_M_impl._M_finish._M_cur
1667 != this->_M_impl._M_finish._M_first)
1668 {
1669 --this->_M_impl._M_finish._M_cur;
1670 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1671 this->_M_impl._M_finish._M_cur);
1672 }
1673 else
1674 _M_pop_back_aux();
1675 }
1676
1677#if __cplusplus >= 201103L
1678 /**
1679 * @brief Inserts an object in %deque before specified iterator.
1680 * @param __position A const_iterator into the %deque.
1681 * @param __args Arguments.
1682 * @return An iterator that points to the inserted data.
1683 *
1684 * This function will insert an object of type T constructed
1685 * with T(std::forward<Args>(args)...) before the specified location.
1686 */
1687 template<typename... _Args>
1688 iterator
1689 emplace(const_iterator __position, _Args&&... __args);
1690
1691 /**
1692 * @brief Inserts given value into %deque before specified iterator.
1693 * @param __position A const_iterator into the %deque.
1694 * @param __x Data to be inserted.
1695 * @return An iterator that points to the inserted data.
1696 *
1697 * This function will insert a copy of the given value before the
1698 * specified location.
1699 */
1700 iterator
1701 insert(const_iterator __position, const value_type& __x);
1702#else
1703 /**
1704 * @brief Inserts given value into %deque before specified iterator.
1705 * @param __position An iterator into the %deque.
1706 * @param __x Data to be inserted.
1707 * @return An iterator that points to the inserted data.
1708 *
1709 * This function will insert a copy of the given value before the
1710 * specified location.
1711 */
1712 iterator
1713 insert(iterator __position, const value_type& __x);
1714#endif
1715
1716#if __cplusplus >= 201103L
1717 /**
1718 * @brief Inserts given rvalue into %deque before specified iterator.
1719 * @param __position A const_iterator into the %deque.
1720 * @param __x Data to be inserted.
1721 * @return An iterator that points to the inserted data.
1722 *
1723 * This function will insert a copy of the given rvalue before the
1724 * specified location.
1725 */
1726 iterator
1727 insert(const_iterator __position, value_type&& __x)
1728 { return emplace(__position, std::move(__x)); }
1729
1730 /**
1731 * @brief Inserts an initializer list into the %deque.
1732 * @param __p An iterator into the %deque.
1733 * @param __l An initializer_list.
1734 * @return An iterator that points to the inserted data.
1735 *
1736 * This function will insert copies of the data in the
1737 * initializer_list @a __l into the %deque before the location
1738 * specified by @a __p. This is known as <em>list insert</em>.
1739 */
1740 iterator
1741 insert(const_iterator __p, initializer_list<value_type> __l)
1742 {
1743 auto __offset = __p - cbegin();
1744 _M_range_insert_aux(__p._M_const_cast(), __l.begin(), __l.end(),
1745 std::random_access_iterator_tag());
1746 return begin() + __offset;
1747 }
1748
1749 /**
1750 * @brief Inserts a number of copies of given data into the %deque.
1751 * @param __position A const_iterator into the %deque.
1752 * @param __n Number of elements to be inserted.
1753 * @param __x Data to be inserted.
1754 * @return An iterator that points to the inserted data.
1755 *
1756 * This function will insert a specified number of copies of the given
1757 * data before the location specified by @a __position.
1758 */
1759 iterator
1760 insert(const_iterator __position, size_type __n, const value_type& __x)
1761 {
1762 difference_type __offset = __position - cbegin();
1763 _M_fill_insert(__position._M_const_cast(), __n, __x);
1764 return begin() + __offset;
1765 }
1766#else
1767 /**
1768 * @brief Inserts a number of copies of given data into the %deque.
1769 * @param __position An iterator into the %deque.
1770 * @param __n Number of elements to be inserted.
1771 * @param __x Data to be inserted.
1772 *
1773 * This function will insert a specified number of copies of the given
1774 * data before the location specified by @a __position.
1775 */
1776 void
1777 insert(iterator __position, size_type __n, const value_type& __x)
1778 { _M_fill_insert(__position, __n, __x); }
1779#endif
1780
1781#if __cplusplus >= 201103L
1782 /**
1783 * @brief Inserts a range into the %deque.
1784 * @param __position A const_iterator into the %deque.
1785 * @param __first An input iterator.
1786 * @param __last An input iterator.
1787 * @return An iterator that points to the inserted data.
1788 *
1789 * This function will insert copies of the data in the range
1790 * [__first,__last) into the %deque before the location specified
1791 * by @a __position. This is known as <em>range insert</em>.
1792 */
1793 template<typename _InputIterator,
1794 typename = std::_RequireInputIter<_InputIterator>>
1795 iterator
1796 insert(const_iterator __position, _InputIterator __first,
1797 _InputIterator __last)
1798 {
1799 difference_type __offset = __position - cbegin();
1800 _M_range_insert_aux(__position._M_const_cast(), __first, __last,
1801 std::__iterator_category(__first));
1802 return begin() + __offset;
1803 }
1804#else
1805 /**
1806 * @brief Inserts a range into the %deque.
1807 * @param __position An iterator into the %deque.
1808 * @param __first An input iterator.
1809 * @param __last An input iterator.
1810 *
1811 * This function will insert copies of the data in the range
1812 * [__first,__last) into the %deque before the location specified
1813 * by @a __position. This is known as <em>range insert</em>.
1814 */
1815 template<typename _InputIterator>
1816 void
1817 insert(iterator __position, _InputIterator __first,
1818 _InputIterator __last)
1819 {
1820 // Check whether it's an integral type. If so, it's not an iterator.
1821 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1822 _M_insert_dispatch(__position, __first, __last, _Integral());
1823 }
1824#endif
1825
1826#if __glibcxx_containers_ranges // C++ >= 23
1827 /**
1828 * @brief Insert a range into the deque.
1829 * @param __rg A range of values that are convertible to `value_type`.
1830 * @pre `__rg` and `*this` do not overlap.
1831 * @return An iterator that points to the first new element inserted,
1832 * or to `__pos` if `__rg` is an empty range.
1833 * @since C++23
1834 */
1835 template<__detail::__container_compatible_range<_Tp> _Rg>
1836 iterator
1837 insert_range(const_iterator __pos, _Rg&& __rg);
1838
1839 /**
1840 * @brief Prepend a range at the begining of the deque.
1841 * @param __rg A range of values that are convertible to `value_type`.
1842 * @since C++23
1843 */
1844 template<__detail::__container_compatible_range<_Tp> _Rg>
1845 void
1846 prepend_range(_Rg&& __rg);
1847
1848 /**
1849 * @brief Append a range at the end of the deque.
1850 * @param __rg A range of values that are convertible to `value_type`.
1851 * @since C++23
1852 */
1853 template<__detail::__container_compatible_range<_Tp> _Rg>
1854 void
1855 append_range(_Rg&& __rg);
1856#endif // containers_ranges
1857
1858 /**
1859 * @brief Remove element at given position.
1860 * @param __position Iterator pointing to element to be erased.
1861 * @return An iterator pointing to the next element (or end()).
1862 *
1863 * This function will erase the element at the given position and thus
1864 * shorten the %deque by one.
1865 *
1866 * The user is cautioned that
1867 * this function only erases the element, and that if the element is
1868 * itself a pointer, the pointed-to memory is not touched in any way.
1869 * Managing the pointer is the user's responsibility.
1870 */
1871 iterator
1872#if __cplusplus >= 201103L
1873 erase(const_iterator __position)
1874#else
1875 erase(iterator __position)
1876#endif
1877 { return _M_erase(__position._M_const_cast()); }
1878
1879 /**
1880 * @brief Remove a range of elements.
1881 * @param __first Iterator pointing to the first element to be erased.
1882 * @param __last Iterator pointing to one past the last element to be
1883 * erased.
1884 * @return An iterator pointing to the element pointed to by @a last
1885 * prior to erasing (or end()).
1886 *
1887 * This function will erase the elements in the range
1888 * [__first,__last) and shorten the %deque accordingly.
1889 *
1890 * The user is cautioned that
1891 * this function only erases the elements, and that if the elements
1892 * themselves are pointers, the pointed-to memory is not touched in any
1893 * way. Managing the pointer is the user's responsibility.
1894 */
1895 iterator
1896#if __cplusplus >= 201103L
1897 erase(const_iterator __first, const_iterator __last)
1898#else
1899 erase(iterator __first, iterator __last)
1900#endif
1901 { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1902
1903 /**
1904 * @brief Swaps data with another %deque.
1905 * @param __x A %deque of the same element and allocator types.
1906 *
1907 * This exchanges the elements between two deques in constant time.
1908 * (Four pointers, so it should be quite fast.)
1909 * Note that the global std::swap() function is specialized such that
1910 * std::swap(d1,d2) will feed to this function.
1911 *
1912 * Whether the allocators are swapped depends on the allocator traits.
1913 */
1914 void
1915 swap(deque& __x) _GLIBCXX_NOEXCEPT
1916 {
1917#if __cplusplus >= 201103L
1918 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1919 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1920#endif
1921 _M_impl._M_swap_data(__x._M_impl);
1922 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1923 __x._M_get_Tp_allocator());
1924 }
1925
1926 /**
1927 * Erases all the elements. Note that this function only erases the
1928 * elements, and that if the elements themselves are pointers, the
1929 * pointed-to memory is not touched in any way. Managing the pointer is
1930 * the user's responsibility.
1931 */
1932 void
1933 clear() _GLIBCXX_NOEXCEPT
1934 { _M_erase_at_end(begin()); }
1935
1936 protected:
1937 // Internal constructor functions follow.
1938
1939#if __cplusplus < 201103L
1940 // called by the range constructor to implement [23.1.1]/9
1941
1942 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1943 // 438. Ambiguity in the "do the right thing" clause
1944 template<typename _Integer>
1945 void
1946 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1947 {
1948 _M_initialize_map(_S_check_init_len(static_cast<size_type>(__n),
1949 _M_get_Tp_allocator()));
1950 _M_fill_initialize(__x);
1951 }
1952
1953 // called by the range constructor to implement [23.1.1]/9
1954 template<typename _InputIterator>
1955 void
1956 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1957 __false_type)
1958 {
1959 _M_range_initialize(__first, __last,
1960 std::__iterator_category(__first));
1961 }
1962#endif
1963
1964 static size_t
1965 _S_check_init_len(size_t __n, const allocator_type& __a)
1966 {
1967 if (__n > _S_max_size(__a))
1968 __throw_length_error(
1969 __N("cannot create std::deque larger than max_size()"));
1970 return __n;
1971 }
1972
1973 static size_type
1974 _S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
1975 {
1976 const size_t __diffmax = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max;
1977 const size_t __allocmax = _Alloc_traits::max_size(__a);
1978 return (std::min)(__diffmax, __allocmax);
1979 }
1980
1981 // called by the second initialize_dispatch above
1982 ///@{
1983 /**
1984 * @brief Fills the deque with whatever is in [first,last).
1985 * @param __first An input iterator.
1986 * @param __last An input iterator.
1987 *
1988 * If the iterators are actually forward iterators (or better), then the
1989 * memory layout can be done all at once. Else we move forward using
1990 * push_back on each value from the iterator.
1991 */
1992 template<typename _InputIterator>
1993 void
1994 _M_range_initialize(_InputIterator __first, _InputIterator __last,
1995 std::input_iterator_tag);
1996
1997 // called by the second initialize_dispatch above
1998 template<typename _ForwardIterator>
1999 void
2000 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
2001 std::forward_iterator_tag);
2002 ///@}
2003
2004 /**
2005 * @brief Fills the %deque with copies of value.
2006 * @param __value Initial value.
2007 * @pre _M_start and _M_finish have already been initialized,
2008 * but none of the %deque's elements have yet been constructed.
2009 *
2010 * This function is called only when the user provides an explicit size
2011 * (with or without an explicit exemplar value).
2012 */
2013 void
2014 _M_fill_initialize(const value_type& __value);
2015
2016#if __cplusplus >= 201103L
2017 // called by deque(n).
2018 void
2019 _M_default_initialize();
2020#endif
2021
2022 // Internal assign functions follow. The *_aux functions do the actual
2023 // assignment work for the range versions.
2024
2025#if __cplusplus < 201103L
2026 // called by the range assign to implement [23.1.1]/9
2027
2028 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2029 // 438. Ambiguity in the "do the right thing" clause
2030 template<typename _Integer>
2031 void
2032 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
2033 { _M_fill_assign(__n, __val); }
2034
2035 // called by the range assign to implement [23.1.1]/9
2036 template<typename _InputIterator>
2037 void
2038 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
2039 __false_type)
2040 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
2041#endif
2042
2043 // called by the second assign_dispatch above
2044 template<typename _InputIterator>
2045 void
2046 _M_assign_aux(_InputIterator __first, _InputIterator __last,
2047 std::input_iterator_tag);
2048
2049 // called by the second assign_dispatch above
2050 template<typename _ForwardIterator>
2051 void
2052 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
2053 std::forward_iterator_tag)
2054 {
2055 const size_type __len = std::distance(__first, __last);
2056 if (__len > size())
2057 {
2058 _ForwardIterator __mid = __first;
2059 std::advance(__mid, size());
2060 std::copy(__first, __mid, begin());
2061 _M_range_insert_aux(end(), __mid, __last,
2062 std::__iterator_category(__first));
2063 }
2064 else
2065 _M_erase_at_end(std::copy(__first, __last, begin()));
2066 }
2067
2068 // Called by assign(n,t), and the range assign when it turns out
2069 // to be the same thing.
2070 void
2071 _M_fill_assign(size_type __n, const value_type& __val)
2072 {
2073 if (__n > size())
2074 {
2075 std::fill(begin(), end(), __val);
2076 _M_fill_insert(end(), __n - size(), __val);
2077 }
2078 else
2079 {
2080 _M_erase_at_end(begin() + difference_type(__n));
2081 std::fill(begin(), end(), __val);
2082 }
2083 }
2084
2085 ///@{
2086 /// Helper functions for push_* and pop_*.
2087#if __cplusplus < 201103L
2088 void _M_push_back_aux(const value_type&);
2089
2090 void _M_push_front_aux(const value_type&);
2091#else
2092 template<typename... _Args>
2093 void _M_push_back_aux(_Args&&... __args);
2094
2095 template<typename... _Args>
2096 void _M_push_front_aux(_Args&&... __args);
2097#endif
2098
2099 void _M_pop_back_aux();
2100
2101 void _M_pop_front_aux();
2102 ///@}
2103
2104 // Internal insert functions follow. The *_aux functions do the actual
2105 // insertion work when all shortcuts fail.
2106
2107#if __cplusplus < 201103L
2108 // called by the range insert to implement [23.1.1]/9
2109
2110 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2111 // 438. Ambiguity in the "do the right thing" clause
2112 template<typename _Integer>
2113 void
2114 _M_insert_dispatch(iterator __pos,
2115 _Integer __n, _Integer __x, __true_type)
2116 { _M_fill_insert(__pos, __n, __x); }
2117
2118 // called by the range insert to implement [23.1.1]/9
2119 template<typename _InputIterator>
2120 void
2121 _M_insert_dispatch(iterator __pos,
2122 _InputIterator __first, _InputIterator __last,
2123 __false_type)
2124 {
2125 _M_range_insert_aux(__pos, __first, __last,
2126 std::__iterator_category(__first));
2127 }
2128#endif
2129
2130 // insert [__first, __last) at the front, assumes distance(__first, __last) is n
2131 template<typename _InputIterator, typename _Sentinel>
2132 void _M_range_prepend(_InputIterator __first, _Sentinel __last,
2133 size_type __n);
2134
2135 // insert [__first, __last) at the back, assumes distance(__first, __last) is n
2136 template<typename _InputIterator, typename _Sentinel>
2137 void _M_range_append(_InputIterator __first, _Sentinel __last,
2138 size_type __n);
2139
2140 // called by the second insert_dispatch above
2141 template<typename _InputIterator>
2142 void
2143 _M_range_insert_aux(iterator __pos, _InputIterator __first,
2144 _InputIterator __last, std::input_iterator_tag);
2145
2146 // called by the second insert_dispatch above
2147 template<typename _ForwardIterator>
2148 void
2149 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
2150 _ForwardIterator __last, std::forward_iterator_tag);
2151
2152 // Called by insert(p,n,x), and the range insert when it turns out to be
2153 // the same thing. Can use fill functions in optimal situations,
2154 // otherwise passes off to insert_aux(p,n,x).
2155 void
2156 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
2157
2158 // called by insert(p,x)
2159#if __cplusplus < 201103L
2160 iterator
2161 _M_insert_aux(iterator __pos, const value_type& __x);
2162#else
2163 struct _Temporary_value
2164 {
2165 template<typename... _Args>
2166 _GLIBCXX20_CONSTEXPR explicit
2167 _Temporary_value(deque* __deque, _Args&&... __args) : _M_this(__deque)
2168 {
2169 _Alloc_traits::construct(_M_this->_M_impl, _M_ptr(),
2170 std::forward<_Args>(__args)...);
2171 }
2172
2173 _GLIBCXX20_CONSTEXPR
2174 ~_Temporary_value()
2175 { _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); }
2176
2177 _GLIBCXX20_CONSTEXPR value_type&
2178 _M_val() noexcept { return __tmp_val; }
2179
2180 private:
2181 _GLIBCXX20_CONSTEXPR _Tp*
2182 _M_ptr() noexcept { return std::__addressof(__tmp_val); }
2183
2184 union
2185 {
2186 _Tp __tmp_val;
2187 };
2188
2189 deque* _M_this;
2190 };
2191
2192 iterator
2193 _M_insert_aux(iterator __pos, const value_type& __x)
2194 { return _M_emplace_aux(__pos, __x); }
2195
2196 template<typename... _Args>
2197 iterator
2198 _M_emplace_aux(iterator __pos, _Args&&... __args);
2199#endif
2200
2201 // called by insert(p,n,x) via fill_insert
2202 void
2203 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
2204
2205 // called by range_insert_aux for forward iterators
2206 template<typename _ForwardIterator>
2207 void
2208 _M_insert_aux(iterator __pos,
2209 _ForwardIterator __first, _ForwardIterator __last,
2210 size_type __n);
2211
2212
2213 // Internal erase functions follow.
2214
2215 void
2216 _M_destroy_data_aux(iterator __first, iterator __last);
2217
2218 // Called by ~deque().
2219 // NB: Doesn't deallocate the nodes.
2220 template<typename _Alloc1>
2221 void
2222 _M_destroy_data(iterator __first, iterator __last, const _Alloc1&)
2223 { _M_destroy_data_aux(__first, __last); }
2224
2225 void
2226 _M_destroy_data(iterator __first, iterator __last,
2227 const std::allocator<_Tp>&)
2228 {
2229 if (!__has_trivial_destructor(value_type))
2230 _M_destroy_data_aux(__first, __last);
2231 }
2232
2233 // Called by erase(q1, q2).
2234 void
2235 _M_erase_at_begin(iterator __pos)
2236 {
2237 _M_destroy_data(begin(), __pos, _M_get_Tp_allocator());
2238 _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
2239 this->_M_impl._M_start = __pos;
2240 }
2241
2242 // Called by erase(q1, q2), resize(), clear(), _M_assign_aux,
2243 // _M_fill_assign, operator=.
2244 void
2245 _M_erase_at_end(iterator __pos)
2246 {
2247 _M_destroy_data(__pos, end(), _M_get_Tp_allocator());
2248 _M_destroy_nodes(__pos._M_node + 1,
2249 this->_M_impl._M_finish._M_node + 1);
2250 this->_M_impl._M_finish = __pos;
2251 }
2252
2253 iterator
2254 _M_erase(iterator __pos);
2255
2256 iterator
2257 _M_erase(iterator __first, iterator __last);
2258
2259#if __cplusplus >= 201103L
2260 // Called by resize(sz).
2261 void
2262 _M_default_append(size_type __n);
2263
2264 bool
2265 _M_shrink_to_fit();
2266#endif
2267
2268 ///@{
2269 /// Memory-handling helpers for the previous internal insert functions.
2270 iterator
2271 _M_reserve_elements_at_front(size_type __n)
2272 {
2273 const size_type __vacancies = this->_M_impl._M_start._M_cur
2274 - this->_M_impl._M_start._M_first;
2275 if (__n > __vacancies)
2276 _M_new_elements_at_front(__n - __vacancies);
2277 return this->_M_impl._M_start - difference_type(__n);
2278 }
2279
2280 iterator
2281 _M_reserve_elements_at_back(size_type __n)
2282 {
2283 const size_type __vacancies = (this->_M_impl._M_finish._M_last
2284 - this->_M_impl._M_finish._M_cur) - 1;
2285 if (__n > __vacancies)
2286 _M_new_elements_at_back(__n - __vacancies);
2287 return this->_M_impl._M_finish + difference_type(__n);
2288 }
2289
2290 void
2291 _M_new_elements_at_front(size_type __new_elements);
2292
2293 void
2294 _M_new_elements_at_back(size_type __new_elements);
2295 ///@}
2296
2297
2298 ///@{
2299 /**
2300 * @brief Memory-handling helpers for the major %map.
2301 *
2302 * Makes sure the _M_map has space for new nodes. Does not
2303 * actually add the nodes. Can invalidate _M_map pointers.
2304 * (And consequently, %deque iterators.)
2305 */
2306 void
2307 _M_reserve_map_at_back(size_type __nodes_to_add = 1)
2308 {
2309 if (__nodes_to_add + 1 > this->_M_impl._M_map_size
2310 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
2311 _M_reallocate_map(__nodes_to_add, false);
2312 }
2313
2314 void
2315 _M_reserve_map_at_front(size_type __nodes_to_add = 1)
2316 {
2317 if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
2318 - this->_M_impl._M_map))
2319 _M_reallocate_map(__nodes_to_add, true);
2320 }
2321
2322 void
2323 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
2324 ///@}
2325
2326#if __cplusplus >= 201103L
2327 // Constant-time, nothrow move assignment when source object's memory
2328 // can be moved because the allocators are equal.
2329 void
2330 _M_move_assign1(deque&& __x, /* always equal: */ true_type) noexcept
2331 {
2332 this->_M_impl._M_swap_data(__x._M_impl);
2333 __x.clear();
2334 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
2335 }
2336
2337 // When the allocators are not equal the operation could throw, because
2338 // we might need to allocate a new map for __x after moving from it
2339 // or we might need to allocate new elements for *this.
2340 void
2341 _M_move_assign1(deque&& __x, /* always equal: */ false_type)
2342 {
2343 if (_M_get_Tp_allocator() == __x._M_get_Tp_allocator())
2344 return _M_move_assign1(std::move(__x), true_type());
2345
2346 constexpr bool __move_storage =
2347 _Alloc_traits::_S_propagate_on_move_assign();
2348 _M_move_assign2(std::move(__x), __bool_constant<__move_storage>());
2349 }
2350
2351 // Destroy all elements and deallocate all memory, then replace
2352 // with elements created from __args.
2353 template<typename... _Args>
2354 void
2355 _M_replace_map(_Args&&... __args)
2356 {
2357 // Create new data first, so if allocation fails there are no effects.
2358 deque __newobj(std::forward<_Args>(__args)...);
2359 // Free existing storage using existing allocator.
2360 clear();
2361 _M_deallocate_node(*begin()._M_node); // one node left after clear()
2362 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
2363 this->_M_impl._M_map = nullptr;
2364 this->_M_impl._M_map_size = 0;
2365 // Take ownership of replacement memory.
2366 this->_M_impl._M_swap_data(__newobj._M_impl);
2367 }
2368
2369 // Do move assignment when the allocator propagates.
2370 void
2371 _M_move_assign2(deque&& __x, /* propagate: */ true_type)
2372 {
2373 // Make a copy of the original allocator state.
2374 auto __alloc = __x._M_get_Tp_allocator();
2375 // The allocator propagates so storage can be moved from __x,
2376 // leaving __x in a valid empty state with a moved-from allocator.
2377 _M_replace_map(std::move(__x));
2378 // Move the corresponding allocator state too.
2379 _M_get_Tp_allocator() = std::move(__alloc);
2380 }
2381
2382 // Do move assignment when it may not be possible to move source
2383 // object's memory, resulting in a linear-time operation.
2384 void
2385 _M_move_assign2(deque&& __x, /* propagate: */ false_type)
2386 {
2387 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
2388 {
2389 // The allocators are equal so storage can be moved from __x,
2390 // leaving __x in a valid empty state with its current allocator.
2391 _M_replace_map(std::move(__x), __x.get_allocator());
2392 }
2393 else
2394 {
2395 // The rvalue's allocator cannot be moved and is not equal,
2396 // so we need to individually move each element.
2397 _M_assign_aux(std::make_move_iterator(__x.begin()),
2398 std::make_move_iterator(__x.end()),
2399 std::random_access_iterator_tag());
2400 __x.clear();
2401 }
2402 }
2403#endif
2404 };
2405
2406#if __cpp_deduction_guides >= 201606
2407 template<typename _InputIterator, typename _ValT
2408 = typename iterator_traits<_InputIterator>::value_type,
2409 typename _Allocator = allocator<_ValT>,
2410 typename = _RequireInputIter<_InputIterator>,
2411 typename = _RequireAllocator<_Allocator>>
2412 deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
2413 -> deque<_ValT, _Allocator>;
2414
2415#if __glibcxx_containers_ranges // C++ >= 23
2416 template<ranges::input_range _Rg,
2417 typename _Alloc = allocator<ranges::range_value_t<_Rg>>>
2418 deque(from_range_t, _Rg&&, _Alloc = _Alloc())
2419 -> deque<ranges::range_value_t<_Rg>, _Alloc>;
2420#endif
2421#endif
2422
2423 /**
2424 * @brief Deque equality comparison.
2425 * @param __x A %deque.
2426 * @param __y A %deque of the same type as @a __x.
2427 * @return True iff the size and elements of the deques are equal.
2428 *
2429 * This is an equivalence relation. It is linear in the size of the
2430 * deques. Deques are considered equivalent if their sizes are equal,
2431 * and if corresponding elements compare equal.
2432 */
2433 template<typename _Tp, typename _Alloc>
2434 _GLIBCXX_NODISCARD
2435 inline bool
2436 operator==(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2437 { return __x.size() == __y.size()
2438 && std::equal(__x.begin(), __x.end(), __y.begin()); }
2439
2440#if __cpp_lib_three_way_comparison
2441 /**
2442 * @brief Deque ordering relation.
2443 * @param __x A `deque`.
2444 * @param __y A `deque` of the same type as `__x`.
2445 * @return A value indicating whether `__x` is less than, equal to,
2446 * greater than, or incomparable with `__y`.
2447 *
2448 * See `std::lexicographical_compare_three_way()` for how the determination
2449 * is made. This operator is used to synthesize relational operators like
2450 * `<` and `>=` etc.
2451 */
2452 template<typename _Tp, typename _Alloc>
2453 [[nodiscard]]
2454 inline __detail::__synth3way_t<_Tp>
2455 operator<=>(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2456 {
2457 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
2458 __y.begin(), __y.end(),
2459 __detail::__synth3way);
2460 }
2461#else
2462 /**
2463 * @brief Deque ordering relation.
2464 * @param __x A %deque.
2465 * @param __y A %deque of the same type as @a __x.
2466 * @return True iff @a x is lexicographically less than @a __y.
2467 *
2468 * This is a total ordering relation. It is linear in the size of the
2469 * deques. The elements must be comparable with @c <.
2470 *
2471 * See std::lexicographical_compare() for how the determination is made.
2472 */
2473 template<typename _Tp, typename _Alloc>
2474 _GLIBCXX_NODISCARD
2475 inline bool
2476 operator<(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2477 { return std::lexicographical_compare(__x.begin(), __x.end(),
2478 __y.begin(), __y.end()); }
2479
2480 /// Based on operator==
2481 template<typename _Tp, typename _Alloc>
2482 _GLIBCXX_NODISCARD
2483 inline bool
2484 operator!=(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2485 { return !(__x == __y); }
2486
2487 /// Based on operator<
2488 template<typename _Tp, typename _Alloc>
2489 _GLIBCXX_NODISCARD
2490 inline bool
2491 operator>(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2492 { return __y < __x; }
2493
2494 /// Based on operator<
2495 template<typename _Tp, typename _Alloc>
2496 _GLIBCXX_NODISCARD
2497 inline bool
2498 operator<=(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2499 { return !(__y < __x); }
2500
2501 /// Based on operator<
2502 template<typename _Tp, typename _Alloc>
2503 _GLIBCXX_NODISCARD
2504 inline bool
2505 operator>=(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2506 { return !(__x < __y); }
2507#endif // three-way comparison
2508
2509 /// See std::deque::swap().
2510 template<typename _Tp, typename _Alloc>
2511 inline void
2512 swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
2513 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
2514 { __x.swap(__y); }
2515
2516#undef _GLIBCXX_DEQUE_BUF_SIZE
2517
2518_GLIBCXX_END_NAMESPACE_CONTAINER
2519
2520#if __cplusplus >= 201103L
2521 // std::allocator is safe, but it is not the only allocator
2522 // for which this is valid.
2523 template<class _Tp>
2524 struct __is_bitwise_relocatable<_GLIBCXX_STD_C::deque<_Tp>>
2525 : true_type { };
2526#endif
2527
2528_GLIBCXX_END_NAMESPACE_VERSION
2529} // namespace std
2530
2531#endif /* _STL_DEQUE_H */
_GLIBCXX_DEQUE_BUF_SIZE
#define _GLIBCXX_DEQUE_BUF_SIZE
This function controls the size of memory nodes.
Definition stl_deque.h:95
std::chrono::operator<=
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:859
std::chrono::operator>=
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:873
std::chrono::operator<
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:826
std::chrono::operator>
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:866
std::true_type
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
Definition type_traits:119
std::false_type
__bool_constant< false > false_type
The type used as a compile-time boolean with false value.
Definition type_traits:122
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:138
std::__addressof
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:52
std::forward
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:72
std::lexicographical_compare_three_way
constexpr auto lexicographical_compare_three_way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Comp __comp) -> decltype(__comp(*__first1, *__first2))
Performs dictionary comparison on ranges.
Definition stl_algobase.h:1867
std::max
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition stl_algobase.h:256
std::min
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition stl_algobase.h:232
std::__iterator_category
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
Definition stl_iterator_base_types.h:241
std
ISO C++ entities toplevel namespace is std.
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::__ptr_rebind
typename pointer_traits< _Ptr >::template rebind< _Tp > __ptr_rebind
Convenience alias for rebinding pointers.
Definition ptr_traits.h:201
std::advance
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Definition stl_iterator_base_funcs.h:261
std::initializer_list
initializer_list
Definition initializer_list:48
std::is_nothrow_default_constructible
is_nothrow_default_constructible
Definition type_traits:1325
__gnu_cxx::__alloc_traits< _Tp_alloc_type >::is_always_equal
typename __detected_or_t< is_empty< _Tp_alloc_type >, __equal, _Tp_alloc_type >::type is_always_equal
Definition bits/alloc_traits.h:365
std::allocator
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:134
std::_Deque_iterator
A deque::iterator.
Definition stl_deque.h:117
std::_Deque_iterator::_M_set_node
void _M_set_node(_Map_pointer __new_node) noexcept
Definition stl_deque.h:266
std::_Deque_base::_M_initialize_map
void _M_initialize_map(size_t)
Layout storage.
Definition stl_deque.h:641
std::deque
A standard container using fixed-size memory allocation and constant-time manipulation of elements at...
Definition stl_deque.h:791
std::deque::rbegin
reverse_iterator rbegin() noexcept
Definition stl_deque.h:1251
std::deque::deque
deque(const deque &__x)
Deque copy constructor.
Definition stl_deque.h:919
std::deque::at
const_reference at(size_type __n) const
Provides access to the data contained in the deque.
Definition stl_deque.h:1498
std::deque::rend
reverse_iterator rend() noexcept
Definition stl_deque.h:1271
std::deque::erase
iterator erase(const_iterator __position)
Remove element at given position.
Definition stl_deque.h:1873
std::deque::back
const_reference back() const noexcept
Definition stl_deque.h:1548
std::deque::crend
const_reverse_iterator crend() const noexcept
Definition stl_deque.h:1321
std::deque::clear
void clear() noexcept
Definition stl_deque.h:1933
std::deque::_M_pop_front_aux
void _M_pop_front_aux()
Helper functions for push_* and pop_*.
Definition deque.tcc:577
std::deque::pop_back
void pop_back() noexcept
Removes last element.
Definition stl_deque.h:1663
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::deque::cbegin
const_iterator cbegin() const noexcept
Definition stl_deque.h:1291
std::deque::resize
void resize(size_type __new_size)
Resizes the deque to the specified number of elements.
Definition stl_deque.h:1354
std::deque::rend
const_reverse_iterator rend() const noexcept
Definition stl_deque.h:1281
std::deque::_M_reserve_elements_at_front
iterator _M_reserve_elements_at_front(size_type __n)
Memory-handling helpers for the previous internal insert functions.
Definition stl_deque.h:2271
std::deque::emplace
iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in deque before specified iterator.
Definition deque.tcc:188
std::deque::pop_front
void pop_front() noexcept
Removes first element.
Definition stl_deque.h:1640
std::deque::get_allocator
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
Definition stl_deque.h:1202
std::deque::swap
void swap(deque &__x) noexcept
Swaps data with another deque.
Definition stl_deque.h:1915
std::deque::operator[]
reference operator[](size_type __n) noexcept
Subscript access to the data contained in the deque.
Definition stl_deque.h:1430
std::deque::at
reference at(size_type __n)
Provides access to the data contained in the deque.
Definition stl_deque.h:1480
std::deque::deque
deque(size_type __n, const allocator_type &__a=allocator_type())
Creates a deque with default constructed elements.
Definition stl_deque.h:880
std::deque::empty
bool empty() const noexcept
Definition stl_deque.h:1413
std::deque::operator[]
const_reference operator[](size_type __n) const noexcept
Subscript access to the data contained in the deque.
Definition stl_deque.h:1449
std::deque::push_front
void push_front(const value_type &__x)
Add data to the front of the deque.
Definition stl_deque.h:1567
std::deque::resize
void resize(size_type __new_size, const value_type &__x)
Resizes the deque to the specified number of elements.
Definition stl_deque.h:1376
std::deque::front
const_reference front() const noexcept
Definition stl_deque.h:1522
std::deque::assign
void assign(size_type __n, const value_type &__val)
Assigns a given value to a deque.
Definition stl_deque.h:1104
std::deque::operator=
deque & operator=(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
Definition stl_deque.h:1085
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::deque::insert
iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into deque before specified iterator.
Definition deque.tcc:212
std::deque::deque
deque(const deque &__x, const __type_identity_t< allocator_type > &__a)
Copy constructor with alternative allocator.
Definition stl_deque.h:938
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::insert
iterator insert(const_iterator __p, initializer_list< value_type > __l)
Inserts an initializer list into the deque.
Definition stl_deque.h:1741
std::deque::end
iterator end() noexcept
Definition stl_deque.h:1231
std::deque::deque
deque(size_type __n, const value_type &__value, const allocator_type &__a=allocator_type())
Creates a deque with copies of an exemplar element.
Definition stl_deque.h:892
std::deque::crbegin
const_reverse_iterator crbegin() const noexcept
Definition stl_deque.h:1311
std::deque::_M_reserve_map_at_back
void _M_reserve_map_at_back(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
Definition stl_deque.h:2307
std::deque::back
reference back() noexcept
Definition stl_deque.h:1534
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
std::deque::deque
deque()=default
Creates a deque with no elements.
std::deque::_M_push_back_aux
void _M_push_back_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
Definition deque.tcc:485
std::deque::operator=
deque & operator=(deque &&__x) noexcept(_Alloc_traits::_S_always_equal())
Deque move assignment operator.
Definition stl_deque.h:1066
std::deque::push_back
void push_back(const value_type &__x)
Add data to the end of the deque.
Definition stl_deque.h:1604
std::deque::_M_range_initialize
void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, std::forward_iterator_tag)
Fills the deque with whatever is in [first,last).
Definition deque.tcc:444
std::deque::deque
deque(const allocator_type &__a)
Creates a deque with no elements.
Definition stl_deque.h:867
std::deque::_M_reserve_map_at_front
void _M_reserve_map_at_front(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
Definition stl_deque.h:2315
std::deque::_M_push_front_aux
void _M_push_front_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
Definition deque.tcc:524
std::deque::_M_range_check
void _M_range_check(size_type __n) const
Safety check used only from at().
Definition stl_deque.h:1458
std::deque::assign
void assign(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
Definition stl_deque.h:1148
std::deque::deque
deque(initializer_list< value_type > __l, const allocator_type &__a=allocator_type())
Builds a deque from an initializer list.
Definition stl_deque.h:978
std::deque::shrink_to_fit
void shrink_to_fit() noexcept
Definition stl_deque.h:1404
std::deque::assign
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a deque.
Definition stl_deque.h:1123
std::deque::deque
deque(_InputIterator __first, _InputIterator __last, const allocator_type &__a=allocator_type())
Builds a deque from a range.
Definition stl_deque.h:1005
std::deque::begin
const_iterator begin() const noexcept
Definition stl_deque.h:1221
std::deque::operator=
deque & operator=(const deque &__x)
Deque assignment operator.
Definition deque.tcc:96
std::deque::end
const_iterator end() const noexcept
Definition stl_deque.h:1241
std::deque::insert
iterator insert(const_iterator __position, size_type __n, const value_type &__x)
Inserts a number of copies of given data into the deque.
Definition stl_deque.h:1760
std::deque::insert
iterator insert(const_iterator __position, value_type &&__x)
Inserts given rvalue into deque before specified iterator.
Definition stl_deque.h:1727
std::deque::_M_pop_back_aux
void _M_pop_back_aux()
Helper functions for push_* and pop_*.
Definition deque.tcc:561
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::front
reference front() noexcept
Definition stl_deque.h:1510
std::deque::_M_reserve_elements_at_back
iterator _M_reserve_elements_at_back(size_type __n)
Memory-handling helpers for the previous internal insert functions.
Definition stl_deque.h:2281
std::deque::cend
const_iterator cend() const noexcept
Definition stl_deque.h:1301
std::deque::insert
iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
Inserts a range into the deque.
Definition stl_deque.h:1796
std::deque::rbegin
const_reverse_iterator rbegin() const noexcept
Definition stl_deque.h:1261
std::deque::deque
deque(deque &&__x, const __type_identity_t< allocator_type > &__a)
Move constructor with alternative allocator.
Definition stl_deque.h:945
std::deque::begin
iterator begin() noexcept
Definition stl_deque.h:1212
std::deque::erase
iterator erase(const_iterator __first, const_iterator __last)
Remove a range of elements.
Definition stl_deque.h:1897
std::deque::deque
deque(deque &&)=default
Deque move constructor.
std::input_iterator_tag
Marking input iterators.
Definition stl_iterator_base_types.h:95
std::forward_iterator_tag
Forward iterators support a superset of input iterator operations.
Definition stl_iterator_base_types.h:101
std::random_access_iterator_tag
Random-access iterators support a superset of bidirectional iterator operations.
Definition stl_iterator_base_types.h:109
std::iterator
Common iterator class.
Definition stl_iterator_base_types.h:130
__gnu_cxx::__alloc_traits
Uniform interface to C++98 and C++11 allocators.
Definition ext/alloc_traits.h:51
__gnu_cxx::__alloc_traits< _Map_alloc_type >::allocate
static constexpr pointer allocate(_Map_alloc_type &__a, size_type __n)
__gnu_cxx::__alloc_traits< _Map_alloc_type >::deallocate
static constexpr void deallocate(_Map_alloc_type &__a, pointer __p, size_type __n)
__gnu_cxx::__alloc_traits< _Tp_alloc_type >::max_size
static constexpr size_type max_size(const _Tp_alloc_type &__a) noexcept
std::assignable_from
[concept.assignable], concept assignable_from
Definition concepts:149
std::ranges::sized_range
[range.sized] The sized_range concept.
Definition ranges_base.h:553
std::ranges::input_range
A range for which ranges::begin returns an input iterator.
Definition ranges_base.h:599
std::ranges::forward_range
A range for which ranges::begin returns a forward iterator.
Definition ranges_base.h:604