libstdc++: stl_deque.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56#ifndef _STL_DEQUE_H
57#define _STL_DEQUE_H 1
58
62#if __cplusplus >= 201103L
65#endif
66#if __cplusplus > 201703L
68#endif
69
71
72namespace std _GLIBCXX_VISIBILITY(default)
73{
74_GLIBCXX_BEGIN_NAMESPACE_VERSION
75_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
76
77
78
79
80
81
82
83
84
85
86
87
88
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)
99
100
101
102
103
104
105
106
107
108
109
110
111
112 template<typename _Tp, typename _Ref, typename _Ptr>
114 {
115#if __cplusplus < 201103L
118 typedef _Tp* _Elt_pointer;
119 typedef _Tp** _Map_pointer;
120#else
121 private:
122 template<typename _CvTp>
124 public:
129#endif
130
131 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
132 { return __deque_buf_size(sizeof(_Tp)); }
133
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;
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
152 : _M_cur(), _M_first(), _M_last(), _M_node() { }
153
154#if __cplusplus < 201103L
155
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
161 template<typename _Iter,
162 typename = _Require<is_same<_Self, const_iterator>,
165 : _M_cur(__x._M_cur), _M_first(__x._M_first),
166 _M_last(__x._M_last), _M_node(__x._M_node) { }
167
169 : _M_cur(__x._M_cur), _M_first(__x._M_first),
170 _M_last(__x._M_last), _M_node(__x._M_node) { }
171
173#endif
174
176 _M_const_cast() const _GLIBCXX_NOEXCEPT
177 { return iterator(_M_cur, _M_node); }
178
179 _GLIBCXX_NODISCARD
180 reference
181 operator*() const _GLIBCXX_NOEXCEPT
182 { return *_M_cur; }
183
184 _GLIBCXX_NODISCARD
185 pointer
186 operator->() const _GLIBCXX_NOEXCEPT
187 { return _M_cur; }
188
190 operator++() _GLIBCXX_NOEXCEPT
191 {
192 ++_M_cur;
193 if (_M_cur == _M_last)
194 {
196 _M_cur = _M_first;
197 }
198 return *this;
199 }
200
202 operator++(int) _GLIBCXX_NOEXCEPT
203 {
204 _Self __tmp = *this;
205 ++*this;
206 return __tmp;
207 }
208
210 operator--() _GLIBCXX_NOEXCEPT
211 {
212 if (_M_cur == _M_first)
213 {
215 _M_cur = _M_last;
216 }
217 --_M_cur;
218 return *this;
219 }
220
222 operator--(int) _GLIBCXX_NOEXCEPT
223 {
224 _Self __tmp = *this;
225 --*this;
226 return __tmp;
227 }
228
230 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
231 {
232 const difference_type __offset = __n + (_M_cur - _M_first);
233 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
234 _M_cur += __n;
235 else
236 {
237 const difference_type __node_offset =
238 __offset > 0 ? __offset / difference_type(_S_buffer_size())
239 : -difference_type((-__offset - 1)
240 / _S_buffer_size()) - 1;
242 _M_cur = _M_first + (__offset - __node_offset
243 * difference_type(_S_buffer_size()));
244 }
245 return *this;
246 }
247
249 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
250 { return *this += -__n; }
251
252 _GLIBCXX_NODISCARD
253 reference
254 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
255 { return *(*this + __n); }
256
257
258
259
260
261
262 void
263 _M_set_node(_Map_pointer __new_node) _GLIBCXX_NOEXCEPT
264 {
265 _M_node = __new_node;
266 _M_first = *__new_node;
267 _M_last = _M_first + difference_type(_S_buffer_size());
268 }
269
270 _GLIBCXX_NODISCARD
271 friend bool
272 operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
273 { return __x._M_cur == __y._M_cur; }
274
275
276
277
278 template<typename _RefR, typename _PtrR>
279 _GLIBCXX_NODISCARD
280 friend bool
281 operator==(const _Self& __x,
282 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
283 _GLIBCXX_NOEXCEPT
284 { return __x._M_cur == __y._M_cur; }
285
286#if __cpp_lib_three_way_comparison
287 [[nodiscard]]
288 friend strong_ordering
289 operator<=>(const _Self& __x, const _Self& __y) noexcept
290 {
291 if (const auto __cmp = __x._M_node <=> __y._M_node; __cmp != 0)
292 return __cmp;
293 return __x._M_cur <=> __y._M_cur;
294 }
295#else
296 _GLIBCXX_NODISCARD
297 friend bool
298 operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
299 { return !(__x == __y); }
300
301 template<typename _RefR, typename _PtrR>
302 _GLIBCXX_NODISCARD
303 friend bool
304 operator!=(const _Self& __x,
305 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
306 _GLIBCXX_NOEXCEPT
307 { return !(__x == __y); }
308
309 _GLIBCXX_NODISCARD
310 friend bool
311 operator<(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
312 {
313 return (__x._M_node == __y._M_node)
314 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
315 }
316
317 template<typename _RefR, typename _PtrR>
318 _GLIBCXX_NODISCARD
319 friend bool
321 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
322 _GLIBCXX_NOEXCEPT
323 {
324 return (__x._M_node == __y._M_node)
325 ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
326 }
327
328 _GLIBCXX_NODISCARD
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 _GLIBCXX_NODISCARD
335 friend bool
337 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
338 _GLIBCXX_NOEXCEPT
339 { return __y < __x; }
340
341 _GLIBCXX_NODISCARD
342 friend bool
343 operator<=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
344 { return !(__y < __x); }
345
346 template<typename _RefR, typename _PtrR>
347 _GLIBCXX_NODISCARD
348 friend bool
350 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
351 _GLIBCXX_NOEXCEPT
352 { return !(__y < __x); }
353
354 _GLIBCXX_NODISCARD
355 friend bool
356 operator>=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
357 { return !(__x < __y); }
358
359 template<typename _RefR, typename _PtrR>
360 _GLIBCXX_NODISCARD
361 friend bool
363 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
364 _GLIBCXX_NOEXCEPT
365 { return !(__x < __y); }
366#endif
367
368 _GLIBCXX_NODISCARD
369 friend difference_type
370 operator-(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
371 {
372 return difference_type(_S_buffer_size())
373 * (__x._M_node - __y._M_node - bool(__x._M_node))
374 + (__x._M_cur - __x._M_first)
375 + (__y._M_last - __y._M_cur);
376 }
377
378
379
380
381
382 template<typename _RefR, typename _PtrR>
383 _GLIBCXX_NODISCARD
384 friend difference_type
385 operator-(const _Self& __x,
386 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
387 _GLIBCXX_NOEXCEPT
388 {
389 return difference_type(_S_buffer_size())
390 * (__x._M_node - __y._M_node - bool(__x._M_node))
391 + (__x._M_cur - __x._M_first)
392 + (__y._M_last - __y._M_cur);
393 }
394
395 _GLIBCXX_NODISCARD
396 friend _Self
397 operator+(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
398 {
399 _Self __tmp = __x;
400 __tmp += __n;
401 return __tmp;
402 }
403
404 _GLIBCXX_NODISCARD
405 friend _Self
406 operator-(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
407 {
408 _Self __tmp = __x;
409 __tmp -= __n;
410 return __tmp;
411 }
412
413 _GLIBCXX_NODISCARD
414 friend _Self
415 operator+(difference_type __n, const _Self& __x) _GLIBCXX_NOEXCEPT
416 { return __x + __n; }
417 };
418
419
420
421
422
423
424
425
426
427
428
429 template<typename _Tp, typename _Alloc>
431 {
432 protected:
434 rebind<_Tp>::other _Tp_alloc_type;
436
437#if __cplusplus < 201103L
438 typedef _Tp* _Ptr;
439 typedef const _Tp* _Ptr_const;
440#else
441 typedef typename _Alloc_traits::pointer _Ptr;
442 typedef typename _Alloc_traits::const_pointer _Ptr_const;
443#endif
444
445 typedef typename _Alloc_traits::template rebind<_Ptr>::other
446 _Map_alloc_type;
448
449 typedef _Alloc allocator_type;
450
451 allocator_type
452 get_allocator() const _GLIBCXX_NOEXCEPT
453 { return allocator_type(_M_get_Tp_allocator()); }
454
457
459 : _M_impl()
461
463 : _M_impl()
465
466 _Deque_base(const allocator_type& __a, size_t __num_elements)
467 : _M_impl(__a)
469
471 : _M_impl(__a)
472 { }
473
474#if __cplusplus >= 201103L
476 : _M_impl(std::move(__x._M_get_Tp_allocator()))
477 {
479 if (__x._M_impl._M_map)
480 this->_M_impl._M_swap_data(__x._M_impl);
481 }
482
484 : _M_impl(std::move(__x._M_impl), _Tp_alloc_type(__a))
485 { __x._M_initialize_map(0); }
486
488 : _M_impl(__a)
489 {
490 if (__x.get_allocator() == __a)
491 {
492 if (__x._M_impl._M_map)
493 {
495 this->_M_impl._M_swap_data(__x._M_impl);
496 }
497 }
498 else
499 {
501 }
502 }
503#endif
504
506
507 typedef typename iterator::_Map_pointer _Map_pointer;
508
509 struct _Deque_impl_data
510 {
511 _Map_pointer _M_map;
512 size_t _M_map_size;
515
516 _Deque_impl_data() _GLIBCXX_NOEXCEPT
517 : _M_map(), _M_map_size(), _M_start(), _M_finish()
518 { }
519
520#if __cplusplus >= 201103L
521 _Deque_impl_data(const _Deque_impl_data&) = default;
522 _Deque_impl_data&
523 operator=(const _Deque_impl_data&) = default;
524
525 _Deque_impl_data(_Deque_impl_data&& __x) noexcept
526 : _Deque_impl_data(__x)
527 { __x = _Deque_impl_data(); }
528#endif
529
530 void
531 _M_swap_data(_Deque_impl_data& __x) _GLIBCXX_NOEXCEPT
532 {
533
534
535 std::swap(*this, __x);
536 }
537 };
538
539
540
541
542 struct _Deque_impl
543 : public _Tp_alloc_type, public _Deque_impl_data
544 {
545 _Deque_impl() _GLIBCXX_NOEXCEPT_IF(
547 : _Tp_alloc_type()
548 { }
549
550 _Deque_impl(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
551 : _Tp_alloc_type(__a)
552 { }
553
554#if __cplusplus >= 201103L
555 _Deque_impl(_Deque_impl&&) = default;
556
557 _Deque_impl(_Tp_alloc_type&& __a) noexcept
559 { }
560
561 _Deque_impl(_Deque_impl&& __d, _Tp_alloc_type&& __a)
563 { }
564#endif
565 };
566
567 _Tp_alloc_type&
568 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
569 { return this->_M_impl; }
570
571 const _Tp_alloc_type&
572 _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
573 { return this->_M_impl; }
574
575 _Map_alloc_type
576 _M_get_map_allocator() const _GLIBCXX_NOEXCEPT
577 { return _Map_alloc_type(_M_get_Tp_allocator()); }
578
579 _Ptr
580 _M_allocate_node()
581 {
583 return _Traits::allocate(_M_impl, __deque_buf_size(sizeof(_Tp)));
584 }
585
586 void
587 _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
588 {
590 _Traits::deallocate(_M_impl, __p, __deque_buf_size(sizeof(_Tp)));
591 }
592
593 _Map_pointer
594 _M_allocate_map(size_t __n)
595 {
596 _Map_alloc_type __map_alloc = _M_get_map_allocator();
598 }
599
600 void
601 _M_deallocate_map(_Map_pointer __p, size_t __n) _GLIBCXX_NOEXCEPT
602 {
603 _Map_alloc_type __map_alloc = _M_get_map_allocator();
605 }
606
608 void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
609 void _M_destroy_nodes(_Map_pointer __nstart,
610 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT;
611 enum { _S_initial_map_size = 8 };
612
613 _Deque_impl _M_impl;
614 };
615
616 template<typename _Tp, typename _Alloc>
617 _Deque_base<_Tp, _Alloc>::
618 ~_Deque_base() _GLIBCXX_NOEXCEPT
619 {
620 if (this->_M_impl._M_map)
621 {
622 _M_destroy_nodes(this->_M_impl._M_start._M_node,
623 this->_M_impl._M_finish._M_node + 1);
624 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
625 }
626 }
627
628
629
630
631
632
633
634
635
636 template<typename _Tp, typename _Alloc>
637 void
640 {
641 const size_t __num_nodes = (__num_elements / __deque_buf_size(sizeof(_Tp))
642 + 1);
643
644 this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
645 size_t(__num_nodes + 2));
646 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
647
648
649
650
651
652
653 _Map_pointer __nstart = (this->_M_impl._M_map
654 + (this->_M_impl._M_map_size - __num_nodes) / 2);
655 _Map_pointer __nfinish = __nstart + __num_nodes;
656
657 __try
658 { _M_create_nodes(__nstart, __nfinish); }
659 __catch(...)
660 {
661 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
662 this->_M_impl._M_map = _Map_pointer();
663 this->_M_impl._M_map_size = 0;
664 __throw_exception_again;
665 }
666
667 this->_M_impl._M_start._M_set_node(__nstart);
668 this->_M_impl._M_finish._M_set_node(__nfinish - 1);
669 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
670 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
671 + __num_elements
672 % __deque_buf_size(sizeof(_Tp)));
673 }
674
675 template<typename _Tp, typename _Alloc>
676 void
678 _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish)
679 {
680 _Map_pointer __cur;
681 __try
682 {
683 for (__cur = __nstart; __cur < __nfinish; ++__cur)
684 *__cur = this->_M_allocate_node();
685 }
686 __catch(...)
687 {
688 _M_destroy_nodes(__nstart, __cur);
689 __throw_exception_again;
690 }
691 }
692
693 template<typename _Tp, typename _Alloc>
694 void
695 _Deque_base<_Tp, _Alloc>::
696 _M_destroy_nodes(_Map_pointer __nstart,
697 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
698 {
699 for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
700 _M_deallocate_node(*__n);
701 }
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787 template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
789 {
790#ifdef _GLIBCXX_CONCEPT_CHECKS
791
792 typedef typename _Alloc::value_type _Alloc_value_type;
793# if __cplusplus < 201103L
794 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
795# endif
796 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
797#endif
798
799#if __cplusplus >= 201103L
801 "std::deque must have a non-const, non-volatile value_type");
802# if __cplusplus > 201703L || defined __STRICT_ANSI__
804 "std::deque must have the same value_type as its allocator");
805# endif
806#endif
807
809 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
811 typedef typename _Base::_Map_pointer _Map_pointer;
812
813 public:
814 typedef _Tp value_type;
815 typedef typename _Alloc_traits::pointer pointer;
816 typedef typename _Alloc_traits::const_pointer const_pointer;
817 typedef typename _Alloc_traits::reference reference;
818 typedef typename _Alloc_traits::const_reference const_reference;
823 typedef size_t size_type;
824 typedef ptrdiff_t difference_type;
825 typedef _Alloc allocator_type;
826
827 private:
828 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
829 { return __deque_buf_size(sizeof(_Tp)); }
830
831
833 using _Base::_M_create_nodes;
834 using _Base::_M_destroy_nodes;
835 using _Base::_M_allocate_node;
836 using _Base::_M_deallocate_node;
837 using _Base::_M_allocate_map;
838 using _Base::_M_deallocate_map;
839 using _Base::_M_get_Tp_allocator;
840
841
842
843
844
845 using _Base::_M_impl;
846
847 public:
848
849
850
851
852
853
854#if __cplusplus >= 201103L
856#else
858#endif
859
860
861
862
863
864 explicit
865 deque(const allocator_type& __a)
866 : _Base(__a, 0) { }
867
868#if __cplusplus >= 201103L
869
870
871
872
873
874
875
876
877 explicit
878 deque(size_type __n, const allocator_type& __a = allocator_type())
879 : _Base(__a, _S_check_init_len(__n, __a))
880 { _M_default_initialize(); }
881
882
883
884
885
886
887
888
889
890 deque(size_type __n, const value_type& __value,
891 const allocator_type& __a = allocator_type())
892 : _Base(__a, _S_check_init_len(__n, __a))
894#else
895
896
897
898
899
900
901
902
903 explicit
904 deque(size_type __n, const value_type& __value = value_type(),
905 const allocator_type& __a = allocator_type())
906 : _Base(__a, _S_check_init_len(__n, __a))
908#endif
909
910
911
912
913
914
915
916
920 { std::__uninitialized_copy_a(__x.begin(), __x.end(),
921 this->_M_impl._M_start,
922 _M_get_Tp_allocator()); }
923
924#if __cplusplus >= 201103L
925
926
927
928
929
930
931
932
934
935
936 deque(const deque& __x, const __type_identity_t<allocator_type>& __a)
938 { std::__uninitialized_copy_a(__x.begin(), __x.end(),
939 this->_M_impl._M_start,
940 _M_get_Tp_allocator()); }
941
942
943 deque(deque&& __x, const __type_identity_t<allocator_type>& __a)
945 { }
946
947 private:
949 : _Base(std::move(__x), __a)
950 { }
951
954 {
955 if (__x.get_allocator() != __a && !__x.empty())
956 {
957 std::__uninitialized_move_a(__x.begin(), __x.end(),
958 this->_M_impl._M_start,
959 _M_get_Tp_allocator());
960 __x.clear();
961 }
962 }
963
964 public:
965
966
967
968
969
970
971
972
973
974
975
977 const allocator_type& __a = allocator_type())
979 {
982 }
983#endif
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000#if __cplusplus >= 201103L
1001 template<typename _InputIterator,
1002 typename = std::_RequireInputIter<_InputIterator>>
1003 deque(_InputIterator __first, _InputIterator __last,
1004 const allocator_type& __a = allocator_type())
1006 {
1009 }
1010#else
1011 template<typename _InputIterator>
1012 deque(_InputIterator __first, _InputIterator __last,
1013 const allocator_type& __a = allocator_type())
1014 : _Base(__a)
1015 {
1016
1017 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1018 _M_initialize_dispatch(__first, __last, _Integral());
1019 }
1020#endif
1021
1022
1023
1024
1025
1026
1028 { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); }
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1041
1042#if __cplusplus >= 201103L
1043
1044
1045
1046
1047
1048
1049
1050
1053 {
1055 _M_move_assign1(std::move(__x), __always_equal{});
1056 return *this;
1057 }
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1072 {
1073 _M_assign_aux(__l.begin(), __l.end(),
1075 return *this;
1076 }
1077#endif
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089 void
1090 assign(size_type __n, const value_type& __val)
1091 { _M_fill_assign(__n, __val); }
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105#if __cplusplus >= 201103L
1106 template<typename _InputIterator,
1107 typename = std::_RequireInputIter<_InputIterator>>
1108 void
1109 assign(_InputIterator __first, _InputIterator __last)
1111#else
1112 template<typename _InputIterator>
1113 void
1114 assign(_InputIterator __first, _InputIterator __last)
1115 {
1116 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1117 _M_assign_dispatch(__first, __last, _Integral());
1118 }
1119#endif
1120
1121#if __cplusplus >= 201103L
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133 void
1136#endif
1137
1138
1139 _GLIBCXX_NODISCARD
1140 allocator_type
1142 { return _Base::get_allocator(); }
1143
1144
1145
1146
1147
1148
1149 _GLIBCXX_NODISCARD
1152 { return this->_M_impl._M_start; }
1153
1154
1155
1156
1157
1158 _GLIBCXX_NODISCARD
1159 const_iterator
1161 { return this->_M_impl._M_start; }
1162
1163
1164
1165
1166
1167
1168 _GLIBCXX_NODISCARD
1171 { return this->_M_impl._M_finish; }
1172
1173
1174
1175
1176
1177
1178 _GLIBCXX_NODISCARD
1179 const_iterator
1180 end() const _GLIBCXX_NOEXCEPT
1181 { return this->_M_impl._M_finish; }
1182
1183
1184
1185
1186
1187
1188 _GLIBCXX_NODISCARD
1192
1193
1194
1195
1196
1197
1198 _GLIBCXX_NODISCARD
1199 const_reverse_iterator
1202
1203
1204
1205
1206
1207
1208 _GLIBCXX_NODISCARD
1212
1213
1214
1215
1216
1217
1218 _GLIBCXX_NODISCARD
1219 const_reverse_iterator
1220 rend() const _GLIBCXX_NOEXCEPT
1222
1223#if __cplusplus >= 201103L
1224
1225
1226
1227
1228 [[__nodiscard__]]
1229 const_iterator
1231 { return this->_M_impl._M_start; }
1232
1233
1234
1235
1236
1237
1238 [[__nodiscard__]]
1239 const_iterator
1241 { return this->_M_impl._M_finish; }
1242
1243
1244
1245
1246
1247
1248 [[__nodiscard__]]
1249 const_reverse_iterator
1252
1253
1254
1255
1256
1257
1258 [[__nodiscard__]]
1259 const_reverse_iterator
1262#endif
1263
1264
1265
1266 _GLIBCXX_NODISCARD
1267 size_type
1268 size() const _GLIBCXX_NOEXCEPT
1269 { return this->_M_impl._M_finish - this->_M_impl._M_start; }
1270
1271
1272 _GLIBCXX_NODISCARD
1273 size_type
1275 { return _S_max_size(_M_get_Tp_allocator()); }
1276
1277#if __cplusplus >= 201103L
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287 void
1289 {
1290 const size_type __len = size();
1291 if (__new_size > __len)
1292 _M_default_append(__new_size - __len);
1293 else if (__new_size < __len)
1294 _M_erase_at_end(this->_M_impl._M_start
1295 + difference_type(__new_size));
1296 }
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309 void
1310 resize(size_type __new_size, const value_type& __x)
1311#else
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323 void
1324 resize(size_type __new_size, value_type __x = value_type())
1325#endif
1326 {
1327 const size_type __len = size();
1328 if (__new_size > __len)
1329 _M_fill_insert(this->_M_impl._M_finish, __new_size - __len, __x);
1330 else if (__new_size < __len)
1331 _M_erase_at_end(this->_M_impl._M_start
1332 + difference_type(__new_size));
1333 }
1334
1335#if __cplusplus >= 201103L
1336
1337 void
1339 { _M_shrink_to_fit(); }
1340#endif
1341
1342
1343
1344
1345
1346 _GLIBCXX_NODISCARD bool
1348 { return this->_M_impl._M_finish == this->_M_impl._M_start; }
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362 _GLIBCXX_NODISCARD
1363 reference
1365 {
1366 __glibcxx_requires_subscript(__n);
1367 return this->_M_impl._M_start[difference_type(__n)];
1368 }
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381 _GLIBCXX_NODISCARD
1382 const_reference
1384 {
1385 __glibcxx_requires_subscript(__n);
1386 return this->_M_impl._M_start[difference_type(__n)];
1387 }
1388
1389 protected:
1390
1391 void
1393 {
1394 if (__n >= this->size())
1395 __throw_out_of_range_fmt(__N("deque::_M_range_check: __n "
1396 "(which is %zu)>= this->size() "
1397 "(which is %zu)"),
1398 __n, this->size());
1399 }
1400
1401 public:
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413 reference
1415 {
1417 return (*this)[__n];
1418 }
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431 const_reference
1433 {
1435 return (*this)[__n];
1436 }
1437
1438
1439
1440
1441
1442 _GLIBCXX_NODISCARD
1443 reference
1445 {
1446 __glibcxx_requires_nonempty();
1447 return *begin();
1448 }
1449
1450
1451
1452
1453
1454 _GLIBCXX_NODISCARD
1455 const_reference
1457 {
1458 __glibcxx_requires_nonempty();
1459 return *begin();
1460 }
1461
1462
1463
1464
1465
1466 _GLIBCXX_NODISCARD
1467 reference
1469 {
1470 __glibcxx_requires_nonempty();
1472 --__tmp;
1473 return *__tmp;
1474 }
1475
1476
1477
1478
1479
1480 _GLIBCXX_NODISCARD
1481 const_reference
1482 back() const _GLIBCXX_NOEXCEPT
1483 {
1484 __glibcxx_requires_nonempty();
1486 --__tmp;
1487 return *__tmp;
1488 }
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500 void
1502 {
1503 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1504 {
1505 _Alloc_traits::construct(this->_M_impl,
1506 this->_M_impl._M_start._M_cur - 1,
1507 __x);
1508 --this->_M_impl._M_start._M_cur;
1509 }
1510 else
1512 }
1513
1514#if __cplusplus >= 201103L
1515 void
1517 { emplace_front(std::move(__x)); }
1518
1519 template<typename... _Args>
1520#if __cplusplus > 201402L
1521 reference
1522#else
1523 void
1524#endif
1525 emplace_front(_Args&&... __args);
1526#endif
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537 void
1539 {
1540 if (this->_M_impl._M_finish._M_cur
1541 != this->_M_impl._M_finish._M_last - 1)
1542 {
1543 _Alloc_traits::construct(this->_M_impl,
1544 this->_M_impl._M_finish._M_cur, __x);
1545 ++this->_M_impl._M_finish._M_cur;
1546 }
1547 else
1549 }
1550
1551#if __cplusplus >= 201103L
1552 void
1554 { emplace_back(std::move(__x)); }
1555
1556 template<typename... _Args>
1557#if __cplusplus > 201402L
1558 reference
1559#else
1560 void
1561#endif
1562 emplace_back(_Args&&... __args);
1563#endif
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573 void
1575 {
1576 __glibcxx_requires_nonempty();
1577 if (this->_M_impl._M_start._M_cur
1578 != this->_M_impl._M_start._M_last - 1)
1579 {
1580 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1581 this->_M_impl._M_start._M_cur);
1582 ++this->_M_impl._M_start._M_cur;
1583 }
1584 else
1586 }
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596 void
1598 {
1599 __glibcxx_requires_nonempty();
1600 if (this->_M_impl._M_finish._M_cur
1601 != this->_M_impl._M_finish._M_first)
1602 {
1603 --this->_M_impl._M_finish._M_cur;
1604 _Alloc_traits::destroy(_M_get_Tp_allocator(),
1605 this->_M_impl._M_finish._M_cur);
1606 }
1607 else
1609 }
1610
1611#if __cplusplus >= 201103L
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621 template<typename... _Args>
1623 emplace(const_iterator __position, _Args&&... __args);
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1635 insert(const_iterator __position, const value_type& __x);
1636#else
1637
1638
1639
1640
1641
1642
1643
1644
1645
1648#endif
1649
1650#if __cplusplus >= 201103L
1651
1652
1653
1654
1655
1656
1657
1658
1659
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1676 {
1677 auto __offset = __p - cbegin();
1678 _M_range_insert_aux(__p._M_const_cast(), __l.begin(), __l.end(),
1680 return begin() + __offset;
1681 }
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1695 {
1696 difference_type __offset = __position - cbegin();
1697 _M_fill_insert(__position._M_const_cast(), __n, __x);
1698 return begin() + __offset;
1699 }
1700#else
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710 void
1711 insert(iterator __position, size_type __n, const value_type& __x)
1712 { _M_fill_insert(__position, __n, __x); }
1713#endif
1714
1715#if __cplusplus >= 201103L
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727 template<typename _InputIterator,
1728 typename = std::_RequireInputIter<_InputIterator>>
1729 iterator
1731 _InputIterator __last)
1732 {
1733 difference_type __offset = __position - cbegin();
1734 _M_range_insert_aux(__position._M_const_cast(), __first, __last,
1736 return begin() + __offset;
1737 }
1738#else
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749 template<typename _InputIterator>
1750 void
1752 _InputIterator __last)
1753 {
1754
1755 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1756 _M_insert_dispatch(__position, __first, __last, _Integral());
1757 }
1758#endif
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773 iterator
1774#if __cplusplus >= 201103L
1776#else
1778#endif
1779 { return _M_erase(__position._M_const_cast()); }
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1798#if __cplusplus >= 201103L
1800#else
1802#endif
1803 { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816 void
1818 {
1819#if __cplusplus >= 201103L
1820 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1821 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1822#endif
1823 _M_impl._M_swap_data(__x._M_impl);
1824 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1825 __x._M_get_Tp_allocator());
1826 }
1827
1828
1829
1830
1831
1832
1833
1834 void
1836 { _M_erase_at_end(begin()); }
1837
1838 protected:
1839
1840
1841#if __cplusplus < 201103L
1842
1843
1844
1845
1846 template<typename _Integer>
1847 void
1848 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1849 {
1850 _M_initialize_map(_S_check_init_len(static_cast<size_type>(__n),
1851 _M_get_Tp_allocator()));
1853 }
1854
1855
1856 template<typename _InputIterator>
1857 void
1858 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1859 __false_type)
1860 {
1863 }
1864#endif
1865
1866 static size_t
1867 _S_check_init_len(size_t __n, const allocator_type& __a)
1868 {
1869 if (__n > _S_max_size(__a))
1870 __throw_length_error(
1871 __N("cannot create std::deque larger than max_size()"));
1872 return __n;
1873 }
1874
1875 static size_type
1876 _S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
1877 {
1878 const size_t __diffmax = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max;
1880 return (std::min)(__diffmax, __allocmax);
1881 }
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895 template<typename _InputIterator>
1896 void
1899
1900
1901 template<typename _ForwardIterator>
1902 void
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917 void
1919
1920#if __cplusplus >= 201103L
1921
1922 void
1923 _M_default_initialize();
1924#endif
1925
1926
1927
1928
1929#if __cplusplus < 201103L
1930
1931
1932
1933
1934 template<typename _Integer>
1935 void
1936 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1937 { _M_fill_assign(__n, __val); }
1938
1939
1940 template<typename _InputIterator>
1941 void
1942 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1943 __false_type)
1945#endif
1946
1947
1948 template<typename _InputIterator>
1949 void
1950 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1952
1953
1954 template<typename _ForwardIterator>
1955 void
1956 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1958 {
1959 const size_type __len = std::distance(__first, __last);
1960 if (__len > size())
1961 {
1962 _ForwardIterator __mid = __first;
1964 std::copy(__first, __mid, begin());
1965 _M_range_insert_aux(end(), __mid, __last,
1967 }
1968 else
1969 _M_erase_at_end(std::copy(__first, __last, begin()));
1970 }
1971
1972
1973
1974 void
1975 _M_fill_assign(size_type __n, const value_type& __val)
1976 {
1977 if (__n > size())
1978 {
1979 std::fill(begin(), end(), __val);
1980 _M_fill_insert(end(), __n - size(), __val);
1981 }
1982 else
1983 {
1984 _M_erase_at_end(begin() + difference_type(__n));
1985 std::fill(begin(), end(), __val);
1986 }
1987 }
1988
1989
1990
1991#if __cplusplus < 201103L
1993
1995#else
1996 template<typename... _Args>
1998
1999 template<typename... _Args>
2001#endif
2002
2004
2006
2007
2008
2009
2010
2011#if __cplusplus < 201103L
2012
2013
2014
2015
2016 template<typename _Integer>
2017 void
2018 _M_insert_dispatch(iterator __pos,
2019 _Integer __n, _Integer __x, __true_type)
2020 { _M_fill_insert(__pos, __n, __x); }
2021
2022
2023 template<typename _InputIterator>
2024 void
2025 _M_insert_dispatch(iterator __pos,
2026 _InputIterator __first, _InputIterator __last,
2027 __false_type)
2028 {
2029 _M_range_insert_aux(__pos, __first, __last,
2031 }
2032#endif
2033
2034
2035 template<typename _InputIterator>
2036 void
2037 _M_range_insert_aux(iterator __pos, _InputIterator __first,
2039
2040
2041 template<typename _ForwardIterator>
2042 void
2043 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
2045
2046
2047
2048
2049 void
2050 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
2051
2052
2053#if __cplusplus < 201103L
2054 iterator
2055 _M_insert_aux(iterator __pos, const value_type& __x);
2056#else
2057 template<typename... _Args>
2058 iterator
2059 _M_insert_aux(iterator __pos, _Args&&... __args);
2060#endif
2061
2062
2063 void
2064 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
2065
2066
2067 template<typename _ForwardIterator>
2068 void
2069 _M_insert_aux(iterator __pos,
2070 _ForwardIterator __first, _ForwardIterator __last,
2071 size_type __n);
2072
2073
2074
2075
2076 void
2077 _M_destroy_data_aux(iterator __first, iterator __last);
2078
2079
2080
2081 template<typename _Alloc1>
2082 void
2083 _M_destroy_data(iterator __first, iterator __last, const _Alloc1&)
2084 { _M_destroy_data_aux(__first, __last); }
2085
2086 void
2087 _M_destroy_data(iterator __first, iterator __last,
2089 {
2090 if (!__has_trivial_destructor(value_type))
2091 _M_destroy_data_aux(__first, __last);
2092 }
2093
2094
2095 void
2096 _M_erase_at_begin(iterator __pos)
2097 {
2098 _M_destroy_data(begin(), __pos, _M_get_Tp_allocator());
2099 _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
2100 this->_M_impl._M_start = __pos;
2101 }
2102
2103
2104
2105 void
2106 _M_erase_at_end(iterator __pos)
2107 {
2108 _M_destroy_data(__pos, end(), _M_get_Tp_allocator());
2109 _M_destroy_nodes(__pos._M_node + 1,
2110 this->_M_impl._M_finish._M_node + 1);
2111 this->_M_impl._M_finish = __pos;
2112 }
2113
2114 iterator
2115 _M_erase(iterator __pos);
2116
2117 iterator
2118 _M_erase(iterator __first, iterator __last);
2119
2120#if __cplusplus >= 201103L
2121
2122 void
2123 _M_default_append(size_type __n);
2124
2125 bool
2126 _M_shrink_to_fit();
2127#endif
2128
2129
2130
2131 iterator
2133 {
2134 const size_type __vacancies = this->_M_impl._M_start._M_cur
2135 - this->_M_impl._M_start._M_first;
2136 if (__n > __vacancies)
2138 return this->_M_impl._M_start - difference_type(__n);
2139 }
2140
2143 {
2144 const size_type __vacancies = (this->_M_impl._M_finish._M_last
2145 - this->_M_impl._M_finish._M_cur) - 1;
2146 if (__n > __vacancies)
2148 return this->_M_impl._M_finish + difference_type(__n);
2149 }
2150
2151 void
2153
2154 void
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167 void
2169 {
2170 if (__nodes_to_add + 1 > this->_M_impl._M_map_size
2171 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
2173 }
2174
2175 void
2177 {
2178 if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
2179 - this->_M_impl._M_map))
2181 }
2182
2183 void
2184 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
2185
2186
2187#if __cplusplus >= 201103L
2188
2189
2190 void
2191 _M_move_assign1(deque&& __x, true_type) noexcept
2192 {
2193 this->_M_impl._M_swap_data(__x._M_impl);
2194 __x.clear();
2195 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
2196 }
2197
2198
2199
2200
2201 void
2202 _M_move_assign1(deque&& __x, false_type)
2203 {
2204 if (_M_get_Tp_allocator() == __x._M_get_Tp_allocator())
2206
2207 constexpr bool __move_storage =
2208 _Alloc_traits::_S_propagate_on_move_assign();
2209 _M_move_assign2(std::move(__x), __bool_constant<__move_storage>());
2210 }
2211
2212
2213
2214 template<typename... _Args>
2215 void
2216 _M_replace_map(_Args&&... __args)
2217 {
2218
2219 deque __newobj(std::forward<_Args>(__args)...);
2220
2222 _M_deallocate_node(*begin()._M_node);
2223 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
2224 this->_M_impl._M_map = nullptr;
2225 this->_M_impl._M_map_size = 0;
2226
2227 this->_M_impl._M_swap_data(__newobj._M_impl);
2228 }
2229
2230
2231 void
2232 _M_move_assign2(deque&& __x, true_type)
2233 {
2234
2235 auto __alloc = __x._M_get_Tp_allocator();
2236
2237
2239
2240 _M_get_Tp_allocator() = std::move(__alloc);
2241 }
2242
2243
2244
2245 void
2246 _M_move_assign2(deque&& __x, false_type)
2247 {
2248 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
2249 {
2250
2251
2252 _M_replace_map(std::move(__x), __x.get_allocator());
2253 }
2254 else
2255 {
2256
2257
2258 _M_assign_aux(std::make_move_iterator(__x.begin()),
2259 std::make_move_iterator(__x.end()),
2261 __x.clear();
2262 }
2263 }
2264#endif
2265 };
2266
2267#if __cpp_deduction_guides >= 201606
2268 template<typename _InputIterator, typename _ValT
2269 = typename iterator_traits<_InputIterator>::value_type,
2270 typename _Allocator = allocator<_ValT>,
2271 typename = _RequireInputIter<_InputIterator>,
2272 typename = _RequireAllocator<_Allocator>>
2273 deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
2274 -> deque<_ValT, _Allocator>;
2275#endif
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287 template<typename _Tp, typename _Alloc>
2288 _GLIBCXX_NODISCARD
2289 inline bool
2291 { return __x.size() == __y.size()
2292 && std::equal(__x.begin(), __x.end(), __y.begin()); }
2293
2294#if __cpp_lib_three_way_comparison
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306 template<typename _Tp, typename _Alloc>
2307 [[nodiscard]]
2308 inline __detail::__synth3way_t<_Tp>
2309 operator<=>(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2310 {
2312 __y.begin(), __y.end(),
2313 __detail::__synth3way);
2314 }
2315#else
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327 template<typename _Tp, typename _Alloc>
2328 _GLIBCXX_NODISCARD
2329 inline bool
2330 operator<(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2331 { return std::lexicographical_compare(__x.begin(), __x.end(),
2332 __y.begin(), __y.end()); }
2333
2334
2335 template<typename _Tp, typename _Alloc>
2336 _GLIBCXX_NODISCARD
2337 inline bool
2338 operator!=(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2339 { return !(__x == __y); }
2340
2341
2342 template<typename _Tp, typename _Alloc>
2343 _GLIBCXX_NODISCARD
2344 inline bool
2345 operator>(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2346 { return __y < __x; }
2347
2348
2349 template<typename _Tp, typename _Alloc>
2350 _GLIBCXX_NODISCARD
2351 inline bool
2352 operator<=(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2353 { return !(__y < __x); }
2354
2355
2356 template<typename _Tp, typename _Alloc>
2357 _GLIBCXX_NODISCARD
2358 inline bool
2359 operator>=(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
2360 { return !(__x < __y); }
2361#endif
2362
2363
2364 template<typename _Tp, typename _Alloc>
2365 inline void
2367 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
2368 { __x.swap(__y); }
2369
2370#undef _GLIBCXX_DEQUE_BUF_SIZE
2371
2372_GLIBCXX_END_NAMESPACE_CONTAINER
2373
2374#if __cplusplus >= 201103L
2375
2376
2377 template<class _Tp>
2378 struct __is_bitwise_relocatable<_GLIBCXX_STD_C::deque<_Tp>>
2380#endif
2381
2382_GLIBCXX_END_NAMESPACE_VERSION
2383}
2384
2385#endif
#define _GLIBCXX_DEQUE_BUF_SIZE
This function controls the size of memory nodes.
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
__bool_constant< false > false_type
The type used as a compile-time boolean with false value.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr auto lexicographical_compare_three_way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Comp __comp) -> decltype(__comp(*__first1, *__first2))
Performs dictionary comparison on ranges.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
typename pointer_traits< _Ptr >::template rebind< _Tp > __ptr_rebind
Convenience alias for rebinding pointers.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
is_nothrow_default_constructible
typename __detected_or_t< is_empty< _Alloc >, __equal, _Alloc >::type is_always_equal
Whether all instances of the allocator type compare equal.
The standard allocator, as per C++03 [20.4.1].
void _M_set_node(_Map_pointer __new_node) noexcept
void _M_initialize_map(size_t)
Layout storage.
A standard container using fixed-size memory allocation and constant-time manipulation of elements at...
reverse_iterator rbegin() noexcept
deque(const deque &__x)
Deque copy constructor.
const_reference at(size_type __n) const
Provides access to the data contained in the deque.
reverse_iterator rend() noexcept
iterator erase(const_iterator __position)
Remove element at given position.
const_reference back() const noexcept
const_reverse_iterator crend() const noexcept
void _M_pop_front_aux()
Helper functions for push_* and pop_*.
void pop_back() noexcept
Removes last element.
size_type size() const noexcept
void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
Memory-handling helpers for the major map.
const_iterator cbegin() const noexcept
void resize(size_type __new_size)
Resizes the deque to the specified number of elements.
const_reverse_iterator rend() const noexcept
iterator _M_reserve_elements_at_front(size_type __n)
Memory-handling helpers for the previous internal insert functions.
iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in deque before specified iterator.
void pop_front() noexcept
Removes first element.
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
void swap(deque &__x) noexcept
Swaps data with another deque.
reference operator[](size_type __n) noexcept
Subscript access to the data contained in the deque.
reference at(size_type __n)
Provides access to the data contained in the deque.
deque(size_type __n, const allocator_type &__a=allocator_type())
Creates a deque with default constructed elements.
bool empty() const noexcept
const_reference operator[](size_type __n) const noexcept
Subscript access to the data contained in the deque.
size_type max_size() const noexcept
void push_front(const value_type &__x)
Add data to the front of the deque.
void resize(size_type __new_size, const value_type &__x)
Resizes the deque to the specified number of elements.
const_reference front() const noexcept
void assign(size_type __n, const value_type &__val)
Assigns a given value to a deque.
deque & operator=(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
void _M_fill_initialize(const value_type &__value)
Fills the deque with copies of value.
iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into deque before specified iterator.
deque(const deque &__x, const __type_identity_t< allocator_type > &__a)
Copy constructor with alternative allocator.
void _M_new_elements_at_back(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
iterator insert(const_iterator __p, initializer_list< value_type > __l)
Inserts an initializer list into the deque.
deque(size_type __n, const value_type &__value, const allocator_type &__a=allocator_type())
Creates a deque with copies of an exemplar element.
const_reverse_iterator crbegin() const noexcept
void _M_reserve_map_at_back(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
reference back() noexcept
void _M_new_elements_at_front(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
deque()=default
Creates a deque with no elements.
void _M_push_back_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
deque & operator=(deque &&__x) noexcept(_Alloc_traits::_S_always_equal())
Deque move assignment operator.
void push_back(const value_type &__x)
Add data to the end of the deque.
deque(const allocator_type &__a)
Creates a deque with no elements.
void _M_reserve_map_at_front(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
void _M_push_front_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
void _M_range_check(size_type __n) const
Safety check used only from at().
void assign(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
deque(initializer_list< value_type > __l, const allocator_type &__a=allocator_type())
Builds a deque from an initializer list.
void shrink_to_fit() noexcept
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a deque.
deque(_InputIterator __first, _InputIterator __last, const allocator_type &__a=allocator_type())
Builds a deque from a range.
const_iterator begin() const noexcept
deque & operator=(const deque &__x)
Deque assignment operator.
const_iterator end() const noexcept
iterator insert(const_iterator __position, size_type __n, const value_type &__x)
Inserts a number of copies of given data into the deque.
iterator insert(const_iterator __position, value_type &&__x)
Inserts given rvalue into deque before specified iterator.
void _M_pop_back_aux()
Helper functions for push_* and pop_*.
void _M_range_initialize(_InputIterator __first, _InputIterator __last, std::input_iterator_tag)
Fills the deque with whatever is in [first,last).
reference front() noexcept
iterator _M_reserve_elements_at_back(size_type __n)
Memory-handling helpers for the previous internal insert functions.
const_iterator cend() const noexcept
iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
Inserts a range into the deque.
const_reverse_iterator rbegin() const noexcept
deque(deque &&__x, const __type_identity_t< allocator_type > &__a)
Move constructor with alternative allocator.
iterator begin() noexcept
iterator erase(const_iterator __first, const_iterator __last)
Remove a range of elements.
deque(deque &&)=default
Deque move constructor.
Forward iterators support a superset of input iterator operations.
Random-access iterators support a superset of bidirectional iterator operations.
Uniform interface to C++98 and C++11 allocators.
static constexpr pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
static constexpr size_type max_size(const _Tp_alloc_type &__a) noexcept
The maximum supported allocation size.