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 = std::less<_Key>,
00071 class _Alloc = std::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 typedef typename _Alloc::value_type _Alloc_value_type;
00109 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
00110 __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
00111 _BinaryFunctionConcept)
00112 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
00113
00114 public:
00115
00116 typedef _Key key_type;
00117 typedef _Key value_type;
00118 typedef _Compare key_compare;
00119 typedef _Compare value_compare;
00120 typedef _Alloc allocator_type;
00121
00122 private:
00124 typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
00125
00126 typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
00127 key_compare, _Key_alloc_type> _Rep_type;
00129 _Rep_type _M_t;
00130
00131 public:
00132 typedef typename _Key_alloc_type::pointer pointer;
00133 typedef typename _Key_alloc_type::const_pointer const_pointer;
00134 typedef typename _Key_alloc_type::reference reference;
00135 typedef typename _Key_alloc_type::const_reference const_reference;
00136
00137
00138
00139 typedef typename _Rep_type::const_iterator iterator;
00140 typedef typename _Rep_type::const_iterator const_iterator;
00141 typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
00142 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
00143 typedef typename _Rep_type::size_type size_type;
00144 typedef typename _Rep_type::difference_type difference_type;
00145
00146
00147
00151 multiset()
00152 : _M_t(_Compare(), allocator_type()) { }
00153
00154 explicit
00155 multiset(const _Compare& __comp,
00156 const allocator_type& __a = allocator_type())
00157 : _M_t(__comp, __a) { }
00158
00168 template <class _InputIterator>
00169 multiset(_InputIterator __first, _InputIterator __last)
00170 : _M_t(_Compare(), allocator_type())
00171 { _M_t.insert_equal(__first, __last); }
00172
00184 template <class _InputIterator>
00185 multiset(_InputIterator __first, _InputIterator __last,
00186 const _Compare& __comp,
00187 const allocator_type& __a = allocator_type())
00188 : _M_t(__comp, __a)
00189 { _M_t.insert_equal(__first, __last); }
00190
00198 multiset(const multiset<_Key,_Compare,_Alloc>& __x)
00199 : _M_t(__x._M_t) { }
00200
00208 multiset<_Key,_Compare,_Alloc>&
00209 operator=(const multiset<_Key,_Compare,_Alloc>& __x)
00210 {
00211 _M_t = __x._M_t;
00212 return *this;
00213 }
00214
00215
00216
00218 key_compare
00219 key_comp() const
00220 { return _M_t.key_comp(); }
00222 value_compare
00223 value_comp() const
00224 { return _M_t.key_comp(); }
00226 allocator_type
00227 get_allocator() const
00228 { return _M_t.get_allocator(); }
00229
00235 iterator
00236 begin() const
00237 { return _M_t.begin(); }
00238
00244 iterator
00245 end() const
00246 { return _M_t.end(); }
00247
00253 reverse_iterator
00254 rbegin() const
00255 { return _M_t.rbegin(); }
00256
00262 reverse_iterator
00263 rend() const
00264 { return _M_t.rend(); }
00265
00267 bool
00268 empty() const
00269 { return _M_t.empty(); }
00270
00272 size_type
00273 size() const
00274 { return _M_t.size(); }
00275
00277 size_type
00278 max_size() const
00279 { return _M_t.max_size(); }
00280
00292 void
00293 swap(multiset<_Key, _Compare, _Alloc>& __x)
00294 { _M_t.swap(__x._M_t); }
00295
00296
00308 iterator
00309 insert(const value_type& __x)
00310 { return _M_t.insert_equal(__x); }
00311
00332 iterator
00333 insert(iterator __position, const value_type& __x)
00334 { return _M_t.insert_equal(__position, __x); }
00335
00344 template <class _InputIterator>
00345 void
00346 insert(_InputIterator __first, _InputIterator __last)
00347 { _M_t.insert_equal(__first, __last); }
00348
00359 void
00360 erase(iterator __position)
00361 { _M_t.erase(__position); }
00362
00374 size_type
00375 erase(const key_type& __x)
00376 { return _M_t.erase(__x); }
00377
00389 void
00390 erase(iterator __first, iterator __last)
00391 { _M_t.erase(__first, __last); }
00392
00399 void
00400 clear()
00401 { _M_t.clear(); }
00402
00403
00404
00410 size_type
00411 count(const key_type& __x) const
00412 { return _M_t.count(__x); }
00413
00414
00415
00417
00428 iterator
00429 find(const key_type& __x)
00430 { return _M_t.find(__x); }
00431
00432 const_iterator
00433 find(const key_type& __x) const
00434 { return _M_t.find(__x); }
00436
00438
00449 iterator
00450 lower_bound(const key_type& __x)
00451 { return _M_t.lower_bound(__x); }
00452
00453 const_iterator
00454 lower_bound(const key_type& __x) const
00455 { return _M_t.lower_bound(__x); }
00457
00459
00465 iterator
00466 upper_bound(const key_type& __x)
00467 { return _M_t.upper_bound(__x); }
00468
00469 const_iterator
00470 upper_bound(const key_type& __x) const
00471 { return _M_t.upper_bound(__x); }
00473
00475
00490 std::pair<iterator, iterator>
00491 equal_range(const key_type& __x)
00492 { return _M_t.equal_range(__x); }
00493
00494 std::pair<const_iterator, const_iterator>
00495 equal_range(const key_type& __x) const
00496 { return _M_t.equal_range(__x); }
00497
00498 template <class _K1, class _C1, class _A1>
00499 friend bool
00500 operator== (const multiset<_K1, _C1, _A1>&,
00501 const multiset<_K1, _C1, _A1>&);
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
00520 template <class _Key, class _Compare, class _Alloc>
00521 inline bool
00522 operator==(const multiset<_Key, _Compare, _Alloc>& __x,
00523 const multiset<_Key, _Compare, _Alloc>& __y)
00524 { return __x._M_t == __y._M_t; }
00525
00537 template <class _Key, class _Compare, class _Alloc>
00538 inline bool
00539 operator<(const multiset<_Key, _Compare, _Alloc>& __x,
00540 const multiset<_Key, _Compare, _Alloc>& __y)
00541 { return __x._M_t < __y._M_t; }
00542
00544 template <class _Key, class _Compare, class _Alloc>
00545 inline bool
00546 operator!=(const multiset<_Key, _Compare, _Alloc>& __x,
00547 const multiset<_Key, _Compare, _Alloc>& __y)
00548 { return !(__x == __y); }
00549
00551 template <class _Key, class _Compare, class _Alloc>
00552 inline bool
00553 operator>(const multiset<_Key,_Compare,_Alloc>& __x,
00554 const multiset<_Key,_Compare,_Alloc>& __y)
00555 { return __y < __x; }
00556
00558 template <class _Key, class _Compare, class _Alloc>
00559 inline bool
00560 operator<=(const multiset<_Key, _Compare, _Alloc>& __x,
00561 const multiset<_Key, _Compare, _Alloc>& __y)
00562 { return !(__y < __x); }
00563
00565 template <class _Key, class _Compare, class _Alloc>
00566 inline bool
00567 operator>=(const multiset<_Key, _Compare, _Alloc>& __x,
00568 const multiset<_Key, _Compare, _Alloc>& __y)
00569 { return !(__x < __y); }
00570
00572 template <class _Key, class _Compare, class _Alloc>
00573 inline void
00574 swap(multiset<_Key, _Compare, _Alloc>& __x,
00575 multiset<_Key, _Compare, _Alloc>& __y)
00576 { __x.swap(__y); }
00577
00578 }
00579
00580 #endif