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