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