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
00061 #ifndef _MAP_H
00062 #define _MAP_H 1
00063
00064 #include <bits/concept_check.h>
00065
00066 namespace _GLIBCXX_STD
00067 {
00089 template <typename _Key, typename _Tp, typename _Compare = less<_Key>,
00090 typename _Alloc = allocator<pair<const _Key, _Tp> > >
00091 class map
00092 {
00093
00094 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00095 __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
00096 _BinaryFunctionConcept)
00097
00098 public:
00099 typedef _Key key_type;
00100 typedef _Tp mapped_type;
00101 typedef pair<const _Key, _Tp> value_type;
00102 typedef _Compare key_compare;
00103
00104 class value_compare
00105 : public binary_function<value_type, value_type, bool>
00106 {
00107 friend class map<_Key,_Tp,_Compare,_Alloc>;
00108 protected:
00109 _Compare comp;
00110
00111 value_compare(_Compare __c)
00112 : comp(__c) { }
00113
00114 public:
00115 bool operator()(const value_type& __x, const value_type& __y) const
00116 { return comp(__x.first, __y.first); }
00117 };
00118
00119 private:
00121 typedef _Rb_tree<key_type, value_type,
00122 _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
00124 _Rep_type _M_t;
00125
00126 public:
00127
00128
00129 typedef typename _Alloc::pointer pointer;
00130 typedef typename _Alloc::const_pointer const_pointer;
00131 typedef typename _Alloc::reference reference;
00132 typedef typename _Alloc::const_reference const_reference;
00133 typedef typename _Rep_type::allocator_type allocator_type;
00134 typedef typename _Rep_type::iterator iterator;
00135 typedef typename _Rep_type::const_iterator const_iterator;
00136 typedef typename _Rep_type::size_type size_type;
00137 typedef typename _Rep_type::difference_type difference_type;
00138 typedef typename _Rep_type::reverse_iterator reverse_iterator;
00139 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
00140
00141
00142
00143
00147 map()
00148 : _M_t(_Compare(), allocator_type()) { }
00149
00150
00154 explicit
00155 map(const _Compare& __comp, const allocator_type& __a = allocator_type())
00156 : _M_t(__comp, __a) { }
00157
00165 map(const map& __x)
00166 : _M_t(__x._M_t) { }
00167
00177 template <typename _InputIterator>
00178 map(_InputIterator __first, _InputIterator __last)
00179 : _M_t(_Compare(), allocator_type())
00180 { _M_t.insert_unique(__first, __last); }
00181
00193 template <typename _InputIterator>
00194 map(_InputIterator __first, _InputIterator __last,
00195 const _Compare& __comp, const allocator_type& __a = allocator_type())
00196 : _M_t(__comp, __a)
00197 { _M_t.insert_unique(__first, __last); }
00198
00199
00200
00201
00215 map&
00216 operator=(const map& __x)
00217 {
00218 _M_t = __x._M_t;
00219 return *this;
00220 }
00221
00223 allocator_type
00224 get_allocator() const
00225 { return _M_t.get_allocator(); }
00226
00227
00233 iterator
00234 begin()
00235 { return _M_t.begin(); }
00236
00242 const_iterator
00243 begin() const
00244 { return _M_t.begin(); }
00245
00250 iterator
00251 end()
00252 { return _M_t.end(); }
00253
00259 const_iterator
00260 end() const
00261 { return _M_t.end(); }
00262
00268 reverse_iterator
00269 rbegin()
00270 { return _M_t.rbegin(); }
00271
00277 const_reverse_iterator
00278 rbegin() const
00279 { return _M_t.rbegin(); }
00280
00286 reverse_iterator
00287 rend()
00288 { return _M_t.rend(); }
00289
00295 const_reverse_iterator
00296 rend() const
00297 { return _M_t.rend(); }
00298
00299
00303 bool
00304 empty() const
00305 { return _M_t.empty(); }
00306
00308 size_type
00309 size() const
00310 { return _M_t.size(); }
00311
00313 size_type
00314 max_size() const
00315 { return _M_t.max_size(); }
00316
00317
00330 mapped_type&
00331 operator[](const key_type& __k)
00332 {
00333
00334 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
00335
00336 iterator __i = lower_bound(__k);
00337
00338 if (__i == end() || key_comp()(__k, (*__i).first))
00339 __i = insert(__i, value_type(__k, mapped_type()));
00340 return (*__i).second;
00341 }
00342
00343
00358 pair<iterator,bool>
00359 insert(const value_type& __x)
00360 { return _M_t.insert_unique(__x); }
00361
00382 iterator
00383 insert(iterator position, const value_type& __x)
00384 { return _M_t.insert_unique(position, __x); }
00385
00394 template <typename _InputIterator>
00395 void
00396 insert(_InputIterator __first, _InputIterator __last)
00397 { _M_t.insert_unique(__first, __last); }
00398
00408 void
00409 erase(iterator __position)
00410 { _M_t.erase(__position); }
00411
00423 size_type
00424 erase(const key_type& __x)
00425 { return _M_t.erase(__x); }
00426
00438 void
00439 erase(iterator __first, iterator __last)
00440 { _M_t.erase(__first, __last); }
00441
00453 void
00454 swap(map& __x)
00455 { _M_t.swap(__x._M_t); }
00456
00463 void
00464 clear()
00465 { _M_t.clear(); }
00466
00467
00472 key_compare
00473 key_comp() const
00474 { return _M_t.key_comp(); }
00475
00480 value_compare
00481 value_comp() const
00482 { return value_compare(_M_t.key_comp()); }
00483
00484
00496 iterator
00497 find(const key_type& __x)
00498 { return _M_t.find(__x); }
00499
00511 const_iterator
00512 find(const key_type& __x) const
00513 { return _M_t.find(__x); }
00514
00523 size_type
00524 count(const key_type& __x) const
00525 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
00526
00538 iterator
00539 lower_bound(const key_type& __x)
00540 { return _M_t.lower_bound(__x); }
00541
00553 const_iterator
00554 lower_bound(const key_type& __x) const
00555 { return _M_t.lower_bound(__x); }
00556
00563 iterator
00564 upper_bound(const key_type& __x)
00565 { return _M_t.upper_bound(__x); }
00566
00573 const_iterator
00574 upper_bound(const key_type& __x) const
00575 { return _M_t.upper_bound(__x); }
00576
00592 pair<iterator,iterator>
00593 equal_range(const key_type& __x)
00594 { return _M_t.equal_range(__x); }
00595
00611 pair<const_iterator,const_iterator>
00612 equal_range(const key_type& __x) const
00613 { return _M_t.equal_range(__x); }
00614
00615 template <typename _K1, typename _T1, typename _C1, typename _A1>
00616 friend bool
00617 operator== (const map<_K1,_T1,_C1,_A1>&,
00618 const map<_K1,_T1,_C1,_A1>&);
00619
00620 template <typename _K1, typename _T1, typename _C1, typename _A1>
00621 friend bool
00622 operator< (const map<_K1,_T1,_C1,_A1>&,
00623 const map<_K1,_T1,_C1,_A1>&);
00624 };
00625
00636 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00637 inline bool
00638 operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x,
00639 const map<_Key,_Tp,_Compare,_Alloc>& __y)
00640 { return __x._M_t == __y._M_t; }
00641
00653 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00654 inline bool
00655 operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x,
00656 const map<_Key,_Tp,_Compare,_Alloc>& __y)
00657 { return __x._M_t < __y._M_t; }
00658
00660 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00661 inline bool
00662 operator!=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
00663 const map<_Key,_Tp,_Compare,_Alloc>& __y)
00664 { return !(__x == __y); }
00665
00667 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00668 inline bool
00669 operator>(const map<_Key,_Tp,_Compare,_Alloc>& __x,
00670 const map<_Key,_Tp,_Compare,_Alloc>& __y)
00671 { return __y < __x; }
00672
00674 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00675 inline bool
00676 operator<=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
00677 const map<_Key,_Tp,_Compare,_Alloc>& __y)
00678 { return !(__y < __x); }
00679
00681 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00682 inline bool
00683 operator>=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
00684 const map<_Key,_Tp,_Compare,_Alloc>& __y)
00685 { return !(__x < __y); }
00686
00688 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00689 inline void
00690 swap(map<_Key,_Tp,_Compare,_Alloc>& __x, map<_Key,_Tp,_Compare,_Alloc>& __y)
00691 { __x.swap(__y); }
00692 }
00693
00694 #endif