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 _SET_H
00062 #define _SET_H 1
00063
00064 #include <bits/concept_check.h>
00065
00066 namespace _GLIBCXX_STD
00067 {
00068
00069 template<class _Key, class _Compare = std::less<_Key>,
00070 class _Alloc = std::allocator<_Key> >
00071 class set;
00072
00073 template<class _Key, class _Compare, class _Alloc>
00074 inline bool
00075 operator==(const set<_Key, _Compare, _Alloc>& __x,
00076 const set<_Key, _Compare, _Alloc>& __y);
00077
00078 template<class _Key, class _Compare, class _Alloc>
00079 inline bool
00080 operator<(const set<_Key, _Compare, _Alloc>& __x,
00081 const set<_Key, _Compare, _Alloc>& __y);
00082
00106 template<class _Key, class _Compare, class _Alloc>
00107 class set
00108 {
00109
00110 typedef typename _Alloc::value_type _Alloc_value_type;
00111 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
00112 __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
00113 _BinaryFunctionConcept)
00114 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
00115
00116 public:
00117
00119
00120 typedef _Key key_type;
00121 typedef _Key value_type;
00122 typedef _Compare key_compare;
00123 typedef _Compare value_compare;
00124 typedef _Alloc allocator_type;
00126
00127 private:
00128 typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
00129
00130 typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
00131 key_compare, _Key_alloc_type> _Rep_type;
00132 _Rep_type _M_t;
00133
00134 public:
00136
00137 typedef typename _Key_alloc_type::pointer pointer;
00138 typedef typename _Key_alloc_type::const_pointer const_pointer;
00139 typedef typename _Key_alloc_type::reference reference;
00140 typedef typename _Key_alloc_type::const_reference const_reference;
00141
00142
00143
00144 typedef typename _Rep_type::const_iterator iterator;
00145 typedef typename _Rep_type::const_iterator const_iterator;
00146 typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
00147 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
00148 typedef typename _Rep_type::size_type size_type;
00149 typedef typename _Rep_type::difference_type difference_type;
00151
00152
00154 set()
00155 : _M_t(_Compare(), allocator_type()) {}
00156
00163 explicit
00164 set(const _Compare& __comp,
00165 const allocator_type& __a = allocator_type())
00166 : _M_t(__comp, __a) {}
00167
00177 template<class _InputIterator>
00178 set(_InputIterator __first, _InputIterator __last)
00179 : _M_t(_Compare(), allocator_type())
00180 { _M_t.insert_unique(__first, __last); }
00181
00193 template<class _InputIterator>
00194 set(_InputIterator __first, _InputIterator __last,
00195 const _Compare& __comp,
00196 const allocator_type& __a = allocator_type())
00197 : _M_t(__comp, __a)
00198 { _M_t.insert_unique(__first, __last); }
00199
00207 set(const set<_Key,_Compare,_Alloc>& __x)
00208 : _M_t(__x._M_t) { }
00209
00217 set<_Key,_Compare,_Alloc>&
00218 operator=(const set<_Key, _Compare, _Alloc>& __x)
00219 {
00220 _M_t = __x._M_t;
00221 return *this;
00222 }
00223
00224
00225
00227 key_compare
00228 key_comp() const
00229 { return _M_t.key_comp(); }
00231 value_compare
00232 value_comp() const
00233 { return _M_t.key_comp(); }
00235 allocator_type
00236 get_allocator() const
00237 { return _M_t.get_allocator(); }
00238
00243 iterator
00244 begin() const
00245 { return _M_t.begin(); }
00246
00251 iterator
00252 end() const
00253 { return _M_t.end(); }
00254
00260 reverse_iterator
00261 rbegin() const
00262 { return _M_t.rbegin(); }
00263
00269 reverse_iterator
00270 rend() const
00271 { return _M_t.rend(); }
00272
00274 bool
00275 empty() const
00276 { return _M_t.empty(); }
00277
00279 size_type
00280 size() const
00281 { return _M_t.size(); }
00282
00284 size_type
00285 max_size() const
00286 { return _M_t.max_size(); }
00287
00299 void
00300 swap(set<_Key,_Compare,_Alloc>& __x)
00301 { _M_t.swap(__x._M_t); }
00302
00303
00317 std::pair<iterator,bool>
00318 insert(const value_type& __x)
00319 {
00320 std::pair<typename _Rep_type::iterator, bool> __p =
00321 _M_t.insert_unique(__x);
00322 return std::pair<iterator, bool>(__p.first, __p.second);
00323 }
00324
00344 iterator
00345 insert(iterator __position, const value_type& __x)
00346 { return _M_t.insert_unique(__position, __x); }
00347
00356 template<class _InputIterator>
00357 void
00358 insert(_InputIterator __first, _InputIterator __last)
00359 { _M_t.insert_unique(__first, __last); }
00360
00370 void
00371 erase(iterator __position)
00372 { _M_t.erase(__position); }
00373
00385 size_type
00386 erase(const key_type& __x)
00387 { return _M_t.erase(__x); }
00388
00400 void
00401 erase(iterator __first, iterator __last)
00402 { _M_t.erase(__first, __last); }
00403
00410 void
00411 clear()
00412 { _M_t.clear(); }
00413
00414
00415
00424 size_type
00425 count(const key_type& __x) const
00426 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
00427
00428
00429
00431
00442 iterator
00443 find(const key_type& __x)
00444 { return _M_t.find(__x); }
00445
00446 const_iterator
00447 find(const key_type& __x) const
00448 { return _M_t.find(__x); }
00450
00452
00463 iterator
00464 lower_bound(const key_type& __x)
00465 { return _M_t.lower_bound(__x); }
00466
00467 const_iterator
00468 lower_bound(const key_type& __x) const
00469 { return _M_t.lower_bound(__x); }
00471
00473
00479 iterator
00480 upper_bound(const key_type& __x)
00481 { return _M_t.upper_bound(__x); }
00482
00483 const_iterator
00484 upper_bound(const key_type& __x) const
00485 { return _M_t.upper_bound(__x); }
00487
00489
00504 std::pair<iterator, iterator>
00505 equal_range(const key_type& __x)
00506 { return _M_t.equal_range(__x); }
00507
00508 std::pair<const_iterator, const_iterator>
00509 equal_range(const key_type& __x) const
00510 { return _M_t.equal_range(__x); }
00512
00513 template<class _K1, class _C1, class _A1>
00514 friend bool
00515 operator== (const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
00516
00517 template<class _K1, class _C1, class _A1>
00518 friend bool
00519 operator< (const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
00520 };
00521
00522
00533 template<class _Key, class _Compare, class _Alloc>
00534 inline bool
00535 operator==(const set<_Key, _Compare, _Alloc>& __x,
00536 const set<_Key, _Compare, _Alloc>& __y)
00537 { return __x._M_t == __y._M_t; }
00538
00550 template<class _Key, class _Compare, class _Alloc>
00551 inline bool
00552 operator<(const set<_Key, _Compare, _Alloc>& __x,
00553 const set<_Key, _Compare, _Alloc>& __y)
00554 { return __x._M_t < __y._M_t; }
00555
00557 template<class _Key, class _Compare, class _Alloc>
00558 inline bool
00559 operator!=(const set<_Key, _Compare, _Alloc>& __x,
00560 const set<_Key, _Compare, _Alloc>& __y)
00561 { return !(__x == __y); }
00562
00564 template<class _Key, class _Compare, class _Alloc>
00565 inline bool
00566 operator>(const set<_Key, _Compare, _Alloc>& __x,
00567 const set<_Key, _Compare, _Alloc>& __y)
00568 { return __y < __x; }
00569
00571 template<class _Key, class _Compare, class _Alloc>
00572 inline bool
00573 operator<=(const set<_Key, _Compare, _Alloc>& __x,
00574 const set<_Key, _Compare, _Alloc>& __y)
00575 { return !(__y < __x); }
00576
00578 template<class _Key, class _Compare, class _Alloc>
00579 inline bool
00580 operator>=(const set<_Key, _Compare, _Alloc>& __x,
00581 const set<_Key, _Compare, _Alloc>& __y)
00582 { return !(__x < __y); }
00583
00585 template<class _Key, class _Compare, class _Alloc>
00586 inline void
00587 swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>& __y)
00588 { __x.swap(__y); }
00589
00590 }
00591
00592 #endif