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