00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057 #ifndef _STL_LIST_H
00058 #define _STL_LIST_H 1
00059
00060 #include <bits/concept_check.h>
00061 #include <initializer_list>
00062
00063 namespace std _GLIBCXX_VISIBILITY(default)
00064 {
00065 namespace __detail
00066 {
00067 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00068
00069
00070
00071
00072
00073
00074
00075
00076 struct _List_node_base
00077 {
00078 _List_node_base* _M_next;
00079 _List_node_base* _M_prev;
00080
00081 static void
00082 swap(_List_node_base& __x, _List_node_base& __y) throw ();
00083
00084 void
00085 _M_transfer(_List_node_base* const __first,
00086 _List_node_base* const __last) throw ();
00087
00088 void
00089 _M_reverse() throw ();
00090
00091 void
00092 _M_hook(_List_node_base* const __position) throw ();
00093
00094 void
00095 _M_unhook() throw ();
00096 };
00097
00098 _GLIBCXX_END_NAMESPACE_VERSION
00099 }
00100
00101 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00102
00103
00104 template<typename _Tp>
00105 struct _List_node : public __detail::_List_node_base
00106 {
00107
00108 _Tp _M_data;
00109
00110 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00111 template<typename... _Args>
00112 _List_node(_Args&&... __args)
00113 : __detail::_List_node_base(), _M_data(std::forward<_Args>(__args)...)
00114 { }
00115 #endif
00116 };
00117
00118
00119
00120
00121
00122
00123 template<typename _Tp>
00124 struct _List_iterator
00125 {
00126 typedef _List_iterator<_Tp> _Self;
00127 typedef _List_node<_Tp> _Node;
00128
00129 typedef ptrdiff_t difference_type;
00130 typedef std::bidirectional_iterator_tag iterator_category;
00131 typedef _Tp value_type;
00132 typedef _Tp* pointer;
00133 typedef _Tp& reference;
00134
00135 _List_iterator()
00136 : _M_node() { }
00137
00138 explicit
00139 _List_iterator(__detail::_List_node_base* __x)
00140 : _M_node(__x) { }
00141
00142
00143 reference
00144 operator*() const
00145 { return static_cast<_Node*>(_M_node)->_M_data; }
00146
00147 pointer
00148 operator->() const
00149 { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); }
00150
00151 _Self&
00152 operator++()
00153 {
00154 _M_node = _M_node->_M_next;
00155 return *this;
00156 }
00157
00158 _Self
00159 operator++(int)
00160 {
00161 _Self __tmp = *this;
00162 _M_node = _M_node->_M_next;
00163 return __tmp;
00164 }
00165
00166 _Self&
00167 operator--()
00168 {
00169 _M_node = _M_node->_M_prev;
00170 return *this;
00171 }
00172
00173 _Self
00174 operator--(int)
00175 {
00176 _Self __tmp = *this;
00177 _M_node = _M_node->_M_prev;
00178 return __tmp;
00179 }
00180
00181 bool
00182 operator==(const _Self& __x) const
00183 { return _M_node == __x._M_node; }
00184
00185 bool
00186 operator!=(const _Self& __x) const
00187 { return _M_node != __x._M_node; }
00188
00189
00190 __detail::_List_node_base* _M_node;
00191 };
00192
00193
00194
00195
00196
00197
00198 template<typename _Tp>
00199 struct _List_const_iterator
00200 {
00201 typedef _List_const_iterator<_Tp> _Self;
00202 typedef const _List_node<_Tp> _Node;
00203 typedef _List_iterator<_Tp> iterator;
00204
00205 typedef ptrdiff_t difference_type;
00206 typedef std::bidirectional_iterator_tag iterator_category;
00207 typedef _Tp value_type;
00208 typedef const _Tp* pointer;
00209 typedef const _Tp& reference;
00210
00211 _List_const_iterator()
00212 : _M_node() { }
00213
00214 explicit
00215 _List_const_iterator(const __detail::_List_node_base* __x)
00216 : _M_node(__x) { }
00217
00218 _List_const_iterator(const iterator& __x)
00219 : _M_node(__x._M_node) { }
00220
00221
00222
00223 reference
00224 operator*() const
00225 { return static_cast<_Node*>(_M_node)->_M_data; }
00226
00227 pointer
00228 operator->() const
00229 { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); }
00230
00231 _Self&
00232 operator++()
00233 {
00234 _M_node = _M_node->_M_next;
00235 return *this;
00236 }
00237
00238 _Self
00239 operator++(int)
00240 {
00241 _Self __tmp = *this;
00242 _M_node = _M_node->_M_next;
00243 return __tmp;
00244 }
00245
00246 _Self&
00247 operator--()
00248 {
00249 _M_node = _M_node->_M_prev;
00250 return *this;
00251 }
00252
00253 _Self
00254 operator--(int)
00255 {
00256 _Self __tmp = *this;
00257 _M_node = _M_node->_M_prev;
00258 return __tmp;
00259 }
00260
00261 bool
00262 operator==(const _Self& __x) const
00263 { return _M_node == __x._M_node; }
00264
00265 bool
00266 operator!=(const _Self& __x) const
00267 { return _M_node != __x._M_node; }
00268
00269
00270 const __detail::_List_node_base* _M_node;
00271 };
00272
00273 template<typename _Val>
00274 inline bool
00275 operator==(const _List_iterator<_Val>& __x,
00276 const _List_const_iterator<_Val>& __y)
00277 { return __x._M_node == __y._M_node; }
00278
00279 template<typename _Val>
00280 inline bool
00281 operator!=(const _List_iterator<_Val>& __x,
00282 const _List_const_iterator<_Val>& __y)
00283 { return __x._M_node != __y._M_node; }
00284
00285
00286
00287 template<typename _Tp, typename _Alloc>
00288 class _List_base
00289 {
00290 protected:
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304 typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
00305 _Node_alloc_type;
00306
00307 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
00308
00309 struct _List_impl
00310 : public _Node_alloc_type
00311 {
00312 __detail::_List_node_base _M_node;
00313
00314 _List_impl()
00315 : _Node_alloc_type(), _M_node()
00316 { }
00317
00318 _List_impl(const _Node_alloc_type& __a)
00319 : _Node_alloc_type(__a), _M_node()
00320 { }
00321 };
00322
00323 _List_impl _M_impl;
00324
00325 _List_node<_Tp>*
00326 _M_get_node()
00327 { return _M_impl._Node_alloc_type::allocate(1); }
00328
00329 void
00330 _M_put_node(_List_node<_Tp>* __p)
00331 { _M_impl._Node_alloc_type::deallocate(__p, 1); }
00332
00333 public:
00334 typedef _Alloc allocator_type;
00335
00336 _Node_alloc_type&
00337 _M_get_Node_allocator()
00338 { return *static_cast<_Node_alloc_type*>(&this->_M_impl); }
00339
00340 const _Node_alloc_type&
00341 _M_get_Node_allocator() const
00342 { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
00343
00344 _Tp_alloc_type
00345 _M_get_Tp_allocator() const
00346 { return _Tp_alloc_type(_M_get_Node_allocator()); }
00347
00348 allocator_type
00349 get_allocator() const
00350 { return allocator_type(_M_get_Node_allocator()); }
00351
00352 _List_base()
00353 : _M_impl()
00354 { _M_init(); }
00355
00356 _List_base(const allocator_type& __a)
00357 : _M_impl(__a)
00358 { _M_init(); }
00359
00360 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00361 _List_base(_List_base&& __x)
00362 : _M_impl(__x._M_get_Node_allocator())
00363 {
00364 _M_init();
00365 __detail::_List_node_base::swap(this->_M_impl._M_node,
00366 __x._M_impl._M_node);
00367 }
00368 #endif
00369
00370
00371 ~_List_base()
00372 { _M_clear(); }
00373
00374 void
00375 _M_clear();
00376
00377 void
00378 _M_init()
00379 {
00380 this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
00381 this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
00382 }
00383 };
00384
00385
00386
00387
00388
00389
00390
00391
00392
00393
00394
00395
00396
00397
00398
00399
00400
00401
00402
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414
00415
00416
00417
00418
00419
00420
00421
00422
00423
00424
00425
00426
00427
00428 template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
00429 class list : protected _List_base<_Tp, _Alloc>
00430 {
00431
00432 typedef typename _Alloc::value_type _Alloc_value_type;
00433 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00434 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
00435
00436 typedef _List_base<_Tp, _Alloc> _Base;
00437 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
00438
00439 public:
00440 typedef _Tp value_type;
00441 typedef typename _Tp_alloc_type::pointer pointer;
00442 typedef typename _Tp_alloc_type::const_pointer const_pointer;
00443 typedef typename _Tp_alloc_type::reference reference;
00444 typedef typename _Tp_alloc_type::const_reference const_reference;
00445 typedef _List_iterator<_Tp> iterator;
00446 typedef _List_const_iterator<_Tp> const_iterator;
00447 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00448 typedef std::reverse_iterator<iterator> reverse_iterator;
00449 typedef size_t size_type;
00450 typedef ptrdiff_t difference_type;
00451 typedef _Alloc allocator_type;
00452
00453 protected:
00454
00455
00456 typedef _List_node<_Tp> _Node;
00457
00458 using _Base::_M_impl;
00459 using _Base::_M_put_node;
00460 using _Base::_M_get_node;
00461 using _Base::_M_get_Tp_allocator;
00462 using _Base::_M_get_Node_allocator;
00463
00464
00465
00466
00467
00468
00469 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00470 _Node*
00471 _M_create_node(const value_type& __x)
00472 {
00473 _Node* __p = this->_M_get_node();
00474 __try
00475 {
00476 _M_get_Tp_allocator().construct
00477 (std::__addressof(__p->_M_data), __x);
00478 }
00479 __catch(...)
00480 {
00481 _M_put_node(__p);
00482 __throw_exception_again;
00483 }
00484 return __p;
00485 }
00486 #else
00487 template<typename... _Args>
00488 _Node*
00489 _M_create_node(_Args&&... __args)
00490 {
00491 _Node* __p = this->_M_get_node();
00492 __try
00493 {
00494 _M_get_Node_allocator().construct(__p,
00495 std::forward<_Args>(__args)...);
00496 }
00497 __catch(...)
00498 {
00499 _M_put_node(__p);
00500 __throw_exception_again;
00501 }
00502 return __p;
00503 }
00504 #endif
00505
00506 public:
00507
00508
00509
00510
00511
00512 list()
00513 : _Base() { }
00514
00515
00516
00517
00518
00519 explicit
00520 list(const allocator_type& __a)
00521 : _Base(__a) { }
00522
00523 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00524
00525
00526
00527
00528
00529
00530
00531 explicit
00532 list(size_type __n)
00533 : _Base()
00534 { _M_default_initialize(__n); }
00535
00536
00537
00538
00539
00540
00541
00542
00543
00544 list(size_type __n, const value_type& __value,
00545 const allocator_type& __a = allocator_type())
00546 : _Base(__a)
00547 { _M_fill_initialize(__n, __value); }
00548 #else
00549
00550
00551
00552
00553
00554
00555
00556
00557 explicit
00558 list(size_type __n, const value_type& __value = value_type(),
00559 const allocator_type& __a = allocator_type())
00560 : _Base(__a)
00561 { _M_fill_initialize(__n, __value); }
00562 #endif
00563
00564
00565
00566
00567
00568
00569
00570
00571 list(const list& __x)
00572 : _Base(__x._M_get_Node_allocator())
00573 { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
00574
00575 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00576
00577
00578
00579
00580
00581
00582
00583 list(list&& __x)
00584 : _Base(std::move(__x)) { }
00585
00586
00587
00588
00589
00590
00591
00592
00593
00594 list(initializer_list<value_type> __l,
00595 const allocator_type& __a = allocator_type())
00596 : _Base(__a)
00597 { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); }
00598 #endif
00599
00600
00601
00602
00603
00604
00605
00606
00607
00608
00609
00610 template<typename _InputIterator>
00611 list(_InputIterator __first, _InputIterator __last,
00612 const allocator_type& __a = allocator_type())
00613 : _Base(__a)
00614 {
00615
00616 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00617 _M_initialize_dispatch(__first, __last, _Integral());
00618 }
00619
00620
00621
00622
00623
00624
00625
00626
00627
00628
00629
00630
00631
00632
00633
00634
00635 list&
00636 operator=(const list& __x);
00637
00638 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00639
00640
00641
00642
00643
00644
00645
00646 list&
00647 operator=(list&& __x)
00648 {
00649
00650
00651 this->clear();
00652 this->swap(__x);
00653 return *this;
00654 }
00655
00656
00657
00658
00659
00660
00661
00662
00663 list&
00664 operator=(initializer_list<value_type> __l)
00665 {
00666 this->assign(__l.begin(), __l.end());
00667 return *this;
00668 }
00669 #endif
00670
00671
00672
00673
00674
00675
00676
00677
00678
00679
00680
00681 void
00682 assign(size_type __n, const value_type& __val)
00683 { _M_fill_assign(__n, __val); }
00684
00685
00686
00687
00688
00689
00690
00691
00692
00693
00694
00695
00696
00697 template<typename _InputIterator>
00698 void
00699 assign(_InputIterator __first, _InputIterator __last)
00700 {
00701
00702 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00703 _M_assign_dispatch(__first, __last, _Integral());
00704 }
00705
00706 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00707
00708
00709
00710
00711
00712
00713
00714 void
00715 assign(initializer_list<value_type> __l)
00716 { this->assign(__l.begin(), __l.end()); }
00717 #endif
00718
00719
00720 allocator_type
00721 get_allocator() const
00722 { return _Base::get_allocator(); }
00723
00724
00725
00726
00727
00728
00729 iterator
00730 begin()
00731 { return iterator(this->_M_impl._M_node._M_next); }
00732
00733
00734
00735
00736
00737
00738 const_iterator
00739 begin() const
00740 { return const_iterator(this->_M_impl._M_node._M_next); }
00741
00742
00743
00744
00745
00746
00747 iterator
00748 end()
00749 { return iterator(&this->_M_impl._M_node); }
00750
00751
00752
00753
00754
00755
00756 const_iterator
00757 end() const
00758 { return const_iterator(&this->_M_impl._M_node); }
00759
00760
00761
00762
00763
00764
00765 reverse_iterator
00766 rbegin()
00767 { return reverse_iterator(end()); }
00768
00769
00770
00771
00772
00773
00774 const_reverse_iterator
00775 rbegin() const
00776 { return const_reverse_iterator(end()); }
00777
00778
00779
00780
00781
00782
00783 reverse_iterator
00784 rend()
00785 { return reverse_iterator(begin()); }
00786
00787
00788
00789
00790
00791
00792 const_reverse_iterator
00793 rend() const
00794 { return const_reverse_iterator(begin()); }
00795
00796 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00797
00798
00799
00800
00801
00802 const_iterator
00803 cbegin() const
00804 { return const_iterator(this->_M_impl._M_node._M_next); }
00805
00806
00807
00808
00809
00810
00811 const_iterator
00812 cend() const
00813 { return const_iterator(&this->_M_impl._M_node); }
00814
00815
00816
00817
00818
00819
00820 const_reverse_iterator
00821 crbegin() const
00822 { return const_reverse_iterator(end()); }
00823
00824
00825
00826
00827
00828
00829 const_reverse_iterator
00830 crend() const
00831 { return const_reverse_iterator(begin()); }
00832 #endif
00833
00834
00835
00836
00837
00838
00839 bool
00840 empty() const
00841 { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
00842
00843
00844 size_type
00845 size() const
00846 { return std::distance(begin(), end()); }
00847
00848
00849 size_type
00850 max_size() const
00851 { return _M_get_Node_allocator().max_size(); }
00852
00853 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00854
00855
00856
00857
00858
00859
00860
00861
00862
00863 void
00864 resize(size_type __new_size);
00865
00866
00867
00868
00869
00870
00871
00872
00873
00874
00875
00876 void
00877 resize(size_type __new_size, const value_type& __x);
00878 #else
00879
00880
00881
00882
00883
00884
00885
00886
00887
00888
00889 void
00890 resize(size_type __new_size, value_type __x = value_type());
00891 #endif
00892
00893
00894
00895
00896
00897
00898 reference
00899 front()
00900 { return *begin(); }
00901
00902
00903
00904
00905
00906 const_reference
00907 front() const
00908 { return *begin(); }
00909
00910
00911
00912
00913
00914 reference
00915 back()
00916 {
00917 iterator __tmp = end();
00918 --__tmp;
00919 return *__tmp;
00920 }
00921
00922
00923
00924
00925
00926 const_reference
00927 back() const
00928 {
00929 const_iterator __tmp = end();
00930 --__tmp;
00931 return *__tmp;
00932 }
00933
00934
00935
00936
00937
00938
00939
00940
00941
00942
00943
00944
00945 void
00946 push_front(const value_type& __x)
00947 { this->_M_insert(begin(), __x); }
00948
00949 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00950 void
00951 push_front(value_type&& __x)
00952 { this->_M_insert(begin(), std::move(__x)); }
00953
00954 template<typename... _Args>
00955 void
00956 emplace_front(_Args&&... __args)
00957 { this->_M_insert(begin(), std::forward<_Args>(__args)...); }
00958 #endif
00959
00960
00961
00962
00963
00964
00965
00966
00967
00968
00969
00970
00971
00972 void
00973 pop_front()
00974 { this->_M_erase(begin()); }
00975
00976
00977
00978
00979
00980
00981
00982
00983
00984
00985
00986 void
00987 push_back(const value_type& __x)
00988 { this->_M_insert(end(), __x); }
00989
00990 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00991 void
00992 push_back(value_type&& __x)
00993 { this->_M_insert(end(), std::move(__x)); }
00994
00995 template<typename... _Args>
00996 void
00997 emplace_back(_Args&&... __args)
00998 { this->_M_insert(end(), std::forward<_Args>(__args)...); }
00999 #endif
01000
01001
01002
01003
01004
01005
01006
01007
01008
01009
01010
01011
01012 void
01013 pop_back()
01014 { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); }
01015
01016 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01017
01018
01019
01020
01021
01022
01023
01024
01025
01026
01027
01028
01029 template<typename... _Args>
01030 iterator
01031 emplace(iterator __position, _Args&&... __args);
01032 #endif
01033
01034
01035
01036
01037
01038
01039
01040
01041
01042
01043
01044
01045 iterator
01046 insert(iterator __position, const value_type& __x);
01047
01048 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01049
01050
01051
01052
01053
01054
01055
01056
01057
01058
01059
01060 iterator
01061 insert(iterator __position, value_type&& __x)
01062 { return emplace(__position, std::move(__x)); }
01063
01064
01065
01066
01067
01068
01069
01070
01071
01072
01073
01074
01075
01076
01077 void
01078 insert(iterator __p, initializer_list<value_type> __l)
01079 { this->insert(__p, __l.begin(), __l.end()); }
01080 #endif
01081
01082
01083
01084
01085
01086
01087
01088
01089
01090
01091
01092
01093
01094 void
01095 insert(iterator __position, size_type __n, const value_type& __x)
01096 {
01097 list __tmp(__n, __x, _M_get_Node_allocator());
01098 splice(__position, __tmp);
01099 }
01100
01101
01102
01103
01104
01105
01106
01107
01108
01109
01110
01111
01112
01113
01114 template<typename _InputIterator>
01115 void
01116 insert(iterator __position, _InputIterator __first,
01117 _InputIterator __last)
01118 {
01119 list __tmp(__first, __last, _M_get_Node_allocator());
01120 splice(__position, __tmp);
01121 }
01122
01123
01124
01125
01126
01127
01128
01129
01130
01131
01132
01133
01134
01135
01136
01137
01138 iterator
01139 erase(iterator __position);
01140
01141
01142
01143
01144
01145
01146
01147
01148
01149
01150
01151
01152
01153
01154
01155
01156
01157
01158
01159 iterator
01160 erase(iterator __first, iterator __last)
01161 {
01162 while (__first != __last)
01163 __first = erase(__first);
01164 return __last;
01165 }
01166
01167
01168
01169
01170
01171
01172
01173
01174
01175
01176 void
01177 swap(list& __x)
01178 {
01179 __detail::_List_node_base::swap(this->_M_impl._M_node,
01180 __x._M_impl._M_node);
01181
01182
01183
01184 std::__alloc_swap<typename _Base::_Node_alloc_type>::
01185 _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator());
01186 }
01187
01188
01189
01190
01191
01192
01193
01194 void
01195 clear()
01196 {
01197 _Base::_M_clear();
01198 _Base::_M_init();
01199 }
01200
01201
01202
01203
01204
01205
01206
01207
01208
01209
01210
01211
01212
01213 void
01214 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01215 splice(iterator __position, list&& __x)
01216 #else
01217 splice(iterator __position, list& __x)
01218 #endif
01219 {
01220 if (!__x.empty())
01221 {
01222 _M_check_equal_allocators(__x);
01223
01224 this->_M_transfer(__position, __x.begin(), __x.end());
01225 }
01226 }
01227
01228 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01229 void
01230 splice(iterator __position, list& __x)
01231 { splice(__position, std::move(__x)); }
01232 #endif
01233
01234
01235
01236
01237
01238
01239
01240
01241
01242
01243 void
01244 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01245 splice(iterator __position, list&& __x, iterator __i)
01246 #else
01247 splice(iterator __position, list& __x, iterator __i)
01248 #endif
01249 {
01250 iterator __j = __i;
01251 ++__j;
01252 if (__position == __i || __position == __j)
01253 return;
01254
01255 if (this != &__x)
01256 _M_check_equal_allocators(__x);
01257
01258 this->_M_transfer(__position, __i, __j);
01259 }
01260
01261 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01262 void
01263 splice(iterator __position, list& __x, iterator __i)
01264 { splice(__position, std::move(__x), __i); }
01265 #endif
01266
01267
01268
01269
01270
01271
01272
01273
01274
01275
01276
01277
01278
01279 void
01280 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01281 splice(iterator __position, list&& __x, iterator __first,
01282 iterator __last)
01283 #else
01284 splice(iterator __position, list& __x, iterator __first,
01285 iterator __last)
01286 #endif
01287 {
01288 if (__first != __last)
01289 {
01290 if (this != &__x)
01291 _M_check_equal_allocators(__x);
01292
01293 this->_M_transfer(__position, __first, __last);
01294 }
01295 }
01296
01297 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01298 void
01299 splice(iterator __position, list& __x, iterator __first, iterator __last)
01300 { splice(__position, std::move(__x), __first, __last); }
01301 #endif
01302
01303
01304
01305
01306
01307
01308
01309
01310
01311
01312
01313
01314 void
01315 remove(const _Tp& __value);
01316
01317
01318
01319
01320
01321
01322
01323
01324
01325
01326
01327
01328 template<typename _Predicate>
01329 void
01330 remove_if(_Predicate);
01331
01332
01333
01334
01335
01336
01337
01338
01339
01340
01341
01342 void
01343 unique();
01344
01345
01346
01347
01348
01349
01350
01351
01352
01353
01354
01355
01356
01357 template<typename _BinaryPredicate>
01358 void
01359 unique(_BinaryPredicate);
01360
01361
01362
01363
01364
01365
01366
01367
01368
01369
01370 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01371 void
01372 merge(list&& __x);
01373
01374 void
01375 merge(list& __x)
01376 { merge(std::move(__x)); }
01377 #else
01378 void
01379 merge(list& __x);
01380 #endif
01381
01382
01383
01384
01385
01386
01387
01388
01389
01390
01391
01392
01393
01394 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01395 template<typename _StrictWeakOrdering>
01396 void
01397 merge(list&&, _StrictWeakOrdering);
01398
01399 template<typename _StrictWeakOrdering>
01400 void
01401 merge(list& __x, _StrictWeakOrdering __comp)
01402 { merge(std::move(__x), __comp); }
01403 #else
01404 template<typename _StrictWeakOrdering>
01405 void
01406 merge(list&, _StrictWeakOrdering);
01407 #endif
01408
01409
01410
01411
01412
01413
01414 void
01415 reverse()
01416 { this->_M_impl._M_node._M_reverse(); }
01417
01418
01419
01420
01421
01422
01423
01424 void
01425 sort();
01426
01427
01428
01429
01430
01431
01432
01433 template<typename _StrictWeakOrdering>
01434 void
01435 sort(_StrictWeakOrdering);
01436
01437 protected:
01438
01439
01440
01441
01442
01443
01444 template<typename _Integer>
01445 void
01446 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
01447 { _M_fill_initialize(static_cast<size_type>(__n), __x); }
01448
01449
01450 template<typename _InputIterator>
01451 void
01452 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
01453 __false_type)
01454 {
01455 for (; __first != __last; ++__first)
01456 push_back(*__first);
01457 }
01458
01459
01460
01461 void
01462 _M_fill_initialize(size_type __n, const value_type& __x)
01463 {
01464 for (; __n; --__n)
01465 push_back(__x);
01466 }
01467
01468 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01469
01470 void
01471 _M_default_initialize(size_type __n)
01472 {
01473 for (; __n; --__n)
01474 emplace_back();
01475 }
01476
01477
01478 void
01479 _M_default_append(size_type __n);
01480 #endif
01481
01482
01483
01484
01485
01486
01487
01488 template<typename _Integer>
01489 void
01490 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01491 { _M_fill_assign(__n, __val); }
01492
01493
01494 template<typename _InputIterator>
01495 void
01496 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01497 __false_type);
01498
01499
01500
01501 void
01502 _M_fill_assign(size_type __n, const value_type& __val);
01503
01504
01505
01506 void
01507 _M_transfer(iterator __position, iterator __first, iterator __last)
01508 { __position._M_node->_M_transfer(__first._M_node, __last._M_node); }
01509
01510
01511 #ifndef __GXX_EXPERIMENTAL_CXX0X__
01512 void
01513 _M_insert(iterator __position, const value_type& __x)
01514 {
01515 _Node* __tmp = _M_create_node(__x);
01516 __tmp->_M_hook(__position._M_node);
01517 }
01518 #else
01519 template<typename... _Args>
01520 void
01521 _M_insert(iterator __position, _Args&&... __args)
01522 {
01523 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
01524 __tmp->_M_hook(__position._M_node);
01525 }
01526 #endif
01527
01528
01529 void
01530 _M_erase(iterator __position)
01531 {
01532 __position._M_node->_M_unhook();
01533 _Node* __n = static_cast<_Node*>(__position._M_node);
01534 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01535 _M_get_Node_allocator().destroy(__n);
01536 #else
01537 _M_get_Tp_allocator().destroy(std::__addressof(__n->_M_data));
01538 #endif
01539 _M_put_node(__n);
01540 }
01541
01542
01543 void
01544 _M_check_equal_allocators(list& __x)
01545 {
01546 if (std::__alloc_neq<typename _Base::_Node_alloc_type>::
01547 _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()))
01548 __throw_runtime_error(__N("list::_M_check_equal_allocators"));
01549 }
01550 };
01551
01552
01553
01554
01555
01556
01557
01558
01559
01560
01561
01562 template<typename _Tp, typename _Alloc>
01563 inline bool
01564 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01565 {
01566 typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
01567 const_iterator __end1 = __x.end();
01568 const_iterator __end2 = __y.end();
01569
01570 const_iterator __i1 = __x.begin();
01571 const_iterator __i2 = __y.begin();
01572 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
01573 {
01574 ++__i1;
01575 ++__i2;
01576 }
01577 return __i1 == __end1 && __i2 == __end2;
01578 }
01579
01580
01581
01582
01583
01584
01585
01586
01587
01588
01589
01590
01591 template<typename _Tp, typename _Alloc>
01592 inline bool
01593 operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01594 { return std::lexicographical_compare(__x.begin(), __x.end(),
01595 __y.begin(), __y.end()); }
01596
01597
01598 template<typename _Tp, typename _Alloc>
01599 inline bool
01600 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01601 { return !(__x == __y); }
01602
01603
01604 template<typename _Tp, typename _Alloc>
01605 inline bool
01606 operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01607 { return __y < __x; }
01608
01609
01610 template<typename _Tp, typename _Alloc>
01611 inline bool
01612 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01613 { return !(__y < __x); }
01614
01615
01616 template<typename _Tp, typename _Alloc>
01617 inline bool
01618 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01619 { return !(__x < __y); }
01620
01621
01622 template<typename _Tp, typename _Alloc>
01623 inline void
01624 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
01625 { __x.swap(__y); }
01626
01627 _GLIBCXX_END_NAMESPACE_CONTAINER
01628 }
01629
01630 #endif