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 _MULTIMAP_H
00062 #define _MULTIMAP_H 1
00063
00064 #include <bits/concept_check.h>
00065
00066 namespace _GLIBCXX_STD
00067 {
00068
00069
00070 template <typename _Key, typename _Tp,
00071 typename _Compare = less<_Key>,
00072 typename _Alloc = allocator<pair<const _Key, _Tp> > >
00073 class multimap;
00074
00075 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00076 inline bool
00077 operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
00078 const multimap<_Key,_Tp,_Compare,_Alloc>& __y);
00079
00080 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00081 inline bool
00082 operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
00083 const multimap<_Key,_Tp,_Compare,_Alloc>& __y);
00084
00106 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00107 class multimap
00108 {
00109
00110 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00111 __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
00112 _BinaryFunctionConcept)
00113
00114 public:
00115 typedef _Key key_type;
00116 typedef _Tp mapped_type;
00117 typedef pair<const _Key, _Tp> value_type;
00118 typedef _Compare key_compare;
00119
00120 class value_compare
00121 : public binary_function<value_type, value_type, bool>
00122 {
00123 friend class multimap<_Key,_Tp,_Compare,_Alloc>;
00124 protected:
00125 _Compare comp;
00126
00127 value_compare(_Compare __c)
00128 : comp(__c) { }
00129
00130 public:
00131 bool operator()(const value_type& __x, const value_type& __y) const
00132 { return comp(__x.first, __y.first); }
00133 };
00134
00135 private:
00137 typedef _Rb_tree<key_type, value_type,
00138 _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
00140 _Rep_type _M_t;
00141
00142 public:
00143
00144
00145 typedef typename _Alloc::pointer pointer;
00146 typedef typename _Alloc::const_pointer const_pointer;
00147 typedef typename _Alloc::reference reference;
00148 typedef typename _Alloc::const_reference const_reference;
00149 typedef typename _Rep_type::allocator_type allocator_type;
00150 typedef typename _Rep_type::iterator iterator;
00151 typedef typename _Rep_type::const_iterator const_iterator;
00152 typedef typename _Rep_type::size_type size_type;
00153 typedef typename _Rep_type::difference_type difference_type;
00154 typedef typename _Rep_type::reverse_iterator reverse_iterator;
00155 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
00156
00157
00158
00162 multimap()
00163 : _M_t(_Compare(), allocator_type()) { }
00164
00165
00169 explicit
00170 multimap(const _Compare& __comp,
00171 const allocator_type& __a = allocator_type())
00172 : _M_t(__comp, __a) { }
00173
00181 multimap(const multimap& __x)
00182 : _M_t(__x._M_t) { }
00183
00193 template <typename _InputIterator>
00194 multimap(_InputIterator __first, _InputIterator __last)
00195 : _M_t(_Compare(), allocator_type())
00196 { _M_t.insert_equal(__first, __last); }
00197
00209 template <typename _InputIterator>
00210 multimap(_InputIterator __first, _InputIterator __last,
00211 const _Compare& __comp,
00212 const allocator_type& __a = allocator_type())
00213 : _M_t(__comp, __a)
00214 { _M_t.insert_equal(__first, __last); }
00215
00216
00217
00218
00232 multimap&
00233 operator=(const multimap& __x)
00234 {
00235 _M_t = __x._M_t;
00236 return *this;
00237 }
00238
00240 allocator_type
00241 get_allocator() const
00242 { return _M_t.get_allocator(); }
00243
00244
00250 iterator
00251 begin()
00252 { return _M_t.begin(); }
00253
00259 const_iterator
00260 begin() const
00261 { return _M_t.begin(); }
00262
00268 iterator
00269 end()
00270 { return _M_t.end(); }
00271
00277 const_iterator
00278 end() const
00279 { return _M_t.end(); }
00280
00286 reverse_iterator
00287 rbegin()
00288 { return _M_t.rbegin(); }
00289
00295 const_reverse_iterator
00296 rbegin() const
00297 { return _M_t.rbegin(); }
00298
00304 reverse_iterator
00305 rend()
00306 { return _M_t.rend(); }
00307
00313 const_reverse_iterator
00314 rend() const
00315 { return _M_t.rend(); }
00316
00317
00319 bool
00320 empty() const
00321 { return _M_t.empty(); }
00322
00324 size_type
00325 size() const
00326 { return _M_t.size(); }
00327
00329 size_type
00330 max_size() const
00331 { return _M_t.max_size(); }
00332
00333
00346 iterator
00347 insert(const value_type& __x)
00348 { return _M_t.insert_equal(__x); }
00349
00370 iterator
00371 insert(iterator __position, const value_type& __x)
00372 { return _M_t.insert_equal(__position, __x); }
00373
00382 template <typename _InputIterator>
00383 void
00384 insert(_InputIterator __first, _InputIterator __last)
00385 { _M_t.insert_equal(__first, __last); }
00386
00397 void
00398 erase(iterator __position)
00399 { _M_t.erase(__position); }
00400
00412 size_type
00413 erase(const key_type& __x)
00414 { return _M_t.erase(__x); }
00415
00427 void
00428 erase(iterator __first, iterator __last)
00429 { _M_t.erase(__first, __last); }
00430
00442 void
00443 swap(multimap& __x)
00444 { _M_t.swap(__x._M_t); }
00445
00452 void
00453 clear()
00454 { _M_t.clear(); }
00455
00456
00461 key_compare
00462 key_comp() const
00463 { return _M_t.key_comp(); }
00464
00469 value_compare
00470 value_comp() const
00471 { return value_compare(_M_t.key_comp()); }
00472
00473
00485 iterator
00486 find(const key_type& __x)
00487 { return _M_t.find(__x); }
00488
00500 const_iterator
00501 find(const key_type& __x) const
00502 { return _M_t.find(__x); }
00503
00509 size_type
00510 count(const key_type& __x) const
00511 { return _M_t.count(__x); }
00512
00524 iterator
00525 lower_bound(const key_type& __x)
00526 { return _M_t.lower_bound(__x); }
00527
00539 const_iterator
00540 lower_bound(const key_type& __x) const
00541 { return _M_t.lower_bound(__x); }
00542
00549 iterator
00550 upper_bound(const key_type& __x)
00551 { return _M_t.upper_bound(__x); }
00552
00559 const_iterator
00560 upper_bound(const key_type& __x) const
00561 { return _M_t.upper_bound(__x); }
00562
00576 pair<iterator,iterator>
00577 equal_range(const key_type& __x)
00578 { return _M_t.equal_range(__x); }
00579
00593 pair<const_iterator,const_iterator>
00594 equal_range(const key_type& __x) const
00595 { return _M_t.equal_range(__x); }
00596
00597 template <typename _K1, typename _T1, typename _C1, typename _A1>
00598 friend bool
00599 operator== (const multimap<_K1,_T1,_C1,_A1>&,
00600 const multimap<_K1,_T1,_C1,_A1>&);
00601
00602 template <typename _K1, typename _T1, typename _C1, typename _A1>
00603 friend bool
00604 operator< (const multimap<_K1,_T1,_C1,_A1>&,
00605 const multimap<_K1,_T1,_C1,_A1>&);
00606 };
00607
00618 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00619 inline bool
00620 operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
00621 const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
00622 { return __x._M_t == __y._M_t; }
00623
00635 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00636 inline bool
00637 operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
00638 const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
00639 { return __x._M_t < __y._M_t; }
00640
00642 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00643 inline bool
00644 operator!=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
00645 const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
00646 { return !(__x == __y); }
00647
00649 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00650 inline bool
00651 operator>(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
00652 const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
00653 { return __y < __x; }
00654
00656 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00657 inline bool
00658 operator<=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
00659 const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
00660 { return !(__y < __x); }
00661
00663 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00664 inline bool
00665 operator>=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
00666 const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
00667 { return !(__x < __y); }
00668
00670 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00671 inline void
00672 swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x,
00673 multimap<_Key,_Tp,_Compare,_Alloc>& __y)
00674 { __x.swap(__y); }
00675 }
00676
00677 #endif