首页 > 代码库 > 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 源码剖析
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。