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