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/functexcept.h>
00065 #include <bits/concept_check.h>
00066
00067 namespace _GLIBCXX_STD
00068 {
00090 template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
00091 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
00092 class map
00093 {
00094 public:
00095 typedef _Key key_type;
00096 typedef _Tp mapped_type;
00097 typedef std::pair<const _Key, _Tp> value_type;
00098 typedef _Compare key_compare;
00099 typedef _Alloc allocator_type;
00100
00101 private:
00102
00103 typedef typename _Alloc::value_type _Alloc_value_type;
00104 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00105 __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
00106 _BinaryFunctionConcept)
00107 __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
00108
00109 public:
00110 class value_compare
00111 : public std::binary_function<value_type, value_type, bool>
00112 {
00113 friend class map<_Key, _Tp, _Compare, _Alloc>;
00114 protected:
00115 _Compare comp;
00116
00117 value_compare(_Compare __c)
00118 : comp(__c) { }
00119
00120 public:
00121 bool operator()(const value_type& __x, const value_type& __y) const
00122 { return comp(__x.first, __y.first); }
00123 };
00124
00125 private:
00127 typedef typename _Alloc::template rebind<value_type>::other
00128 _Pair_alloc_type;
00129
00130 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
00131 key_compare, _Pair_alloc_type> _Rep_type;
00132
00134 _Rep_type _M_t;
00135
00136 public:
00137
00138
00139 typedef typename _Pair_alloc_type::pointer pointer;
00140 typedef typename _Pair_alloc_type::const_pointer const_pointer;
00141 typedef typename _Pair_alloc_type::reference reference;
00142 typedef typename _Pair_alloc_type::const_reference const_reference;
00143 typedef typename _Rep_type::iterator iterator;
00144 typedef typename _Rep_type::const_iterator const_iterator;
00145 typedef typename _Rep_type::size_type size_type;
00146 typedef typename _Rep_type::difference_type difference_type;
00147 typedef typename _Rep_type::reverse_iterator reverse_iterator;
00148 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
00149
00150
00151
00152
00156 map()
00157 : _M_t(_Compare(), allocator_type()) { }
00158
00159
00163 explicit
00164 map(const _Compare& __comp, const allocator_type& __a = allocator_type())
00165 : _M_t(__comp, __a) { }
00166
00174 map(const map& __x)
00175 : _M_t(__x._M_t) { }
00176
00186 template <typename _InputIterator>
00187 map(_InputIterator __first, _InputIterator __last)
00188 : _M_t(_Compare(), allocator_type())
00189 { _M_t.insert_unique(__first, __last); }
00190
00202 template <typename _InputIterator>
00203 map(_InputIterator __first, _InputIterator __last,
00204 const _Compare& __comp, const allocator_type& __a = allocator_type())
00205 : _M_t(__comp, __a)
00206 { _M_t.insert_unique(__first, __last); }
00207
00208
00209
00210
00224 map&
00225 operator=(const map& __x)
00226 {
00227 _M_t = __x._M_t;
00228 return *this;
00229 }
00230
00232 allocator_type
00233 get_allocator() const
00234 { return _M_t.get_allocator(); }
00235
00236
00242 iterator
00243 begin()
00244 { return _M_t.begin(); }
00245
00251 const_iterator
00252 begin() const
00253 { return _M_t.begin(); }
00254
00259 iterator
00260 end()
00261 { return _M_t.end(); }
00262
00268 const_iterator
00269 end() const
00270 { return _M_t.end(); }
00271
00277 reverse_iterator
00278 rbegin()
00279 { return _M_t.rbegin(); }
00280
00286 const_reverse_iterator
00287 rbegin() const
00288 { return _M_t.rbegin(); }
00289
00295 reverse_iterator
00296 rend()
00297 { return _M_t.rend(); }
00298
00304 const_reverse_iterator
00305 rend() const
00306 { return _M_t.rend(); }
00307
00308
00312 bool
00313 empty() const
00314 { return _M_t.empty(); }
00315
00317 size_type
00318 size() const
00319 { return _M_t.size(); }
00320
00322 size_type
00323 max_size() const
00324 { return _M_t.max_size(); }
00325
00326
00339 mapped_type&
00340 operator[](const key_type& __k)
00341 {
00342
00343 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
00344
00345 iterator __i = lower_bound(__k);
00346
00347 if (__i == end() || key_comp()(__k, (*__i).first))
00348 __i = insert(__i, value_type(__k, mapped_type()));
00349 return (*__i).second;
00350 }
00351
00352
00353
00361 mapped_type&
00362 at(const key_type& __k)
00363 {
00364 iterator __i = lower_bound(__k);
00365 if (__i == end() || key_comp()(__k, (*__i).first))
00366 __throw_out_of_range(__N("map::at"));
00367 return (*__i).second;
00368 }
00369
00370 const mapped_type&
00371 at(const key_type& __k) const
00372 {
00373 const_iterator __i = lower_bound(__k);
00374 if (__i == end() || key_comp()(__k, (*__i).first))
00375 __throw_out_of_range(__N("map::at"));
00376 return (*__i).second;
00377 }
00378
00379
00394 std::pair<iterator,bool>
00395 insert(const value_type& __x)
00396 { return _M_t.insert_unique(__x); }
00397
00418 iterator
00419 insert(iterator position, const value_type& __x)
00420 { return _M_t.insert_unique(position, __x); }
00421
00430 template <typename _InputIterator>
00431 void
00432 insert(_InputIterator __first, _InputIterator __last)
00433 { _M_t.insert_unique(__first, __last); }
00434
00444 void
00445 erase(iterator __position)
00446 { _M_t.erase(__position); }
00447
00459 size_type
00460 erase(const key_type& __x)
00461 { return _M_t.erase(__x); }
00462
00474 void
00475 erase(iterator __first, iterator __last)
00476 { _M_t.erase(__first, __last); }
00477
00489 void
00490 swap(map& __x)
00491 { _M_t.swap(__x._M_t); }
00492
00499 void
00500 clear()
00501 { _M_t.clear(); }
00502
00503
00508 key_compare
00509 key_comp() const
00510 { return _M_t.key_comp(); }
00511
00516 value_compare
00517 value_comp() const
00518 { return value_compare(_M_t.key_comp()); }
00519
00520
00532 iterator
00533 find(const key_type& __x)
00534 { return _M_t.find(__x); }
00535
00547 const_iterator
00548 find(const key_type& __x) const
00549 { return _M_t.find(__x); }
00550
00559 size_type
00560 count(const key_type& __x) const
00561 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
00562
00574 iterator
00575 lower_bound(const key_type& __x)
00576 { return _M_t.lower_bound(__x); }
00577
00589 const_iterator
00590 lower_bound(const key_type& __x) const
00591 { return _M_t.lower_bound(__x); }
00592
00599 iterator
00600 upper_bound(const key_type& __x)
00601 { return _M_t.upper_bound(__x); }
00602
00609 const_iterator
00610 upper_bound(const key_type& __x) const
00611 { return _M_t.upper_bound(__x); }
00612
00628 std::pair<iterator, iterator>
00629 equal_range(const key_type& __x)
00630 { return _M_t.equal_range(__x); }
00631
00647 std::pair<const_iterator, const_iterator>
00648 equal_range(const key_type& __x) const
00649 { return _M_t.equal_range(__x); }
00650
00651 template <typename _K1, typename _T1, typename _C1, typename _A1>
00652 friend bool
00653 operator== (const map<_K1, _T1, _C1, _A1>&,
00654 const map<_K1, _T1, _C1, _A1>&);
00655
00656 template <typename _K1, typename _T1, typename _C1, typename _A1>
00657 friend bool
00658 operator< (const map<_K1, _T1, _C1, _A1>&,
00659 const map<_K1, _T1, _C1, _A1>&);
00660 };
00661
00672 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00673 inline bool
00674 operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x,
00675 const map<_Key, _Tp, _Compare, _Alloc>& __y)
00676 { return __x._M_t == __y._M_t; }
00677
00689 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00690 inline bool
00691 operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,
00692 const map<_Key, _Tp, _Compare, _Alloc>& __y)
00693 { return __x._M_t < __y._M_t; }
00694
00696 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00697 inline bool
00698 operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
00699 const map<_Key, _Tp, _Compare, _Alloc>& __y)
00700 { return !(__x == __y); }
00701
00703 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00704 inline bool
00705 operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x,
00706 const map<_Key, _Tp, _Compare, _Alloc>& __y)
00707 { return __y < __x; }
00708
00710 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00711 inline bool
00712 operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
00713 const map<_Key, _Tp, _Compare, _Alloc>& __y)
00714 { return !(__y < __x); }
00715
00717 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00718 inline bool
00719 operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
00720 const map<_Key, _Tp, _Compare, _Alloc>& __y)
00721 { return !(__x < __y); }
00722
00724 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
00725 inline void
00726 swap(map<_Key, _Tp, _Compare, _Alloc>& __x,
00727 map<_Key, _Tp, _Compare, _Alloc>& __y)
00728 { __x.swap(__y); }
00729 }
00730
00731 #endif