首页 > 代码库 > STL-Map 源码剖析

STL-Map 源码剖析

  1 G++ 2.91.57,cygnus\cygwin-b20\include\g++\stl_map.h 完整列表  2 /*  3  *  4  * Copyright (c) 1994  5  * Hewlett-Packard Company  6  *  7  * Permission to use, copy, modify, distribute and sell this software  8  * and its documentation for any purpose is hereby granted without fee,  9  * provided that the above copyright notice appear in all copies and 10  * that both that copyright notice and this permission notice appear 11  * in supporting documentation.  Hewlett-Packard Company makes no 12  * representations about the suitability of this software for any 13  * purpose.  It is provided "as is" without express or implied warranty. 14  * 15  * 16  * Copyright (c) 1996,1997 17  * Silicon Graphics Computer Systems, Inc. 18  * 19  * Permission to use, copy, modify, distribute and sell this software 20  * and its documentation for any purpose is hereby granted without fee, 21  * provided that the above copyright notice appear in all copies and 22  * that both that copyright notice and this permission notice appear 23  * in supporting documentation.  Silicon Graphics makes no 24  * representations about the suitability of this software for any 25  * purpose.  It is provided "as is" without express or implied warranty. 26  */ 27  28 /* NOTE: This is an internal header file, included by other STL headers. 29  *   You should not attempt to use it directly. 30  */ 31  32 #ifndef __SGI_STL_INTERNAL_MAP_H 33 #define __SGI_STL_INTERNAL_MAP_H 34  35 __STL_BEGIN_NAMESPACE 36  37 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 38 #pragma set woff 1174 39 #endif 40  41 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES 42 // 注意,以下Key 為鍵值(key)型別,T為資料(data)型別。 43 template <class Key, class T, class Compare = less<Key>, class Alloc = alloc> 44 #else 45 template <class Key, class T, class Compare, class Alloc = alloc> 46 #endif 47 class map { 48 public: 49  50 // typedefs: 51  52   typedef Key key_type;    // 鍵值型別 53   typedef T data_type;        // 資料(真值)型別 54   typedef T mapped_type;    //  55   typedef pair<const Key, T> value_type;    // 元素型別(鍵值/真值) 56   typedef Compare key_compare;    // 鍵值比較函式 57      58   // 以下定義一個 functor,其作用就是喚起 元素比較函式。 59   class value_compare 60     : public binary_function<value_type, value_type, bool> { 61   friend class map<Key, T, Compare, Alloc>; 62   protected : 63     Compare comp; 64     value_compare(Compare c) : comp(c) {} 65   public: 66     bool operator()(const value_type& x, const value_type& y) const { 67       return comp(x.first, y.first); 68     } 69   }; 70  71 private: 72   // 以下定義表述型別(representation type)。以map元素型別(一個pair) 73   // 的第一型別,做為RB-tree節點的鍵值型別。 74   typedef rb_tree<key_type, value_type,  75                   select1st<value_type>, key_compare, Alloc> rep_type; 76   rep_type t;  // 以紅黑樹(RB-tree)表現 map 77 public: 78   typedef typename rep_type::pointer pointer; 79   typedef typename rep_type::const_pointer const_pointer; 80   typedef typename rep_type::reference reference; 81   typedef typename rep_type::const_reference const_reference; 82   typedef typename rep_type::iterator iterator; 83   // 注意上一行,為什麼不像set一樣地將iterator 定義為 RB-tree 的 const_iterator? 84   // 按說map 的元素有一定次序安排,不允許使用者在任意處做寫入動作,因此 85   // 迭代器應該無法執行寫入動作才是。  86   typedef typename rep_type::const_iterator const_iterator; 87   typedef typename rep_type::reverse_iterator reverse_iterator; 88   typedef typename rep_type::const_reverse_iterator const_reverse_iterator; 89   typedef typename rep_type::size_type size_type; 90   typedef typename rep_type::difference_type difference_type; 91  92   // allocation/deallocation 93   // 注意, map 一定使用 insert_unique() 而不使用 insert_equal()。 94   // multimap 才使用 insert_equal()。 95  96   map() : t(Compare()) {} 97   explicit map(const Compare& comp) : t(comp) {} 98  99 #ifdef __STL_MEMBER_TEMPLATES100   template <class InputIterator>101   map(InputIterator first, InputIterator last)102     : t(Compare()) { t.insert_unique(first, last); }103 104   template <class InputIterator>105   map(InputIterator first, InputIterator last, const Compare& comp)106     : t(comp) { t.insert_unique(first, last); }107 #else108   map(const value_type* first, const value_type* last)109     : t(Compare()) { t.insert_unique(first, last); }110   map(const value_type* first, const value_type* last, const Compare& comp)111     : t(comp) { t.insert_unique(first, last); }112 113   map(const_iterator first, const_iterator last)114     : t(Compare()) { t.insert_unique(first, last); }115   map(const_iterator first, const_iterator last, const Compare& comp)116     : t(comp) { t.insert_unique(first, last); }117 #endif /* __STL_MEMBER_TEMPLATES */118 119   map(const map<Key, T, Compare, Alloc>& x) : t(x.t) {}120   map<Key, T, Compare, Alloc>& operator=(const map<Key, T, Compare, Alloc>& x)121   {122     t = x.t;123     return *this; 124   }125 126   // accessors:127   // 以下所有的 map操作行為,RB-tree 都已提供,所以map只要轉呼叫即可。128 129   key_compare key_comp() const { return t.key_comp(); }130   value_compare value_comp() const { return value_compare(t.key_comp()); }131   iterator begin() { return t.begin(); }132   const_iterator begin() const { return t.begin(); }133   iterator end() { return t.end(); }134   const_iterator end() const { return t.end(); }135   reverse_iterator rbegin() { return t.rbegin(); }136   const_reverse_iterator rbegin() const { return t.rbegin(); }137   reverse_iterator rend() { return t.rend(); }138   const_reverse_iterator rend() const { return t.rend(); }139   bool empty() const { return t.empty(); }140   size_type size() const { return t.size(); }141   size_type max_size() const { return t.max_size(); }142   // 注意以下 註標(subscript)運算子143   T& operator[](const key_type& k) {144     return (*((insert(value_type(k, T()))).first)).second;145   }146   void swap(map<Key, T, Compare, Alloc>& x) { t.swap(x.t); }147 148   // insert/erase149 150   // 注意以下 insert 動作傳回的型別151   pair<iterator,bool> insert(const value_type& x) { return t.insert_unique(x); }152   iterator insert(iterator position, const value_type& x) {153     return t.insert_unique(position, x);154   }155 #ifdef __STL_MEMBER_TEMPLATES156   template <class InputIterator>157   void insert(InputIterator first, InputIterator last) {158     t.insert_unique(first, last);159   }160 #else161   void insert(const value_type* first, const value_type* last) {162     t.insert_unique(first, last);163   }164   void insert(const_iterator first, const_iterator last) {165     t.insert_unique(first, last);166   }167 #endif /* __STL_MEMBER_TEMPLATES */168 169   void erase(iterator position) { t.erase(position); }170   size_type erase(const key_type& x) { return t.erase(x); }171   void erase(iterator first, iterator last) { t.erase(first, last); }172   void clear() { t.clear(); }173 174   // map operations:175 176   iterator find(const key_type& x) { return t.find(x); }177   const_iterator find(const key_type& x) const { return t.find(x); }178   size_type count(const key_type& x) const { return t.count(x); }179   iterator lower_bound(const key_type& x) {return t.lower_bound(x); }180   const_iterator lower_bound(const key_type& x) const {181     return t.lower_bound(x); 182   }183   iterator upper_bound(const key_type& x) {return t.upper_bound(x); }184   const_iterator upper_bound(const key_type& x) const {185     return t.upper_bound(x); 186   }187   188   pair<iterator,iterator> equal_range(const key_type& x) {189     return t.equal_range(x);190   }191   pair<const_iterator,const_iterator> equal_range(const key_type& x) const {192     return t.equal_range(x);193   }194   friend bool operator== __STL_NULL_TMPL_ARGS (const map&, const map&);195   friend bool operator< __STL_NULL_TMPL_ARGS (const map&, const map&);196 };197 198 template <class Key, class T, class Compare, class Alloc>199 inline bool operator==(const map<Key, T, Compare, Alloc>& x, 200                        const map<Key, T, Compare, Alloc>& y) {201   return x.t == y.t;202 }203 204 template <class Key, class T, class Compare, class Alloc>205 inline bool operator<(const map<Key, T, Compare, Alloc>& x, 206                       const map<Key, T, Compare, Alloc>& y) {207   return x.t < y.t;208 }209 210 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER211 212 template <class Key, class T, class Compare, class Alloc>213 inline void swap(map<Key, T, Compare, Alloc>& x, 214                  map<Key, T, Compare, Alloc>& y) {215   x.swap(y);216 }217 218 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */219 220 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)221 #pragma reset woff 1174222 #endif223 224 __STL_END_NAMESPACE225 226 #endif /* __SGI_STL_INTERNAL_MAP_H */227 228 // Local Variables:229 // mode:C++230 // End:

 

STL-Map 源码剖析