4 * Hewlett-Packard Company
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.
15 * Copyright (c) 1996,1997
16 * Silicon Graphics Computer Systems, Inc.
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.
27 /* NOTE: This is an internal header file, included by other STL headers.
28 * You should not attempt to use it directly.
31 #ifndef _CPP_BITS_STL_MAP_H
32 #define _CPP_BITS_STL_MAP_H 1
34 #include <bits/concept_checks.h>
38 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
43 template <class _Key, class _Tp, class _Compare = less<_Key>,
44 class _Alloc = allocator<pair<const _Key, _Tp> > >
50 __STL_CLASS_REQUIRES(_Tp, _Assignable);
51 __STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key);
55 typedef _Key key_type;
56 typedef _Tp data_type;
57 typedef _Tp mapped_type;
58 typedef pair<const _Key, _Tp> value_type;
59 typedef _Compare key_compare;
62 : public binary_function<value_type, value_type, bool> {
63 friend class map<_Key,_Tp,_Compare,_Alloc>;
66 value_compare(_Compare __c) : comp(__c) {}
68 bool operator()(const value_type& __x, const value_type& __y) const {
69 return comp(__x.first, __y.first);
74 typedef _Rb_tree<key_type, value_type,
75 _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
76 _Rep_type _M_t; // red-black tree representing map
78 typedef typename _Rep_type::pointer pointer;
79 typedef typename _Rep_type::const_pointer const_pointer;
80 typedef typename _Rep_type::reference reference;
81 typedef typename _Rep_type::const_reference const_reference;
82 typedef typename _Rep_type::iterator iterator;
83 typedef typename _Rep_type::const_iterator const_iterator;
84 typedef typename _Rep_type::reverse_iterator reverse_iterator;
85 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
86 typedef typename _Rep_type::size_type size_type;
87 typedef typename _Rep_type::difference_type difference_type;
88 typedef typename _Rep_type::allocator_type allocator_type;
90 // allocation/deallocation
92 map() : _M_t(_Compare(), allocator_type()) {}
93 explicit map(const _Compare& __comp,
94 const allocator_type& __a = allocator_type())
95 : _M_t(__comp, __a) {}
97 #ifdef __STL_MEMBER_TEMPLATES
98 template <class _InputIterator>
99 map(_InputIterator __first, _InputIterator __last)
100 : _M_t(_Compare(), allocator_type())
101 { _M_t.insert_unique(__first, __last); }
103 template <class _InputIterator>
104 map(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
105 const allocator_type& __a = allocator_type())
106 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
108 map(const value_type* __first, const value_type* __last)
109 : _M_t(_Compare(), allocator_type())
110 { _M_t.insert_unique(__first, __last); }
112 map(const value_type* __first,
113 const value_type* __last, const _Compare& __comp,
114 const allocator_type& __a = allocator_type())
115 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
117 map(const_iterator __first, const_iterator __last)
118 : _M_t(_Compare(), allocator_type())
119 { _M_t.insert_unique(__first, __last); }
121 map(const_iterator __first, const_iterator __last, const _Compare& __comp,
122 const allocator_type& __a = allocator_type())
123 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
125 #endif /* __STL_MEMBER_TEMPLATES */
127 map(const map<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}
128 map<_Key,_Tp,_Compare,_Alloc>&
129 operator=(const map<_Key, _Tp, _Compare, _Alloc>& __x)
137 key_compare key_comp() const { return _M_t.key_comp(); }
138 value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
139 allocator_type get_allocator() const { return _M_t.get_allocator(); }
141 iterator begin() { return _M_t.begin(); }
142 const_iterator begin() const { return _M_t.begin(); }
143 iterator end() { return _M_t.end(); }
144 const_iterator end() const { return _M_t.end(); }
145 reverse_iterator rbegin() { return _M_t.rbegin(); }
146 const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
147 reverse_iterator rend() { return _M_t.rend(); }
148 const_reverse_iterator rend() const { return _M_t.rend(); }
149 bool empty() const { return _M_t.empty(); }
150 size_type size() const { return _M_t.size(); }
151 size_type max_size() const { return _M_t.max_size(); }
152 _Tp& operator[](const key_type& __k) {
153 iterator __i = lower_bound(__k);
154 // __i->first is greater than or equivalent to __k.
155 if (__i == end() || key_comp()(__k, (*__i).first))
156 __i = insert(__i, value_type(__k, _Tp()));
157 return (*__i).second;
159 void swap(map<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
163 pair<iterator,bool> insert(const value_type& __x)
164 { return _M_t.insert_unique(__x); }
165 iterator insert(iterator position, const value_type& __x)
166 { return _M_t.insert_unique(position, __x); }
167 #ifdef __STL_MEMBER_TEMPLATES
168 template <class _InputIterator>
169 void insert(_InputIterator __first, _InputIterator __last) {
170 _M_t.insert_unique(__first, __last);
173 void insert(const value_type* __first, const value_type* __last) {
174 _M_t.insert_unique(__first, __last);
176 void insert(const_iterator __first, const_iterator __last) {
177 _M_t.insert_unique(__first, __last);
179 #endif /* __STL_MEMBER_TEMPLATES */
181 void erase(iterator __position) { _M_t.erase(__position); }
182 size_type erase(const key_type& __x) { return _M_t.erase(__x); }
183 void erase(iterator __first, iterator __last)
184 { _M_t.erase(__first, __last); }
185 void clear() { _M_t.clear(); }
189 iterator find(const key_type& __x) { return _M_t.find(__x); }
190 const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
191 size_type count(const key_type& __x) const {
192 return _M_t.find(__x) == _M_t.end() ? 0 : 1;
194 iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
195 const_iterator lower_bound(const key_type& __x) const {
196 return _M_t.lower_bound(__x);
198 iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
199 const_iterator upper_bound(const key_type& __x) const {
200 return _M_t.upper_bound(__x);
203 pair<iterator,iterator> equal_range(const key_type& __x) {
204 return _M_t.equal_range(__x);
206 pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
207 return _M_t.equal_range(__x);
210 #ifdef __STL_TEMPLATE_FRIENDS
211 template <class _K1, class _T1, class _C1, class _A1>
212 friend bool operator== (const map<_K1, _T1, _C1, _A1>&,
213 const map<_K1, _T1, _C1, _A1>&);
214 template <class _K1, class _T1, class _C1, class _A1>
215 friend bool operator< (const map<_K1, _T1, _C1, _A1>&,
216 const map<_K1, _T1, _C1, _A1>&);
217 #else /* __STL_TEMPLATE_FRIENDS */
218 friend bool __STD_QUALIFIER
219 operator== __STL_NULL_TMPL_ARGS (const map&, const map&);
220 friend bool __STD_QUALIFIER
221 operator< __STL_NULL_TMPL_ARGS (const map&, const map&);
222 #endif /* __STL_TEMPLATE_FRIENDS */
225 template <class _Key, class _Tp, class _Compare, class _Alloc>
226 inline bool operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x,
227 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
228 return __x._M_t == __y._M_t;
231 template <class _Key, class _Tp, class _Compare, class _Alloc>
232 inline bool operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x,
233 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
234 return __x._M_t < __y._M_t;
237 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
239 template <class _Key, class _Tp, class _Compare, class _Alloc>
240 inline bool operator!=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
241 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
242 return !(__x == __y);
245 template <class _Key, class _Tp, class _Compare, class _Alloc>
246 inline bool operator>(const map<_Key,_Tp,_Compare,_Alloc>& __x,
247 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
251 template <class _Key, class _Tp, class _Compare, class _Alloc>
252 inline bool operator<=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
253 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
257 template <class _Key, class _Tp, class _Compare, class _Alloc>
258 inline bool operator>=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
259 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
263 template <class _Key, class _Tp, class _Compare, class _Alloc>
264 inline void swap(map<_Key,_Tp,_Compare,_Alloc>& __x,
265 map<_Key,_Tp,_Compare,_Alloc>& __y) {
269 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
271 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
272 #pragma reset woff 1174
273 #pragma reset woff 1375
278 #endif /* _CPP_BITS_STL_MAP_H */