00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060 #ifndef _CPP_BITS_STL_MAP_H
00061 #define _CPP_BITS_STL_MAP_H 1
00062
00063 #include <bits/concept_check.h>
00064
00065 namespace std
00066 {
00067
00068 template <class _Key, class _Tp, class _Compare = less<_Key>,
00069 class _Alloc = allocator<pair<const _Key, _Tp> > >
00070 class map
00071 {
00072
00073 __glibcpp_class_requires(_Tp, _SGIAssignableConcept);
00074 __glibcpp_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept);
00075
00076 public:
00077
00078 typedef _Key key_type;
00079 typedef _Tp data_type;
00080 typedef _Tp mapped_type;
00081 typedef pair<const _Key, _Tp> value_type;
00082 typedef _Compare key_compare;
00083
00084 class value_compare
00085 : public binary_function<value_type, value_type, bool> {
00086 friend class map<_Key,_Tp,_Compare,_Alloc>;
00087 protected :
00088 _Compare comp;
00089 value_compare(_Compare __c) : comp(__c) {}
00090 public:
00091 bool operator()(const value_type& __x, const value_type& __y) const {
00092 return comp(__x.first, __y.first);
00093 }
00094 };
00095
00096 private:
00097 typedef _Rb_tree<key_type, value_type,
00098 _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
00099 _Rep_type _M_t;
00100 public:
00101 typedef typename _Rep_type::pointer pointer;
00102 typedef typename _Rep_type::const_pointer const_pointer;
00103 typedef typename _Rep_type::reference reference;
00104 typedef typename _Rep_type::const_reference const_reference;
00105 typedef typename _Rep_type::iterator iterator;
00106 typedef typename _Rep_type::const_iterator const_iterator;
00107 typedef typename _Rep_type::reverse_iterator reverse_iterator;
00108 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
00109 typedef typename _Rep_type::size_type size_type;
00110 typedef typename _Rep_type::difference_type difference_type;
00111 typedef typename _Rep_type::allocator_type allocator_type;
00112
00113
00114
00115 map() : _M_t(_Compare(), allocator_type()) {}
00116 explicit map(const _Compare& __comp,
00117 const allocator_type& __a = allocator_type())
00118 : _M_t(__comp, __a) {}
00119
00120 template <class _InputIterator>
00121 map(_InputIterator __first, _InputIterator __last)
00122 : _M_t(_Compare(), allocator_type())
00123 { _M_t.insert_unique(__first, __last); }
00124
00125 template <class _InputIterator>
00126 map(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
00127 const allocator_type& __a = allocator_type())
00128 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
00129 map(const map<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}
00130
00131 map<_Key,_Tp,_Compare,_Alloc>&
00132 operator=(const map<_Key, _Tp, _Compare, _Alloc>& __x)
00133 {
00134 _M_t = __x._M_t;
00135 return *this;
00136 }
00137
00138
00139
00140 key_compare key_comp() const { return _M_t.key_comp(); }
00141 value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
00142 allocator_type get_allocator() const { return _M_t.get_allocator(); }
00143
00144 iterator begin() { return _M_t.begin(); }
00145 const_iterator begin() const { return _M_t.begin(); }
00146 iterator end() { return _M_t.end(); }
00147 const_iterator end() const { return _M_t.end(); }
00148 reverse_iterator rbegin() { return _M_t.rbegin(); }
00149 const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
00150 reverse_iterator rend() { return _M_t.rend(); }
00151 const_reverse_iterator rend() const { return _M_t.rend(); }
00152 bool empty() const { return _M_t.empty(); }
00153 size_type size() const { return _M_t.size(); }
00154 size_type max_size() const { return _M_t.max_size(); }
00155 _Tp& operator[](const key_type& __k) {
00156 iterator __i = lower_bound(__k);
00157
00158 if (__i == end() || key_comp()(__k, (*__i).first))
00159 __i = insert(__i, value_type(__k, _Tp()));
00160 return (*__i).second;
00161 }
00162 void swap(map<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
00163
00164
00165
00166 pair<iterator,bool> insert(const value_type& __x)
00167 { return _M_t.insert_unique(__x); }
00168 iterator insert(iterator position, const value_type& __x)
00169 { return _M_t.insert_unique(position, __x); }
00170 template <class _InputIterator>
00171 void insert(_InputIterator __first, _InputIterator __last) {
00172 _M_t.insert_unique(__first, __last);
00173 }
00174
00175 void erase(iterator __position) { _M_t.erase(__position); }
00176 size_type erase(const key_type& __x) { return _M_t.erase(__x); }
00177 void erase(iterator __first, iterator __last)
00178 { _M_t.erase(__first, __last); }
00179 void clear() { _M_t.clear(); }
00180
00181
00182
00183 iterator find(const key_type& __x) { return _M_t.find(__x); }
00184 const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
00185 size_type count(const key_type& __x) const {
00186 return _M_t.find(__x) == _M_t.end() ? 0 : 1;
00187 }
00188 iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
00189 const_iterator lower_bound(const key_type& __x) const {
00190 return _M_t.lower_bound(__x);
00191 }
00192 iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
00193 const_iterator upper_bound(const key_type& __x) const {
00194 return _M_t.upper_bound(__x);
00195 }
00196
00197 pair<iterator,iterator> equal_range(const key_type& __x) {
00198 return _M_t.equal_range(__x);
00199 }
00200 pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
00201 return _M_t.equal_range(__x);
00202 }
00203
00204 template <class _K1, class _T1, class _C1, class _A1>
00205 friend bool operator== (const map<_K1, _T1, _C1, _A1>&,
00206 const map<_K1, _T1, _C1, _A1>&);
00207 template <class _K1, class _T1, class _C1, class _A1>
00208 friend bool operator< (const map<_K1, _T1, _C1, _A1>&,
00209 const map<_K1, _T1, _C1, _A1>&);
00210 };
00211
00212 template <class _Key, class _Tp, class _Compare, class _Alloc>
00213 inline bool operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x,
00214 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
00215 return __x._M_t == __y._M_t;
00216 }
00217
00218 template <class _Key, class _Tp, class _Compare, class _Alloc>
00219 inline bool operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x,
00220 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
00221 return __x._M_t < __y._M_t;
00222 }
00223
00224 template <class _Key, class _Tp, class _Compare, class _Alloc>
00225 inline bool operator!=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
00226 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
00227 return !(__x == __y);
00228 }
00229
00230 template <class _Key, class _Tp, class _Compare, class _Alloc>
00231 inline bool operator>(const map<_Key,_Tp,_Compare,_Alloc>& __x,
00232 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
00233 return __y < __x;
00234 }
00235
00236 template <class _Key, class _Tp, class _Compare, class _Alloc>
00237 inline bool operator<=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
00238 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
00239 return !(__y < __x);
00240 }
00241
00242 template <class _Key, class _Tp, class _Compare, class _Alloc>
00243 inline bool operator>=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
00244 const map<_Key,_Tp,_Compare,_Alloc>& __y) {
00245 return !(__x < __y);
00246 }
00247
00248 template <class _Key, class _Tp, class _Compare, class _Alloc>
00249 inline void swap(map<_Key,_Tp,_Compare,_Alloc>& __x,
00250 map<_Key,_Tp,_Compare,_Alloc>& __y) {
00251 __x.swap(__y);
00252 }
00253
00254 }
00255
00256 #endif
00257
00258
00259
00260