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 _MULTISET_H
00062 #define _MULTISET_H 1
00063
00064 #include <bits/concept_check.h>
00065
00066 namespace _GLIBCXX_STD
00067 {
00068
00069
00070 template <class _Key, class _Compare = less<_Key>,
00071 class _Alloc = allocator<_Key> >
00072 class multiset;
00073
00074 template <class _Key, class _Compare, class _Alloc>
00075 inline bool
00076 operator==(const multiset<_Key,_Compare,_Alloc>& __x,
00077 const multiset<_Key,_Compare,_Alloc>& __y);
00078
00079 template <class _Key, class _Compare, class _Alloc>
00080 inline bool
00081 operator<(const multiset<_Key,_Compare,_Alloc>& __x,
00082 const multiset<_Key,_Compare,_Alloc>& __y);
00083
00104 template <class _Key, class _Compare, class _Alloc>
00105 class multiset
00106 {
00107
00108 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
00109 __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
00110 _BinaryFunctionConcept)
00111
00112 public:
00113
00114 typedef _Key key_type;
00115 typedef _Key value_type;
00116 typedef _Compare key_compare;
00117 typedef _Compare value_compare;
00118
00119 private:
00121 typedef _Rb_tree<key_type, value_type,
00122 _Identity<value_type>, key_compare, _Alloc> _Rep_type;
00124 _Rep_type _M_t;
00125
00126 public:
00127 typedef typename _Alloc::pointer pointer;
00128 typedef typename _Alloc::const_pointer const_pointer;
00129 typedef typename _Alloc::reference reference;
00130 typedef typename _Alloc::const_reference const_reference;
00131
00132
00133
00134 typedef typename _Rep_type::const_iterator iterator;
00135 typedef typename _Rep_type::const_iterator const_iterator;
00136 typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
00137 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
00138 typedef typename _Rep_type::size_type size_type;
00139 typedef typename _Rep_type::difference_type difference_type;
00140 typedef typename _Rep_type::allocator_type allocator_type;
00141
00142
00143
00147 multiset()
00148 : _M_t(_Compare(), allocator_type()) { }
00149
00150 explicit
00151 multiset(const _Compare& __comp,
00152 const allocator_type& __a = allocator_type())
00153 : _M_t(__comp, __a) { }
00154
00164 template <class _InputIterator>
00165 multiset(_InputIterator __first, _InputIterator __last)
00166 : _M_t(_Compare(), allocator_type())
00167 { _M_t.insert_equal(__first, __last); }
00168
00180 template <class _InputIterator>
00181 multiset(_InputIterator __first, _InputIterator __last,
00182 const _Compare& __comp,
00183 const allocator_type& __a = allocator_type())
00184 : _M_t(__comp, __a)
00185 { _M_t.insert_equal(__first, __last); }
00186
00194 multiset(const multiset<_Key,_Compare,_Alloc>& __x)
00195 : _M_t(__x._M_t) { }
00196
00204 multiset<_Key,_Compare,_Alloc>&
00205 operator=(const multiset<_Key,_Compare,_Alloc>& __x)
00206 {
00207 _M_t = __x._M_t;
00208 return *this;
00209 }
00210
00211
00212
00214 key_compare
00215 key_comp() const
00216 { return _M_t.key_comp(); }
00218 value_compare
00219 value_comp() const
00220 { return _M_t.key_comp(); }
00222 allocator_type
00223 get_allocator() const
00224 { return _M_t.get_allocator(); }
00225
00231 iterator
00232 begin() const
00233 { return _M_t.begin(); }
00234
00240 iterator
00241 end() const
00242 { return _M_t.end(); }
00243
00249 reverse_iterator
00250 rbegin() const
00251 { return _M_t.rbegin(); }
00252
00258 reverse_iterator
00259 rend() const
00260 { return _M_t.rend(); }
00261
00263 bool
00264 empty() const
00265 { return _M_t.empty(); }
00266
00268 size_type
00269 size() const
00270 { return _M_t.size(); }
00271
00273 size_type
00274 max_size() const
00275 { return _M_t.max_size(); }
00276
00288 void
00289 swap(multiset<_Key,_Compare,_Alloc>& __x)
00290 { _M_t.swap(__x._M_t); }
00291
00292
00304 iterator
00305 insert(const value_type& __x)
00306 { return _M_t.insert_equal(__x); }
00307
00328 iterator
00329 insert(iterator __position, const value_type& __x)
00330 {
00331 typedef typename _Rep_type::iterator _Rep_iterator;
00332 return _M_t.insert_equal((_Rep_iterator&)__position, __x);
00333 }
00334
00343 template <class _InputIterator>
00344 void
00345 insert(_InputIterator __first, _InputIterator __last)
00346 { _M_t.insert_equal(__first, __last); }
00347
00358 void
00359 erase(iterator __position)
00360 {
00361 typedef typename _Rep_type::iterator _Rep_iterator;
00362 _M_t.erase((_Rep_iterator&)__position);
00363 }
00364
00376 size_type
00377 erase(const key_type& __x)
00378 { return _M_t.erase(__x); }
00379
00391 void
00392 erase(iterator __first, iterator __last)
00393 {
00394 typedef typename _Rep_type::iterator _Rep_iterator;
00395 _M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last);
00396 }
00397
00404 void
00405 clear()
00406 { _M_t.clear(); }
00407
00408
00409
00415 size_type
00416 count(const key_type& __x) const
00417 { return _M_t.count(__x); }
00418
00419
00420
00422
00433 iterator
00434 find(const key_type& __x)
00435 { return _M_t.find(__x); }
00436
00437 const_iterator
00438 find(const key_type& __x) const
00439 { return _M_t.find(__x); }
00441
00443
00454 iterator
00455 lower_bound(const key_type& __x)
00456 { return _M_t.lower_bound(__x); }
00457
00458 const_iterator
00459 lower_bound(const key_type& __x) const
00460 { return _M_t.lower_bound(__x); }
00462
00464
00470 iterator
00471 upper_bound(const key_type& __x)
00472 { return _M_t.upper_bound(__x); }
00473
00474 const_iterator
00475 upper_bound(const key_type& __x) const
00476 { return _M_t.upper_bound(__x); }
00478
00480
00495 pair<iterator,iterator>
00496 equal_range(const key_type& __x)
00497 { return _M_t.equal_range(__x); }
00498
00499 pair<const_iterator,const_iterator>
00500 equal_range(const key_type& __x) const
00501 { return _M_t.equal_range(__x); }
00502
00503 template <class _K1, class _C1, class _A1>
00504 friend bool
00505 operator== (const multiset<_K1,_C1,_A1>&,
00506 const multiset<_K1,_C1,_A1>&);
00507
00508 template <class _K1, class _C1, class _A1>
00509 friend bool
00510 operator< (const multiset<_K1,_C1,_A1>&,
00511 const multiset<_K1,_C1,_A1>&);
00512 };
00513
00525 template <class _Key, class _Compare, class _Alloc>
00526 inline bool
00527 operator==(const multiset<_Key,_Compare,_Alloc>& __x,
00528 const multiset<_Key,_Compare,_Alloc>& __y)
00529 { return __x._M_t == __y._M_t; }
00530
00542 template <class _Key, class _Compare, class _Alloc>
00543 inline bool
00544 operator<(const multiset<_Key,_Compare,_Alloc>& __x,
00545 const multiset<_Key,_Compare,_Alloc>& __y)
00546 { return __x._M_t < __y._M_t; }
00547
00549 template <class _Key, class _Compare, class _Alloc>
00550 inline bool
00551 operator!=(const multiset<_Key,_Compare,_Alloc>& __x,
00552 const multiset<_Key,_Compare,_Alloc>& __y)
00553 { return !(__x == __y); }
00554
00556 template <class _Key, class _Compare, class _Alloc>
00557 inline bool
00558 operator>(const multiset<_Key,_Compare,_Alloc>& __x,
00559 const multiset<_Key,_Compare,_Alloc>& __y)
00560 { return __y < __x; }
00561
00563 template <class _Key, class _Compare, class _Alloc>
00564 inline bool
00565 operator<=(const multiset<_Key,_Compare,_Alloc>& __x,
00566 const multiset<_Key,_Compare,_Alloc>& __y)
00567 { return !(__y < __x); }
00568
00570 template <class _Key, class _Compare, class _Alloc>
00571 inline bool
00572 operator>=(const multiset<_Key,_Compare,_Alloc>& __x,
00573 const multiset<_Key,_Compare,_Alloc>& __y)
00574 { return !(__x < __y); }
00575
00577 template <class _Key, class _Compare, class _Alloc>
00578 inline void
00579 swap(multiset<_Key,_Compare,_Alloc>& __x,
00580 multiset<_Key,_Compare,_Alloc>& __y)
00581 { __x.swap(__y); }
00582
00583 }
00584
00585 #endif