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 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
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
00280 template<typename _Tp, typename _Alloc>
00281 class _List_base
00282 {
00283 protected:
00284
00285
00286
00287
00288
00289
00290
00291
00292
00293
00294
00295
00296
00297 typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
00298 _Node_alloc_type;
00299
00300 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
00301
00302 struct _List_impl
00303 : public _Node_alloc_type
00304 {
00305 _List_node_base _M_node;
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 _Tp_alloc_type
00326 _M_get_Tp_allocator() const
00327 { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
00328
00329 allocator_type
00330 get_allocator() const
00331 { return _M_get_Tp_allocator(); }
00332
00333 _List_base(const allocator_type& __a)
00334 : _M_impl(__a)
00335 { _M_init(); }
00336
00337
00338 ~_List_base()
00339 { _M_clear(); }
00340
00341 void
00342 _M_clear();
00343
00344 void
00345 _M_init()
00346 {
00347 this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
00348 this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
00349 }
00350 };
00351
00397 template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
00398 class list : protected _List_base<_Tp, _Alloc>
00399 {
00400
00401 typedef typename _Alloc::value_type _Alloc_value_type;
00402 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00403 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
00404
00405 typedef _List_base<_Tp, _Alloc> _Base;
00406 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
00407
00408 public:
00409 typedef _Tp value_type;
00410 typedef typename _Tp_alloc_type::pointer pointer;
00411 typedef typename _Tp_alloc_type::const_pointer const_pointer;
00412 typedef typename _Tp_alloc_type::reference reference;
00413 typedef typename _Tp_alloc_type::const_reference const_reference;
00414 typedef _List_iterator<_Tp> iterator;
00415 typedef _List_const_iterator<_Tp> const_iterator;
00416 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00417 typedef std::reverse_iterator<iterator> reverse_iterator;
00418 typedef size_t size_type;
00419 typedef ptrdiff_t difference_type;
00420 typedef _Alloc allocator_type;
00421
00422 protected:
00423
00424
00425 typedef _List_node<_Tp> _Node;
00426
00433 using _Base::_M_impl;
00434 using _Base::_M_put_node;
00435 using _Base::_M_get_node;
00436 using _Base::_M_get_Tp_allocator;
00437
00445 _Node*
00446 _M_create_node(const value_type& __x)
00447 {
00448 _Node* __p = this->_M_get_node();
00449 try
00450 {
00451 _M_get_Tp_allocator().construct(&__p->_M_data, __x);
00452 }
00453 catch(...)
00454 {
00455 _M_put_node(__p);
00456 __throw_exception_again;
00457 }
00458 return __p;
00459 }
00460
00461 public:
00462
00463
00467 explicit
00468 list(const allocator_type& __a = allocator_type())
00469 : _Base(__a) { }
00470
00478 explicit
00479 list(size_type __n, const value_type& __value = value_type(),
00480 const allocator_type& __a = allocator_type())
00481 : _Base(__a)
00482 { this->insert(begin(), __n, __value); }
00483
00491 list(const list& __x)
00492 : _Base(__x.get_allocator())
00493 { this->insert(begin(), __x.begin(), __x.end()); }
00494
00509 template<typename _InputIterator>
00510 list(_InputIterator __first, _InputIterator __last,
00511 const allocator_type& __a = allocator_type())
00512 : _Base(__a)
00513 { this->insert(begin(), __first, __last); }
00514
00530 list&
00531 operator=(const list& __x);
00532
00543 void
00544 assign(size_type __n, const value_type& __val)
00545 { _M_fill_assign(__n, __val); }
00546
00559 template<typename _InputIterator>
00560 void
00561 assign(_InputIterator __first, _InputIterator __last)
00562 {
00563
00564 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00565 _M_assign_dispatch(__first, __last, _Integral());
00566 }
00567
00569 allocator_type
00570 get_allocator() const
00571 { return _Base::get_allocator(); }
00572
00573
00578 iterator
00579 begin()
00580 { return iterator(this->_M_impl._M_node._M_next); }
00581
00587 const_iterator
00588 begin() const
00589 { return const_iterator(this->_M_impl._M_node._M_next); }
00590
00596 iterator
00597 end()
00598 { return iterator(&this->_M_impl._M_node); }
00599
00605 const_iterator
00606 end() const
00607 { return const_iterator(&this->_M_impl._M_node); }
00608
00614 reverse_iterator
00615 rbegin()
00616 { return reverse_iterator(end()); }
00617
00623 const_reverse_iterator
00624 rbegin() const
00625 { return const_reverse_iterator(end()); }
00626
00632 reverse_iterator
00633 rend()
00634 { return reverse_iterator(begin()); }
00635
00641 const_reverse_iterator
00642 rend() const
00643 { return const_reverse_iterator(begin()); }
00644
00645
00650 bool
00651 empty() const
00652 { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
00653
00655 size_type
00656 size() const
00657 { return std::distance(begin(), end()); }
00658
00660 size_type
00661 max_size() const
00662 { return size_type(-1); }
00663
00674 void
00675 resize(size_type __new_size, value_type __x = value_type());
00676
00677
00682 reference
00683 front()
00684 { return *begin(); }
00685
00690 const_reference
00691 front() const
00692 { return *begin(); }
00693
00698 reference
00699 back()
00700 {
00701 iterator __tmp = end();
00702 --__tmp;
00703 return *__tmp;
00704 }
00705
00710 const_reference
00711 back() const
00712 {
00713 const_iterator __tmp = end();
00714 --__tmp;
00715 return *__tmp;
00716 }
00717
00718
00729 void
00730 push_front(const value_type& __x)
00731 { this->_M_insert(begin(), __x); }
00732
00745 void
00746 pop_front()
00747 { this->_M_erase(begin()); }
00748
00759 void
00760 push_back(const value_type& __x)
00761 { this->_M_insert(end(), __x); }
00762
00774 void
00775 pop_back()
00776 { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); }
00777
00789 iterator
00790 insert(iterator __position, const value_type& __x);
00791
00805 void
00806 insert(iterator __position, size_type __n, const value_type& __x)
00807 { _M_fill_insert(__position, __n, __x); }
00808
00823 template<typename _InputIterator>
00824 void
00825 insert(iterator __position, _InputIterator __first,
00826 _InputIterator __last)
00827 {
00828
00829 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00830 _M_insert_dispatch(__position, __first, __last, _Integral());
00831 }
00832
00848 iterator
00849 erase(iterator __position);
00850
00870 iterator
00871 erase(iterator __first, iterator __last)
00872 {
00873 while (__first != __last)
00874 __first = erase(__first);
00875 return __last;
00876 }
00877
00887 void
00888 swap(list& __x)
00889 { _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node); }
00890
00897 void
00898 clear()
00899 {
00900 _Base::_M_clear();
00901 _Base::_M_init();
00902 }
00903
00904
00914 void
00915 splice(iterator __position, list& __x)
00916 {
00917 if (!__x.empty())
00918 this->_M_transfer(__position, __x.begin(), __x.end());
00919 }
00920
00930 void
00931 splice(iterator __position, list&, iterator __i)
00932 {
00933 iterator __j = __i;
00934 ++__j;
00935 if (__position == __i || __position == __j)
00936 return;
00937 this->_M_transfer(__position, __i, __j);
00938 }
00939
00952 void
00953 splice(iterator __position, list&, iterator __first, iterator __last)
00954 {
00955 if (__first != __last)
00956 this->_M_transfer(__position, __first, __last);
00957 }
00958
00970 void
00971 remove(const _Tp& __value);
00972
00984 template<typename _Predicate>
00985 void
00986 remove_if(_Predicate);
00987
00998 void
00999 unique();
01000
01013 template<typename _BinaryPredicate>
01014 void
01015 unique(_BinaryPredicate);
01016
01026 void
01027 merge(list& __x);
01028
01041 template<typename _StrictWeakOrdering>
01042 void
01043 merge(list&, _StrictWeakOrdering);
01044
01050 void
01051 reverse()
01052 { this->_M_impl._M_node.reverse(); }
01053
01060 void
01061 sort();
01062
01069 template<typename _StrictWeakOrdering>
01070 void
01071 sort(_StrictWeakOrdering);
01072
01073 protected:
01074
01075
01076
01077 template<typename _Integer>
01078 void
01079 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01080 {
01081 _M_fill_assign(static_cast<size_type>(__n),
01082 static_cast<value_type>(__val));
01083 }
01084
01085
01086 template<typename _InputIterator>
01087 void
01088 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01089 __false_type);
01090
01091
01092
01093 void
01094 _M_fill_assign(size_type __n, const value_type& __val);
01095
01096
01097
01098
01099
01100 template<typename _Integer>
01101 void
01102 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
01103 __true_type)
01104 {
01105 _M_fill_insert(__pos, static_cast<size_type>(__n),
01106 static_cast<value_type>(__x));
01107 }
01108
01109
01110 template<typename _InputIterator>
01111 void
01112 _M_insert_dispatch(iterator __pos,
01113 _InputIterator __first, _InputIterator __last,
01114 __false_type)
01115 {
01116 for (; __first != __last; ++__first)
01117 _M_insert(__pos, *__first);
01118 }
01119
01120
01121
01122 void
01123 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
01124 {
01125 for (; __n > 0; --__n)
01126 _M_insert(__pos, __x);
01127 }
01128
01129
01130
01131 void
01132 _M_transfer(iterator __position, iterator __first, iterator __last)
01133 { __position._M_node->transfer(__first._M_node, __last._M_node); }
01134
01135
01136 void
01137 _M_insert(iterator __position, const value_type& __x)
01138 {
01139 _Node* __tmp = _M_create_node(__x);
01140 __tmp->hook(__position._M_node);
01141 }
01142
01143
01144 void
01145 _M_erase(iterator __position)
01146 {
01147 __position._M_node->unhook();
01148 _Node* __n = static_cast<_Node*>(__position._M_node);
01149 _M_get_Tp_allocator().destroy(&__n->_M_data);
01150 _M_put_node(__n);
01151 }
01152 };
01153
01164 template<typename _Tp, typename _Alloc>
01165 inline bool
01166 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01167 {
01168 typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
01169 const_iterator __end1 = __x.end();
01170 const_iterator __end2 = __y.end();
01171
01172 const_iterator __i1 = __x.begin();
01173 const_iterator __i2 = __y.begin();
01174 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
01175 {
01176 ++__i1;
01177 ++__i2;
01178 }
01179 return __i1 == __end1 && __i2 == __end2;
01180 }
01181
01193 template<typename _Tp, typename _Alloc>
01194 inline bool
01195 operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01196 { return std::lexicographical_compare(__x.begin(), __x.end(),
01197 __y.begin(), __y.end()); }
01198
01200 template<typename _Tp, typename _Alloc>
01201 inline bool
01202 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01203 { return !(__x == __y); }
01204
01206 template<typename _Tp, typename _Alloc>
01207 inline bool
01208 operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01209 { return __y < __x; }
01210
01212 template<typename _Tp, typename _Alloc>
01213 inline bool
01214 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01215 { return !(__y < __x); }
01216
01218 template<typename _Tp, typename _Alloc>
01219 inline bool
01220 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01221 { return !(__x < __y); }
01222
01224 template<typename _Tp, typename _Alloc>
01225 inline void
01226 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
01227 { __x.swap(__y); }
01228 }
01229
01230 #endif
01231