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
00061 #ifndef _LIST_H
00062 #define _LIST_H 1
00063
00064 #include <bits/concept_check.h>
00065
00066 namespace _GLIBCXX_STD
00067 {
00068
00069
00070
00071
00072
00074 struct _List_node_base
00075 {
00076 _List_node_base* _M_next;
00077 _List_node_base* _M_prev;
00078
00079 static void
00080 swap(_List_node_base& __x, _List_node_base& __y);
00081
00082 void
00083 transfer(_List_node_base * const __first,
00084 _List_node_base * const __last);
00085
00086 void
00087 reverse();
00088
00089 void
00090 hook(_List_node_base * const __position);
00091
00092 void
00093 unhook();
00094 };
00095
00097 template<typename _Tp>
00098 struct _List_node : public _List_node_base
00099 {
00100 _Tp _M_data;
00101 };
00102
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 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 _List_iterator(_List_node_base* __x)
00126 : _M_node(__x) { }
00127
00128
00129 reference
00130 operator*() const
00131 { return static_cast<_Node*>(_M_node)->_M_data; }
00132
00133 pointer
00134 operator->() const
00135 { return &static_cast<_Node*>(_M_node)->_M_data; }
00136
00137 _Self&
00138 operator++()
00139 {
00140 _M_node = _M_node->_M_next;
00141 return *this;
00142 }
00143
00144 _Self
00145 operator++(int)
00146 {
00147 _Self __tmp = *this;
00148 _M_node = _M_node->_M_next;
00149 return __tmp;
00150 }
00151
00152 _Self&
00153 operator--()
00154 {
00155 _M_node = _M_node->_M_prev;
00156 return *this;
00157 }
00158
00159 _Self
00160 operator--(int)
00161 {
00162 _Self __tmp = *this;
00163 _M_node = _M_node->_M_prev;
00164 return __tmp;
00165 }
00166
00167 bool
00168 operator==(const _Self& __x) const
00169 { return _M_node == __x._M_node; }
00170
00171 bool
00172 operator!=(const _Self& __x) const
00173 { return _M_node != __x._M_node; }
00174
00175
00176 _List_node_base* _M_node;
00177 };
00178
00186 template<typename _Tp>
00187 struct _List_const_iterator
00188 {
00189 typedef _List_const_iterator<_Tp> _Self;
00190 typedef const _List_node<_Tp> _Node;
00191 typedef _List_iterator<_Tp> iterator;
00192
00193 typedef ptrdiff_t difference_type;
00194 typedef bidirectional_iterator_tag iterator_category;
00195 typedef _Tp value_type;
00196 typedef const _Tp* pointer;
00197 typedef const _Tp& reference;
00198
00199 _List_const_iterator()
00200 : _M_node() { }
00201
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
00278 template<typename _Tp, typename _Alloc>
00279 class _List_base
00280 {
00281 protected:
00282
00283
00284
00285
00286
00287
00288
00289
00290
00291
00292
00293
00294
00295 typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
00296
00297 _Node_Alloc_type;
00298
00299 struct _List_impl
00300 : public _Node_Alloc_type {
00301 _List_node_base _M_node;
00302 _List_impl (const _Node_Alloc_type& __a)
00303 : _Node_Alloc_type(__a)
00304 { }
00305 };
00306
00307 _List_impl _M_impl;
00308
00309 _List_node<_Tp>*
00310 _M_get_node()
00311 { return _M_impl._Node_Alloc_type::allocate(1); }
00312
00313 void
00314 _M_put_node(_List_node<_Tp>* __p)
00315 { _M_impl._Node_Alloc_type::deallocate(__p, 1); }
00316
00317 public:
00318 typedef _Alloc allocator_type;
00319
00320 allocator_type
00321 get_allocator() const
00322 { return allocator_type(*static_cast<const _Node_Alloc_type*>(&this->_M_impl)); }
00323
00324 _List_base(const allocator_type& __a)
00325 : _M_impl(__a)
00326 { _M_init(); }
00327
00328
00329 ~_List_base()
00330 { _M_clear(); }
00331
00332 void
00333 _M_clear();
00334
00335 void
00336 _M_init()
00337 {
00338 this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
00339 this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
00340 }
00341 };
00342
00388 template<typename _Tp, typename _Alloc = allocator<_Tp> >
00389 class list : protected _List_base<_Tp, _Alloc>
00390 {
00391
00392 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00393
00394 typedef _List_base<_Tp, _Alloc> _Base;
00395
00396 public:
00397 typedef _Tp value_type;
00398 typedef typename _Alloc::pointer pointer;
00399 typedef typename _Alloc::const_pointer const_pointer;
00400 typedef typename _Alloc::reference reference;
00401 typedef typename _Alloc::const_reference const_reference;
00402 typedef _List_iterator<_Tp> iterator;
00403 typedef _List_const_iterator<_Tp> const_iterator;
00404 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00405 typedef std::reverse_iterator<iterator> reverse_iterator;
00406 typedef size_t size_type;
00407 typedef ptrdiff_t difference_type;
00408 typedef typename _Base::allocator_type allocator_type;
00409
00410 protected:
00411
00412
00413 typedef _List_node<_Tp> _Node;
00414
00421 using _Base::_M_impl;
00422 using _Base::_M_put_node;
00423 using _Base::_M_get_node;
00424
00432 _Node*
00433 _M_create_node(const value_type& __x)
00434 {
00435 _Node* __p = this->_M_get_node();
00436 try
00437 {
00438 std::_Construct(&__p->_M_data, __x);
00439 }
00440 catch(...)
00441 {
00442 _M_put_node(__p);
00443 __throw_exception_again;
00444 }
00445 return __p;
00446 }
00447
00454 _Node*
00455 _M_create_node()
00456 {
00457 _Node* __p = this->_M_get_node();
00458 try
00459 {
00460 std::_Construct(&__p->_M_data);
00461 }
00462 catch(...)
00463 {
00464 _M_put_node(__p);
00465 __throw_exception_again;
00466 }
00467 return __p;
00468 }
00469
00470 public:
00471
00472
00476 explicit
00477 list(const allocator_type& __a = allocator_type())
00478 : _Base(__a) { }
00479
00487 list(size_type __n, const value_type& __value,
00488 const allocator_type& __a = allocator_type())
00489 : _Base(__a)
00490 { this->insert(begin(), __n, __value); }
00491
00499 explicit
00500 list(size_type __n)
00501 : _Base(allocator_type())
00502 { this->insert(begin(), __n, value_type()); }
00503
00511 list(const list& __x)
00512 : _Base(__x.get_allocator())
00513 { this->insert(begin(), __x.begin(), __x.end()); }
00514
00529 template<typename _InputIterator>
00530 list(_InputIterator __first, _InputIterator __last,
00531 const allocator_type& __a = allocator_type())
00532 : _Base(__a)
00533 { this->insert(begin(), __first, __last); }
00534
00550 list&
00551 operator=(const list& __x);
00552
00563 void
00564 assign(size_type __n, const value_type& __val)
00565 { _M_fill_assign(__n, __val); }
00566
00579 template<typename _InputIterator>
00580 void
00581 assign(_InputIterator __first, _InputIterator __last)
00582 {
00583
00584 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00585 _M_assign_dispatch(__first, __last, _Integral());
00586 }
00587
00589 allocator_type
00590 get_allocator() const
00591 { return _Base::get_allocator(); }
00592
00593
00598 iterator
00599 begin()
00600 { return this->_M_impl._M_node._M_next; }
00601
00607 const_iterator
00608 begin() const
00609 { return this->_M_impl._M_node._M_next; }
00610
00616 iterator
00617 end() { return &this->_M_impl._M_node; }
00618
00624 const_iterator
00625 end() const
00626 { return &this->_M_impl._M_node; }
00627
00633 reverse_iterator
00634 rbegin()
00635 { return reverse_iterator(end()); }
00636
00642 const_reverse_iterator
00643 rbegin() const
00644 { return const_reverse_iterator(end()); }
00645
00651 reverse_iterator
00652 rend()
00653 { return reverse_iterator(begin()); }
00654
00660 const_reverse_iterator
00661 rend() const
00662 { return const_reverse_iterator(begin()); }
00663
00664
00669 bool
00670 empty() const
00671 { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
00672
00674 size_type
00675 size() const
00676 { return std::distance(begin(), end()); }
00677
00679 size_type
00680 max_size() const
00681 { return size_type(-1); }
00682
00693 void
00694 resize(size_type __new_size, const value_type& __x);
00695
00705 void
00706 resize(size_type __new_size)
00707 { this->resize(__new_size, value_type()); }
00708
00709
00714 reference
00715 front()
00716 { return *begin(); }
00717
00722 const_reference
00723 front() const
00724 { return *begin(); }
00725
00730 reference
00731 back()
00732 { return *(--end()); }
00733
00738 const_reference
00739 back() const
00740 { return *(--end()); }
00741
00742
00753 void
00754 push_front(const value_type& __x)
00755 { this->_M_insert(begin(), __x); }
00756
00769 void
00770 pop_front()
00771 { this->_M_erase(begin()); }
00772
00783 void
00784 push_back(const value_type& __x)
00785 { this->_M_insert(end(), __x); }
00786
00798 void
00799 pop_back()
00800 { this->_M_erase(this->_M_impl._M_node._M_prev); }
00801
00813 iterator
00814 insert(iterator __position, const value_type& __x);
00815
00829 void
00830 insert(iterator __position, size_type __n, const value_type& __x)
00831 { _M_fill_insert(__position, __n, __x); }
00832
00847 template<typename _InputIterator>
00848 void
00849 insert(iterator __position, _InputIterator __first,
00850 _InputIterator __last)
00851 {
00852
00853 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00854 _M_insert_dispatch(__position, __first, __last, _Integral());
00855 }
00856
00872 iterator
00873 erase(iterator __position);
00874
00894 iterator
00895 erase(iterator __first, iterator __last)
00896 {
00897 while (__first != __last)
00898 __first = erase(__first);
00899 return __last;
00900 }
00901
00911 void
00912 swap(list& __x)
00913 { _List_node_base::swap(this->_M_impl._M_node,__x._M_impl._M_node); }
00914
00921 void
00922 clear()
00923 {
00924 _Base::_M_clear();
00925 _Base::_M_init();
00926 }
00927
00928
00938 void
00939 splice(iterator __position, list& __x)
00940 {
00941 if (!__x.empty())
00942 this->_M_transfer(__position, __x.begin(), __x.end());
00943 }
00944
00954 void
00955 splice(iterator __position, list&, iterator __i)
00956 {
00957 iterator __j = __i;
00958 ++__j;
00959 if (__position == __i || __position == __j)
00960 return;
00961 this->_M_transfer(__position, __i, __j);
00962 }
00963
00976 void
00977 splice(iterator __position, list&, iterator __first, iterator __last)
00978 {
00979 if (__first != __last)
00980 this->_M_transfer(__position, __first, __last);
00981 }
00982
00994 void
00995 remove(const _Tp& __value);
00996
01008 template<typename _Predicate>
01009 void
01010 remove_if(_Predicate);
01011
01022 void
01023 unique();
01024
01037 template<typename _BinaryPredicate>
01038 void
01039 unique(_BinaryPredicate);
01040
01050 void
01051 merge(list& __x);
01052
01065 template<typename _StrictWeakOrdering>
01066 void
01067 merge(list&, _StrictWeakOrdering);
01068
01074 void
01075 reverse()
01076 { this->_M_impl._M_node.reverse(); }
01077
01084 void
01085 sort();
01086
01093 template<typename _StrictWeakOrdering>
01094 void
01095 sort(_StrictWeakOrdering);
01096
01097 protected:
01098
01099
01100
01101 template<typename _Integer>
01102 void
01103 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01104 {
01105 _M_fill_assign(static_cast<size_type>(__n),
01106 static_cast<value_type>(__val));
01107 }
01108
01109
01110 template<typename _InputIterator>
01111 void
01112 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01113 __false_type);
01114
01115
01116
01117 void
01118 _M_fill_assign(size_type __n, const value_type& __val);
01119
01120
01121
01122
01123
01124 template<typename _Integer>
01125 void
01126 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
01127 __true_type)
01128 {
01129 _M_fill_insert(__pos, static_cast<size_type>(__n),
01130 static_cast<value_type>(__x));
01131 }
01132
01133
01134 template<typename _InputIterator>
01135 void
01136 _M_insert_dispatch(iterator __pos,
01137 _InputIterator __first, _InputIterator __last,
01138 __false_type)
01139 {
01140 for ( ; __first != __last; ++__first)
01141 _M_insert(__pos, *__first);
01142 }
01143
01144
01145
01146 void
01147 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
01148 {
01149 for ( ; __n > 0; --__n)
01150 _M_insert(__pos, __x);
01151 }
01152
01153
01154
01155 void
01156 _M_transfer(iterator __position, iterator __first, iterator __last)
01157 { __position._M_node->transfer(__first._M_node,__last._M_node); }
01158
01159
01160 void
01161 _M_insert(iterator __position, const value_type& __x)
01162 {
01163 _Node* __tmp = _M_create_node(__x);
01164 __tmp->hook(__position._M_node);
01165 }
01166
01167
01168 void
01169 _M_erase(iterator __position)
01170 {
01171 __position._M_node->unhook();
01172 _Node* __n = static_cast<_Node*>(__position._M_node);
01173 std::_Destroy(&__n->_M_data);
01174 _M_put_node(__n);
01175 }
01176 };
01177
01188 template<typename _Tp, typename _Alloc>
01189 inline bool
01190 operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
01191 {
01192 typedef typename list<_Tp,_Alloc>::const_iterator const_iterator;
01193 const_iterator __end1 = __x.end();
01194 const_iterator __end2 = __y.end();
01195
01196 const_iterator __i1 = __x.begin();
01197 const_iterator __i2 = __y.begin();
01198 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
01199 {
01200 ++__i1;
01201 ++__i2;
01202 }
01203 return __i1 == __end1 && __i2 == __end2;
01204 }
01205
01217 template<typename _Tp, typename _Alloc>
01218 inline bool
01219 operator<(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
01220 { return std::lexicographical_compare(__x.begin(), __x.end(),
01221 __y.begin(), __y.end()); }
01222
01224 template<typename _Tp, typename _Alloc>
01225 inline bool
01226 operator!=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
01227 { return !(__x == __y); }
01228
01230 template<typename _Tp, typename _Alloc>
01231 inline bool
01232 operator>(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
01233 { return __y < __x; }
01234
01236 template<typename _Tp, typename _Alloc>
01237 inline bool
01238 operator<=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
01239 { return !(__y < __x); }
01240
01242 template<typename _Tp, typename _Alloc>
01243 inline bool
01244 operator>=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
01245 { return !(__x < __y); }
01246
01248 template<typename _Tp, typename _Alloc>
01249 inline void
01250 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
01251 { __x.swap(__y); }
01252 }
01253
01254 #endif
01255