1 /* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Permission to use, copy, modify, distribute and sell this software 7 * and its documentation for any purpose is hereby granted without fee, 8 * provided that the above copyright notice appear in all copies and 9 * that both that copyright notice and this permission notice appear 10 * in supporting documentation. Hewlett-Packard Company makes no 11 * representations about the suitability of this software for any 12 * purpose. It is provided "as is" without express or implied warranty. 13 * 14 * 15 * Copyright (c) 1996,1997 16 * Silicon Graphics Computer Systems, Inc. 17 * 18 * Permission to use, copy, modify, distribute and sell this software 19 * and its documentation for any purpose is hereby granted without fee, 20 * provided that the above copyright notice appear in all copies and 21 * that both that copyright notice and this permission notice appear 22 * in supporting documentation. Silicon Graphics makes no 23 * representations about the suitability of this software for any 24 * purpose. It is provided "as is" without express or implied warranty. 25 */ 26 27 /* NOTE: This is an internal header file, included by other STL headers. 28 * You should not attempt to use it directly. 29 */ 30 31 #ifndef __SGI_STL_INTERNAL_MULTIMAP_H 32 #define __SGI_STL_INTERNAL_MULTIMAP_H 33 34 __STL_BEGIN_NAMESPACE 35 36 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 37 #pragma set woff 1174 38 #pragma set woff 1375 39 #endif 40 41 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES 42 template <class _Key, class _Tp, class _Compare = less<_Key>, 43 class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > 44 #else 45 template <class _Key, class _Tp, class _Compare, 46 class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > 47 #endif 48 class multimap { 49 public: 50 51 // typedefs: 52 53 typedef _Key key_type; 54 typedef _Tp data_type; 55 typedef _Tp mapped_type; 56 typedef pair<const _Key, _Tp> value_type; 57 typedef _Compare key_compare; 58 59 class value_compare : public binary_function<value_type, value_type, bool> { 60 friend class multimap<_Key,_Tp,_Compare,_Alloc>; 61 protected: 62 _Compare _M_comp; 63 value_compare(_Compare __c) : _M_comp(__c) {} 64 public: 65 bool operator()(const value_type& __x, const value_type& __y) const { 66 return _M_comp(__x.first, __y.first); 67 } 68 }; 69 70 private: 71 typedef _Rb_tree<key_type, value_type, 72 _Select1st<value_type>, key_compare, _Alloc> _Rep_type; 73 _Rep_type _M_t; // red-black tree representing multimap 74 public: 75 typedef typename _Rep_type::pointer pointer; 76 typedef typename _Rep_type::const_pointer const_pointer; 77 typedef typename _Rep_type::reference reference; 78 typedef typename _Rep_type::const_reference const_reference; 79 typedef typename _Rep_type::iterator iterator; 80 typedef typename _Rep_type::const_iterator const_iterator; 81 typedef typename _Rep_type::reverse_iterator reverse_iterator; 82 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 83 typedef typename _Rep_type::size_type size_type; 84 typedef typename _Rep_type::difference_type difference_type; 85 typedef typename _Rep_type::allocator_type allocator_type; 86 87 // allocation/deallocation 88 89 multimap() : _M_t(_Compare(), allocator_type()) { } 90 explicit multimap(const _Compare& __comp, 91 const allocator_type& __a = allocator_type()) 92 : _M_t(__comp, __a) { } 93 94 #ifdef __STL_MEMBER_TEMPLATES 95 template <class _InputIterator> 96 multimap(_InputIterator __first, _InputIterator __last) 97 : _M_t(_Compare(), allocator_type()) 98 { _M_t.insert_equal(__first, __last); } 99 100 template <class _InputIterator> 101 multimap(_InputIterator __first, _InputIterator __last, 102 const _Compare& __comp, 103 const allocator_type& __a = allocator_type()) 104 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 105 #else 106 multimap(const value_type* __first, const value_type* __last) 107 : _M_t(_Compare(), allocator_type()) 108 { _M_t.insert_equal(__first, __last); } 109 multimap(const value_type* __first, const value_type* __last, 110 const _Compare& __comp, 111 const allocator_type& __a = allocator_type()) 112 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 113 114 multimap(const_iterator __first, const_iterator __last) 115 : _M_t(_Compare(), allocator_type()) 116 { _M_t.insert_equal(__first, __last); } 117 multimap(const_iterator __first, const_iterator __last, 118 const _Compare& __comp, 119 const allocator_type& __a = allocator_type()) 120 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 121 #endif /* __STL_MEMBER_TEMPLATES */ 122 123 multimap(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) { } 124 multimap<_Key,_Tp,_Compare,_Alloc>& 125 operator=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) { 126 _M_t = __x._M_t; 127 return *this; 128 } 129 130 // accessors: 131 132 key_compare key_comp() const { return _M_t.key_comp(); } 133 value_compare value_comp() const { return value_compare(_M_t.key_comp()); } 134 allocator_type get_allocator() const { return _M_t.get_allocator(); } 135 136 iterator begin() { return _M_t.begin(); } 137 const_iterator begin() const { return _M_t.begin(); } 138 iterator end() { return _M_t.end(); } 139 const_iterator end() const { return _M_t.end(); } 140 reverse_iterator rbegin() { return _M_t.rbegin(); } 141 const_reverse_iterator rbegin() const { return _M_t.rbegin(); } 142 reverse_iterator rend() { return _M_t.rend(); } 143 const_reverse_iterator rend() const { return _M_t.rend(); } 144 bool empty() const { return _M_t.empty(); } 145 size_type size() const { return _M_t.size(); } 146 size_type max_size() const { return _M_t.max_size(); } 147 void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); } 148 149 // insert/erase 150 151 iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); } 152 iterator insert(iterator __position, const value_type& __x) { 153 return _M_t.insert_equal(__position, __x); 154 } 155 #ifdef __STL_MEMBER_TEMPLATES 156 template <class _InputIterator> 157 void insert(_InputIterator __first, _InputIterator __last) { 158 _M_t.insert_equal(__first, __last); 159 } 160 #else 161 void insert(const value_type* __first, const value_type* __last) { 162 _M_t.insert_equal(__first, __last); 163 } 164 void insert(const_iterator __first, const_iterator __last) { 165 _M_t.insert_equal(__first, __last); 166 } 167 #endif /* __STL_MEMBER_TEMPLATES */ 168 void erase(iterator __position) { _M_t.erase(__position); } 169 size_type erase(const key_type& __x) { return _M_t.erase(__x); } 170 void erase(iterator __first, iterator __last) 171 { _M_t.erase(__first, __last); } 172 void clear() { _M_t.clear(); } 173 174 // multimap operations: 175 176 iterator find(const key_type& __x) { return _M_t.find(__x); } 177 const_iterator find(const key_type& __x) const { return _M_t.find(__x); } 178 size_type count(const key_type& __x) const { return _M_t.count(__x); } 179 iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); } 180 const_iterator lower_bound(const key_type& __x) const { 181 return _M_t.lower_bound(__x); 182 } 183 iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); } 184 const_iterator upper_bound(const key_type& __x) const { 185 return _M_t.upper_bound(__x); 186 } 187 pair<iterator,iterator> equal_range(const key_type& __x) { 188 return _M_t.equal_range(__x); 189 } 190 pair<const_iterator,const_iterator> equal_range(const key_type& __x) const { 191 return _M_t.equal_range(__x); 192 } 193 friend bool operator== __STL_NULL_TMPL_ARGS (const multimap&, 194 const multimap&); 195 friend bool operator< __STL_NULL_TMPL_ARGS (const multimap&, 196 const multimap&); 197 }; 198 199 template <class _Key, class _Tp, class _Compare, class _Alloc> 200 inline bool operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 201 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) { 202 return __x._M_t == __y._M_t; 203 } 204 205 template <class _Key, class _Tp, class _Compare, class _Alloc> 206 inline bool operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 207 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) { 208 return __x._M_t < __y._M_t; 209 } 210 211 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER 212 213 template <class _Key, class _Tp, class _Compare, class _Alloc> 214 inline void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x, 215 multimap<_Key,_Tp,_Compare,_Alloc>& __y) { 216 __x.swap(__y); 217 } 218 219 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ 220 221 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 222 #pragma reset woff 1174 223 #pragma reset woff 1375 224 #endif 225 226 __STL_END_NAMESPACE 227 228 #endif /* __SGI_STL_INTERNAL_MULTIMAP_H */ 229 230 // Local Variables: 231 // mode:C++ 232 // End: 233