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 = std::less<_Key>,
00072 typename _Alloc = std::allocator<std::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 public:
00110 typedef _Key key_type;
00111 typedef _Tp mapped_type;
00112 typedef std::pair<const _Key, _Tp> value_type;
00113 typedef _Compare key_compare;
00114 typedef _Alloc allocator_type;
00115
00116 private:
00117
00118 typedef typename _Alloc::value_type _Alloc_value_type;
00119 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00120 __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
00121 _BinaryFunctionConcept)
00122 __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
00123
00124 public:
00125 class value_compare
00126 : public std::binary_function<value_type, value_type, bool>
00127 {
00128 friend class multimap<_Key, _Tp, _Compare, _Alloc>;
00129 protected:
00130 _Compare comp;
00131
00132 value_compare(_Compare __c)
00133 : comp(__c) { }
00134
00135 public:
00136 bool operator()(const value_type& __x, const value_type& __y) const
00137 { return comp(__x.first, __y.first); }
00138 };
00139
00140 private:
00142 typedef typename _Alloc::template rebind<value_type>::other
00143 _Pair_alloc_type;
00144
00145 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
00146 key_compare, _Pair_alloc_type> _Rep_type;
00148 _Rep_type _M_t;
00149
00150 public:
00151
00152
00153 typedef typename _Pair_alloc_type::pointer pointer;
00154 typedef typename _Pair_alloc_type::const_pointer const_pointer;
00155 typedef typename _Pair_alloc_type::reference reference;
00156 typedef typename _Pair_alloc_type::const_reference const_reference;
00157 typedef typename _Rep_type::iterator iterator;
00158 typedef typename _Rep_type::const_iterator const_iterator;
00159 typedef typename _Rep_type::size_type size_type;
00160 typedef typename _Rep_type::difference_type difference_type;
00161 typedef typename _Rep_type::reverse_iterator reverse_iterator;
00162 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
00163
00164
00165
00169 multimap()
00170 : _M_t(_Compare(), allocator_type()) { }
00171
00172
00176 explicit
00177 multimap(const _Compare& __comp,
00178 const allocator_type& __a = allocator_type())
00179 : _M_t(__comp, __a) { }
00180
00188 multimap(const multimap& __x)
00189 : _M_t(__x._M_t) { }
00190
00200 template <typename _InputIterator>
00201 multimap(_InputIterator __first, _InputIterator __last)
00202 : _M_t(_Compare(), allocator_type())
00203 { _M_t.insert_equal(__first, __last); }
00204
00216 template <typename _InputIterator>
00217 multimap(_InputIterator __first, _InputIterator __last,
00218 const _Compare& __comp,
00219 const allocator_type& __a = allocator_type())
00220 : _M_t(__comp, __a)
00221 { _M_t.insert_equal(__first, __last); }
00222
00223
00224
00225
00239 multimap&
00240 operator=(const multimap& __x)
00241 {
00242 _M_t = __x._M_t;
00243 return *this;
00244 }
00245
00247 allocator_type
00248 get_allocator() const
00249 { return _M_t.get_allocator(); }
00250
00251
00257 iterator
00258 begin()
00259 { return _M_t.begin(); }
00260
00266 const_iterator
00267 begin() const
00268 { return _M_t.begin(); }
00269
00275 iterator
00276 end()
00277 { return _M_t.end(); }
00278
00284 const_iterator
00285 end() const
00286 { return _M_t.end(); }
00287
00293 reverse_iterator
00294 rbegin()
00295 { return _M_t.rbegin(); }
00296
00302 const_reverse_iterator
00303 rbegin() const
00304 { return _M_t.rbegin(); }
00305
00311 reverse_iterator
00312 rend()
00313 { return _M_t.rend(); }
00314
00320 const_reverse_iterator
00321 rend() const
00322 { return _M_t.rend(); }
00323
00324
00326 bool
00327 empty() const
00328 { return _M_t.empty(); }
00329
00331 size_type
00332 size() const
00333 { return _M_t.size(); }
00334
00336 size_type
00337 max_size() const
00338 { return _M_t.max_size(); }
00339
00340
00353 iterator
00354 insert(const value_type& __x)
00355 { return _M_t.insert_equal(__x); }
00356
00377 iterator
00378 insert(iterator __position, const value_type& __x)
00379 { return _M_t.insert_equal(__position, __x); }
00380
00389 template <typename _InputIterator>
00390 void
00391 insert(_InputIterator __first, _InputIterator __last)
00392 { _M_t.insert_equal(__first, __last); }
00393
00404 void
00405 erase(iterator __position)
00406 { _M_t.erase(__position); }
00407
00419 size_type
00420 erase(const key_type& __x)
00421 { return _M_t.erase(__x); }
00422
00434 void
00435 erase(iterator __first, iterator __last)
00436 { _M_t.erase(__first, __last); }
00437
00449 void
00450 swap(multimap& __x)
00451 { _M_t.swap(__x._M_t); }
00452
00459 void
00460 clear()
00461 { _M_t.clear(); }
00462
00463
00468 key_compare
00469 key_comp() const
00470 { return _M_t.key_comp(); }
00471
00476 value_compare
00477 value_comp() const
00478 { return value_compare(_M_t.key_comp()); }
00479
00480
00492 iterator
00493 find(const key_type& __x)
00494 { return _M_t.find(__x); }
00495
00507 const_iterator
00508 find(const key_type& __x) const
00509 { return _M_t.find(__x); }
00510
00516 size_type
00517 count(const key_type& __x) const
00518 { return _M_t.count(__x); }
00519
00531 iterator
00532 lower_bound(const key_type& __x)
00533 { return _M_t.lower_bound(__x); }
00534
00546 const_iterator
00547 lower_bound(const key_type& __x) const
00548 { return _M_t.lower_bound(__x); }
00549
00556 iterator
00557 upper_bound(const key_type& __x)
00558 { return _M_t.upper_bound(__x); }
00559
00566 const_iterator
00567 upper_bound(const key_type& __x) const
00568 { return _M_t.upper_bound(__x); }
00569
00583 std::pair<iterator, iterator>
00584 equal_range(const key_type& __x)
00585 { return _M_t.equal_range(__x); }
00586
00600 std::pair<const_iterator, const_iterator>
00601 equal_range(const key_type& __x) const
00602 { return _M_t.equal_range(__x); }
00603
00604 template <typename _K1, typename _T1, typename _C1, typename _A1>
00605 friend bool
00606 operator== (const multimap<_K1, _T1, _C1, _A1>&,
00607 const multimap<_K1, _T1, _C1, _A1>&);
00608
00609 template <typename _K1, typename _T1, typename _C1, typename _A1>
00610 friend bool
00611 operator< (const multimap<_K1, _T1, _C1, _A1>&,
00612 const multimap<_K1, _T1, _C1, _A1>&);
00613 };
00614
00625 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00626 inline bool
00627 operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
00628 const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
00629 { return __x._M_t == __y._M_t; }
00630
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._M_t < __y._M_t; }
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 !(__x == __y); }
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 !(__y < __x); }
00668
00670 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00671 inline bool
00672 operator>=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
00673 const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
00674 { return !(__x < __y); }
00675
00677 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00678 inline void
00679 swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x,
00680 multimap<_Key, _Tp, _Compare, _Alloc>& __y)
00681 { __x.swap(__y); }
00682 }
00683
00684 #endif