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 __SGI_STL_INTERNAL_MULTIMAP_H
32 #define __SGI_STL_INTERNAL_MULTIMAP_H
34 #include <bits/concept_checks.h>
38 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
43 // Forward declaration of operators < and ==, needed for friend declaration.
45 template <class _Key, class _Tp,
46 class _Compare = less<_Key>,
47 class _Alloc = allocator<pair<const _Key, _Tp> > >
50 template <class _Key, class _Tp, class _Compare, class _Alloc>
51 inline bool operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
52 const multimap<_Key,_Tp,_Compare,_Alloc>& __y);
54 template <class _Key, class _Tp, class _Compare, class _Alloc>
55 inline bool operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
56 const multimap<_Key,_Tp,_Compare,_Alloc>& __y);
58 template <class _Key, class _Tp, class _Compare, class _Alloc>
62 __STL_CLASS_REQUIRES(_Tp, _Assignable);
63 __STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key);
69 typedef _Key key_type;
70 typedef _Tp data_type;
71 typedef _Tp mapped_type;
72 typedef pair<const _Key, _Tp> value_type;
73 typedef _Compare key_compare;
75 class value_compare : public binary_function<value_type, value_type, bool> {
76 friend class multimap<_Key,_Tp,_Compare,_Alloc>;
79 value_compare(_Compare __c) : comp(__c) {}
81 bool operator()(const value_type& __x, const value_type& __y) const {
82 return comp(__x.first, __y.first);
87 typedef _Rb_tree<key_type, value_type,
88 _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
89 _Rep_type _M_t; // red-black tree representing multimap
91 typedef typename _Rep_type::pointer pointer;
92 typedef typename _Rep_type::const_pointer const_pointer;
93 typedef typename _Rep_type::reference reference;
94 typedef typename _Rep_type::const_reference const_reference;
95 typedef typename _Rep_type::iterator iterator;
96 typedef typename _Rep_type::const_iterator const_iterator;
97 typedef typename _Rep_type::reverse_iterator reverse_iterator;
98 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
99 typedef typename _Rep_type::size_type size_type;
100 typedef typename _Rep_type::difference_type difference_type;
101 typedef typename _Rep_type::allocator_type allocator_type;
103 // allocation/deallocation
105 multimap() : _M_t(_Compare(), allocator_type()) { }
106 explicit multimap(const _Compare& __comp,
107 const allocator_type& __a = allocator_type())
108 : _M_t(__comp, __a) { }
110 #ifdef __STL_MEMBER_TEMPLATES
111 template <class _InputIterator>
112 multimap(_InputIterator __first, _InputIterator __last)
113 : _M_t(_Compare(), allocator_type())
114 { _M_t.insert_equal(__first, __last); }
116 template <class _InputIterator>
117 multimap(_InputIterator __first, _InputIterator __last,
118 const _Compare& __comp,
119 const allocator_type& __a = allocator_type())
120 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
122 multimap(const value_type* __first, const value_type* __last)
123 : _M_t(_Compare(), allocator_type())
124 { _M_t.insert_equal(__first, __last); }
125 multimap(const value_type* __first, const value_type* __last,
126 const _Compare& __comp,
127 const allocator_type& __a = allocator_type())
128 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
130 multimap(const_iterator __first, const_iterator __last)
131 : _M_t(_Compare(), allocator_type())
132 { _M_t.insert_equal(__first, __last); }
133 multimap(const_iterator __first, const_iterator __last,
134 const _Compare& __comp,
135 const allocator_type& __a = allocator_type())
136 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
137 #endif /* __STL_MEMBER_TEMPLATES */
139 multimap(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) { }
140 multimap<_Key,_Tp,_Compare,_Alloc>&
141 operator=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) {
148 key_compare key_comp() const { return _M_t.key_comp(); }
149 value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
150 allocator_type get_allocator() const { return _M_t.get_allocator(); }
152 iterator begin() { return _M_t.begin(); }
153 const_iterator begin() const { return _M_t.begin(); }
154 iterator end() { return _M_t.end(); }
155 const_iterator end() const { return _M_t.end(); }
156 reverse_iterator rbegin() { return _M_t.rbegin(); }
157 const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
158 reverse_iterator rend() { return _M_t.rend(); }
159 const_reverse_iterator rend() const { return _M_t.rend(); }
160 bool empty() const { return _M_t.empty(); }
161 size_type size() const { return _M_t.size(); }
162 size_type max_size() const { return _M_t.max_size(); }
163 void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
167 iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); }
168 iterator insert(iterator __position, const value_type& __x) {
169 return _M_t.insert_equal(__position, __x);
171 #ifdef __STL_MEMBER_TEMPLATES
172 template <class _InputIterator>
173 void insert(_InputIterator __first, _InputIterator __last) {
174 _M_t.insert_equal(__first, __last);
177 void insert(const value_type* __first, const value_type* __last) {
178 _M_t.insert_equal(__first, __last);
180 void insert(const_iterator __first, const_iterator __last) {
181 _M_t.insert_equal(__first, __last);
183 #endif /* __STL_MEMBER_TEMPLATES */
184 void erase(iterator __position) { _M_t.erase(__position); }
185 size_type erase(const key_type& __x) { return _M_t.erase(__x); }
186 void erase(iterator __first, iterator __last)
187 { _M_t.erase(__first, __last); }
188 void clear() { _M_t.clear(); }
190 // multimap operations:
192 iterator find(const key_type& __x) { return _M_t.find(__x); }
193 const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
194 size_type count(const key_type& __x) const { return _M_t.count(__x); }
195 iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
196 const_iterator lower_bound(const key_type& __x) const {
197 return _M_t.lower_bound(__x);
199 iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
200 const_iterator upper_bound(const key_type& __x) const {
201 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 multimap<_K1, _T1, _C1, _A1>&,
213 const multimap<_K1, _T1, _C1, _A1>&);
214 template <class _K1, class _T1, class _C1, class _A1>
215 friend bool operator< (const multimap<_K1, _T1, _C1, _A1>&,
216 const multimap<_K1, _T1, _C1, _A1>&);
217 #else /* __STL_TEMPLATE_FRIENDS */
218 friend bool __STD_QUALIFIER
219 operator== __STL_NULL_TMPL_ARGS (const multimap&, const multimap&);
220 friend bool __STD_QUALIFIER
221 operator< __STL_NULL_TMPL_ARGS (const multimap&, const multimap&);
222 #endif /* __STL_TEMPLATE_FRIENDS */
225 template <class _Key, class _Tp, class _Compare, class _Alloc>
226 inline bool operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
227 const multimap<_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 multimap<_Key,_Tp,_Compare,_Alloc>& __x,
233 const multimap<_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 multimap<_Key,_Tp,_Compare,_Alloc>& __x,
241 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
242 return !(__x == __y);
245 template <class _Key, class _Tp, class _Compare, class _Alloc>
246 inline bool operator>(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
247 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
251 template <class _Key, class _Tp, class _Compare, class _Alloc>
252 inline bool operator<=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
253 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
257 template <class _Key, class _Tp, class _Compare, class _Alloc>
258 inline bool operator>=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
259 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
263 template <class _Key, class _Tp, class _Compare, class _Alloc>
264 inline void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x,
265 multimap<_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 /* __SGI_STL_INTERNAL_MULTIMAP_H */