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_MAP_H 32 #define __SGI_STL_INTERNAL_MAP_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 map { 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 60 : public binary_function<value_type, value_type, bool> { 61 friend class map<_Key,_Tp,_Compare,_Alloc>; 62 protected : 63 _Compare _M_comp; 64 value_compare(_Compare __c) : _M_comp(__c) {} 65 public: 66 bool operator()(const value_type& __x, const value_type& __y) const { 67 return _M_comp(__x.first, __y.first); 68 } 69 }; 70 71 private: 72 typedef _Rb_tree<key_type, value_type, 73 _Select1st<value_type>, key_compare, _Alloc> _Rep_type; 74 _Rep_type _M_t; // red-black tree representing map 75 public: 76 typedef typename _Rep_type::pointer pointer; 77 typedef typename _Rep_type::const_pointer const_pointer; 78 typedef typename _Rep_type::reference reference; 79 typedef typename _Rep_type::const_reference const_reference; 80 typedef typename _Rep_type::iterator iterator; 81 typedef typename _Rep_type::const_iterator const_iterator; 82 typedef typename _Rep_type::reverse_iterator reverse_iterator; 83 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 84 typedef typename _Rep_type::size_type size_type; 85 typedef typename _Rep_type::difference_type difference_type; 86 typedef typename _Rep_type::allocator_type allocator_type; 87 88 // allocation/deallocation 89 90 map() : _M_t(_Compare(), allocator_type()) {} 91 explicit map(const _Compare& __comp, 92 const allocator_type& __a = allocator_type()) 93 : _M_t(__comp, __a) {} 94 95 #ifdef __STL_MEMBER_TEMPLATES 96 template <class _InputIterator> 97 map(_InputIterator __first, _InputIterator __last) 98 : _M_t(_Compare(), allocator_type()) 99 { _M_t.insert_unique(__first, __last); } 100 101 template <class _InputIterator> 102 map(_InputIterator __first, _InputIterator __last, const _Compare& __comp, 103 const allocator_type& __a = allocator_type()) 104 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 105 #else 106 map(const value_type* __first, const value_type* __last) 107 : _M_t(_Compare(), allocator_type()) 108 { _M_t.insert_unique(__first, __last); } 109 110 map(const value_type* __first, 111 const value_type* __last, const _Compare& __comp, 112 const allocator_type& __a = allocator_type()) 113 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 114 115 map(const_iterator __first, const_iterator __last) 116 : _M_t(_Compare(), allocator_type()) 117 { _M_t.insert_unique(__first, __last); } 118 119 map(const_iterator __first, const_iterator __last, const _Compare& __comp, 120 const allocator_type& __a = allocator_type()) 121 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 122 123 #endif /* __STL_MEMBER_TEMPLATES */ 124 125 map(const map<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {} 126 map<_Key,_Tp,_Compare,_Alloc>& 127 operator=(const map<_Key, _Tp, _Compare, _Alloc>& __x) 128 { 129 _M_t = __x._M_t; 130 return *this; 131 } 132 133 // accessors: 134 135 key_compare key_comp() const { return _M_t.key_comp(); } 136 value_compare value_comp() const { return value_compare(_M_t.key_comp()); } 137 allocator_type get_allocator() const { return _M_t.get_allocator(); } 138 139 iterator begin() { return _M_t.begin(); } 140 const_iterator begin() const { return _M_t.begin(); } 141 iterator end() { return _M_t.end(); } 142 const_iterator end() const { return _M_t.end(); } 143 reverse_iterator rbegin() { return _M_t.rbegin(); } 144 const_reverse_iterator rbegin() const { return _M_t.rbegin(); } 145 reverse_iterator rend() { return _M_t.rend(); } 146 const_reverse_iterator rend() const { return _M_t.rend(); } 147 bool empty() const { return _M_t.empty(); } 148 size_type size() const { return _M_t.size(); } 149 size_type max_size() const { return _M_t.max_size(); } 150 _Tp& operator[](const key_type& __k) { 151 iterator __i = lower_bound(__k); 152 // __i->first is greater than or equivalent to __k. 153 if (__i == end() || key_comp()(__k, (*__i).first)) 154 __i = insert(__i, value_type(__k, _Tp())); 155 return (*__i).second; 156 } 157 void swap(map<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); } 158 159 // insert/erase 160 161 pair<iterator,bool> insert(const value_type& __x) 162 { return _M_t.insert_unique(__x); } 163 iterator insert(iterator position, const value_type& __x) 164 { return _M_t.insert_unique(position, __x); } 165 #ifdef __STL_MEMBER_TEMPLATES 166 template <class _InputIterator> 167 void insert(_InputIterator __first, _InputIterator __last) { 168 _M_t.insert_unique(__first, __last); 169 } 170 #else 171 void insert(const value_type* __first, const value_type* __last) { 172 _M_t.insert_unique(__first, __last); 173 } 174 void insert(const_iterator __first, const_iterator __last) { 175 _M_t.insert_unique(__first, __last); 176 } 177 #endif /* __STL_MEMBER_TEMPLATES */ 178 179 void erase(iterator __position) { _M_t.erase(__position); } 180 size_type erase(const key_type& __x) { return _M_t.erase(__x); } 181 void erase(iterator __first, iterator __last) 182 { _M_t.erase(__first, __last); } 183 void clear() { _M_t.clear(); } 184 185 // map operations: 186 187 iterator find(const key_type& __x) { return _M_t.find(__x); } 188 const_iterator find(const key_type& __x) const { return _M_t.find(__x); } 189 size_type count(const key_type& __x) const { return _M_t.count(__x); } 190 iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); } 191 const_iterator lower_bound(const key_type& __x) const { 192 return _M_t.lower_bound(__x); 193 } 194 iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); } 195 const_iterator upper_bound(const key_type& __x) const { 196 return _M_t.upper_bound(__x); 197 } 198 199 pair<iterator,iterator> equal_range(const key_type& __x) { 200 return _M_t.equal_range(__x); 201 } 202 pair<const_iterator,const_iterator> equal_range(const key_type& __x) const { 203 return _M_t.equal_range(__x); 204 } 205 friend bool operator== __STL_NULL_TMPL_ARGS (const map&, const map&); 206 friend bool operator< __STL_NULL_TMPL_ARGS (const map&, const map&); 207 }; 208 209 template <class _Key, class _Tp, class _Compare, class _Alloc> 210 inline bool operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x, 211 const map<_Key,_Tp,_Compare,_Alloc>& __y) { 212 return __x._M_t == __y._M_t; 213 } 214 215 template <class _Key, class _Tp, class _Compare, class _Alloc> 216 inline bool operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x, 217 const map<_Key,_Tp,_Compare,_Alloc>& __y) { 218 return __x._M_t < __y._M_t; 219 } 220 221 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER 222 223 template <class _Key, class _Tp, class _Compare, class _Alloc> 224 inline void swap(map<_Key,_Tp,_Compare,_Alloc>& __x, 225 map<_Key,_Tp,_Compare,_Alloc>& __y) { 226 __x.swap(__y); 227 } 228 229 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ 230 231 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 232 #pragma reset woff 1174 233 #pragma reset woff 1375 234 #endif 235 236 __STL_END_NAMESPACE 237 238 #endif /* __SGI_STL_INTERNAL_MAP_H */ 239 240 // Local Variables: 241 // mode:C++ 242 // End: 243