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