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_check.h>
39 template <class _Key, class _Tp, class _Compare = less<_Key>,
40 class _Alloc = allocator<pair<const _Key, _Tp> > >
43 // concept requirements
44 __glibcpp_class_requires(_Tp, _SGIAssignableConcept);
45 __glibcpp_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept);
49 typedef _Key key_type;
50 typedef _Tp data_type;
51 typedef _Tp mapped_type;
52 typedef pair<const _Key, _Tp> value_type;
53 typedef _Compare key_compare;
56 : public binary_function<value_type, value_type, bool> {
57 friend class map<_Key,_Tp,_Compare,_Alloc>;
60 value_compare(_Compare __c) : comp(__c) {}
62 bool operator()(const value_type& __x, const value_type& __y) const {
63 return comp(__x.first, __y.first);
68 typedef _Rb_tree<key_type, value_type,
69 _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
70 _Rep_type _M_t; // red-black tree representing map
72 typedef typename _Rep_type::pointer pointer;
73 typedef typename _Rep_type::const_pointer const_pointer;
74 typedef typename _Rep_type::reference reference;
75 typedef typename _Rep_type::const_reference const_reference;
76 typedef typename _Rep_type::iterator iterator;
77 typedef typename _Rep_type::const_iterator const_iterator;
78 typedef typename _Rep_type::reverse_iterator reverse_iterator;
79 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
80 typedef typename _Rep_type::size_type size_type;
81 typedef typename _Rep_type::difference_type difference_type;
82 typedef typename _Rep_type::allocator_type allocator_type;
84 // allocation/deallocation
86 map() : _M_t(_Compare(), allocator_type()) {}
87 explicit map(const _Compare& __comp,
88 const allocator_type& __a = allocator_type())
89 : _M_t(__comp, __a) {}
91 template <class _InputIterator>
92 map(_InputIterator __first, _InputIterator __last)
93 : _M_t(_Compare(), allocator_type())
94 { _M_t.insert_unique(__first, __last); }
96 template <class _InputIterator>
97 map(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
98 const allocator_type& __a = allocator_type())
99 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
100 map(const map<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}
102 map<_Key,_Tp,_Compare,_Alloc>&
103 operator=(const map<_Key, _Tp, _Compare, _Alloc>& __x)
111 key_compare key_comp() const { return _M_t.key_comp(); }
112 value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
113 allocator_type get_allocator() const { return _M_t.get_allocator(); }
115 iterator begin() { return _M_t.begin(); }
116 const_iterator begin() const { return _M_t.begin(); }
117 iterator end() { return _M_t.end(); }
118 const_iterator end() const { return _M_t.end(); }
119 reverse_iterator rbegin() { return _M_t.rbegin(); }
120 const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
121 reverse_iterator rend() { return _M_t.rend(); }
122 const_reverse_iterator rend() const { return _M_t.rend(); }
123 bool empty() const { return _M_t.empty(); }
124 size_type size() const { return _M_t.size(); }
125 size_type max_size() const { return _M_t.max_size(); }
126 _Tp& operator[](const key_type& __k) {
127 iterator __i = lower_bound(__k);
128 // __i->first is greater than or equivalent to __k.
129 if (__i == end() || key_comp()(__k, (*__i).first))
130 __i = insert(__i, value_type(__k, _Tp()));
131 return (*__i).second;
133 void swap(map<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
137 pair<iterator,bool> insert(const value_type& __x)
138 { return _M_t.insert_unique(__x); }
139 iterator insert(iterator position, const value_type& __x)
140 { return _M_t.insert_unique(position, __x); }
141 template <class _InputIterator>
142 void insert(_InputIterator __first, _InputIterator __last) {
143 _M_t.insert_unique(__first, __last);
146 void erase(iterator __position) { _M_t.erase(__position); }
147 size_type erase(const key_type& __x) { return _M_t.erase(__x); }
148 void erase(iterator __first, iterator __last)
149 { _M_t.erase(__first, __last); }
150 void clear() { _M_t.clear(); }
154 iterator find(const key_type& __x) { return _M_t.find(__x); }
155 const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
156 size_type count(const key_type& __x) const {
157 return _M_t.find(__x) == _M_t.end() ? 0 : 1;
159 iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
160 const_iterator lower_bound(const key_type& __x) const {
161 return _M_t.lower_bound(__x);
163 iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
164 const_iterator upper_bound(const key_type& __x) const {
165 return _M_t.upper_bound(__x);
168 pair<iterator,iterator> equal_range(const key_type& __x) {
169 return _M_t.equal_range(__x);
171 pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
172 return _M_t.equal_range(__x);
175 template <class _K1, class _T1, class _C1, class _A1>
176 friend bool operator== (const map<_K1, _T1, _C1, _A1>&,
177 const map<_K1, _T1, _C1, _A1>&);
178 template <class _K1, class _T1, class _C1, class _A1>
179 friend bool operator< (const map<_K1, _T1, _C1, _A1>&,
180 const map<_K1, _T1, _C1, _A1>&);
183 template <class _Key, class _Tp, class _Compare, class _Alloc>
184 inline bool operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x,
185 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
186 return __x._M_t == __y._M_t;
189 template <class _Key, class _Tp, class _Compare, class _Alloc>
190 inline bool operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x,
191 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
192 return __x._M_t < __y._M_t;
195 template <class _Key, class _Tp, class _Compare, class _Alloc>
196 inline bool operator!=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
197 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
198 return !(__x == __y);
201 template <class _Key, class _Tp, class _Compare, class _Alloc>
202 inline bool operator>(const map<_Key,_Tp,_Compare,_Alloc>& __x,
203 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
207 template <class _Key, class _Tp, class _Compare, class _Alloc>
208 inline bool operator<=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
209 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
213 template <class _Key, class _Tp, class _Compare, class _Alloc>
214 inline bool operator>=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
215 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
219 template <class _Key, class _Tp, class _Compare, class _Alloc>
220 inline void swap(map<_Key,_Tp,_Compare,_Alloc>& __x,
221 map<_Key,_Tp,_Compare,_Alloc>& __y) {
227 #endif /* _CPP_BITS_STL_MAP_H */