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 = less<_Key>,
00070 class _Alloc = 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 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
00111 __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
00112 _BinaryFunctionConcept)
00113
00114 public:
00115
00117
00118 typedef _Key key_type;
00119 typedef _Key value_type;
00120 typedef _Compare key_compare;
00121 typedef _Compare value_compare;
00123
00124 private:
00125 typedef _Rb_tree<key_type, value_type,
00126 _Identity<value_type>, key_compare, _Alloc> _Rep_type;
00127 _Rep_type _M_t;
00128 public:
00130
00131 typedef typename _Alloc::pointer pointer;
00132 typedef typename _Alloc::const_pointer const_pointer;
00133 typedef typename _Alloc::reference reference;
00134 typedef typename _Alloc::const_reference const_reference;
00135
00136
00137
00138 typedef typename _Rep_type::const_iterator iterator;
00139 typedef typename _Rep_type::const_iterator const_iterator;
00140 typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
00141 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
00142 typedef typename _Rep_type::size_type size_type;
00143 typedef typename _Rep_type::difference_type difference_type;
00144 typedef typename _Rep_type::allocator_type allocator_type;
00146
00147
00149 set()
00150 : _M_t(_Compare(), allocator_type()) {}
00151
00158 explicit set(const _Compare& __comp,
00159 const allocator_type& __a = allocator_type())
00160 : _M_t(__comp, __a) {}
00161
00171 template<class _InputIterator>
00172 set(_InputIterator __first, _InputIterator __last)
00173 : _M_t(_Compare(), allocator_type())
00174 { _M_t.insert_unique(__first, __last); }
00175
00187 template<class _InputIterator>
00188 set(_InputIterator __first, _InputIterator __last,
00189 const _Compare& __comp,
00190 const allocator_type& __a = allocator_type())
00191 : _M_t(__comp, __a)
00192 { _M_t.insert_unique(__first, __last); }
00193
00201 set(const set<_Key,_Compare,_Alloc>& __x)
00202 : _M_t(__x._M_t) { }
00203
00211 set<_Key,_Compare,_Alloc>&
00212 operator=(const set<_Key, _Compare, _Alloc>& __x)
00213 {
00214 _M_t = __x._M_t;
00215 return *this;
00216 }
00217
00218
00219
00221 key_compare
00222 key_comp() const
00223 { return _M_t.key_comp(); }
00225 value_compare
00226 value_comp() const
00227 { return _M_t.key_comp(); }
00229 allocator_type
00230 get_allocator() const
00231 { return _M_t.get_allocator(); }
00232
00237 iterator
00238 begin() const
00239 { return _M_t.begin(); }
00240
00245 iterator
00246 end() const
00247 { return _M_t.end(); }
00248
00254 reverse_iterator
00255 rbegin() const
00256 { return _M_t.rbegin(); }
00257
00263 reverse_iterator
00264 rend() const
00265 { return _M_t.rend(); }
00266
00268 bool
00269 empty() const
00270 { return _M_t.empty(); }
00271
00273 size_type
00274 size() const
00275 { return _M_t.size(); }
00276
00278 size_type
00279 max_size() const
00280 { return _M_t.max_size(); }
00281
00293 void
00294 swap(set<_Key,_Compare,_Alloc>& __x)
00295 { _M_t.swap(__x._M_t); }
00296
00297
00311 pair<iterator,bool>
00312 insert(const value_type& __x)
00313 {
00314 pair<typename _Rep_type::iterator, bool> __p = _M_t.insert_unique(__x);
00315 return pair<iterator, bool>(__p.first, __p.second);
00316 }
00317
00337 iterator
00338 insert(iterator __position, const value_type& __x)
00339 {
00340 typedef typename _Rep_type::iterator _Rep_iterator;
00341 return _M_t.insert_unique((_Rep_iterator&)__position, __x);
00342 }
00343
00352 template<class _InputIterator>
00353 void
00354 insert(_InputIterator __first, _InputIterator __last)
00355 { _M_t.insert_unique(__first, __last); }
00356
00366 void
00367 erase(iterator __position)
00368 {
00369 typedef typename _Rep_type::iterator _Rep_iterator;
00370 _M_t.erase((_Rep_iterator&)__position);
00371 }
00372
00384 size_type
00385 erase(const key_type& __x) { return _M_t.erase(__x); }
00386
00398 void
00399 erase(iterator __first, iterator __last)
00400 {
00401 typedef typename _Rep_type::iterator _Rep_iterator;
00402 _M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last);
00403 }
00404
00411 void
00412 clear()
00413 { _M_t.clear(); }
00414
00415
00416
00425 size_type
00426 count(const key_type& __x) const
00427 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
00428
00429
00430
00432
00443 iterator
00444 find(const key_type& __x)
00445 { return _M_t.find(__x); }
00446
00447 const_iterator
00448 find(const key_type& __x) const
00449 { return _M_t.find(__x); }
00451
00453
00464 iterator
00465 lower_bound(const key_type& __x)
00466 { return _M_t.lower_bound(__x); }
00467
00468 const_iterator
00469 lower_bound(const key_type& __x) const
00470 { return _M_t.lower_bound(__x); }
00472
00474
00480 iterator
00481 upper_bound(const key_type& __x)
00482 { return _M_t.upper_bound(__x); }
00483
00484 const_iterator
00485 upper_bound(const key_type& __x) const
00486 { return _M_t.upper_bound(__x); }
00488
00490
00505 pair<iterator,iterator>
00506 equal_range(const key_type& __x)
00507 { return _M_t.equal_range(__x); }
00508
00509 pair<const_iterator,const_iterator>
00510 equal_range(const key_type& __x) const
00511 { return _M_t.equal_range(__x); }
00513
00514 template<class _K1, class _C1, class _A1>
00515 friend bool
00516 operator== (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&);
00517
00518 template<class _K1, class _C1, class _A1>
00519 friend bool
00520 operator< (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&);
00521 };
00522
00523
00534 template<class _Key, class _Compare, class _Alloc>
00535 inline bool
00536 operator==(const set<_Key,_Compare,_Alloc>& __x,
00537 const set<_Key,_Compare,_Alloc>& __y)
00538 { return __x._M_t == __y._M_t; }
00539
00551 template<class _Key, class _Compare, class _Alloc>
00552 inline bool
00553 operator<(const set<_Key,_Compare,_Alloc>& __x,
00554 const set<_Key,_Compare,_Alloc>& __y)
00555 { return __x._M_t < __y._M_t; }
00556
00558 template<class _Key, class _Compare, class _Alloc>
00559 inline bool
00560 operator!=(const set<_Key,_Compare,_Alloc>& __x,
00561 const set<_Key,_Compare,_Alloc>& __y)
00562 { return !(__x == __y); }
00563
00565 template<class _Key, class _Compare, class _Alloc>
00566 inline bool
00567 operator>(const set<_Key,_Compare,_Alloc>& __x,
00568 const set<_Key,_Compare,_Alloc>& __y)
00569 { return __y < __x; }
00570
00572 template<class _Key, class _Compare, class _Alloc>
00573 inline bool
00574 operator<=(const set<_Key,_Compare,_Alloc>& __x,
00575 const set<_Key,_Compare,_Alloc>& __y)
00576 { return !(__y < __x); }
00577
00579 template<class _Key, class _Compare, class _Alloc>
00580 inline bool
00581 operator>=(const set<_Key,_Compare,_Alloc>& __x,
00582 const set<_Key,_Compare,_Alloc>& __y)
00583 { return !(__x < __y); }
00584
00586 template<class _Key, class _Compare, class _Alloc>
00587 inline void
00588 swap(set<_Key,_Compare,_Alloc>& __x, set<_Key,_Compare,_Alloc>& __y)
00589 { __x.swap(__y); }
00590
00591 }
00592
00593 #endif