和set類似，也采用了rb_tree作為底層容器，但每個節點是一個pair對象，它關聯了鍵值和實值。鍵值不允許修改，但實值是可以修改的，等下的代碼也會有所說明。 下面是map的代碼框架： ~~~ template <class Key, class T, class Compare = less<Key>, class Alloc = alloc> // 默認采用遞增順序 class map { public: typedef Key key_type; // 鍵值類型 typedef T data_type; // 實值類型 typedef T mapped_type; typedef pair<const Key, T> value_type; // 注意const Key，表示無法修改鍵值 typedef Compare key_compare; .... private: // select1st抽取出value_type（pair）內的first元素 typedef rb_tree<key_type, value_type, // rb_tree的一個節點存儲一個pair select1st<value_type>, key_compare, Alloc> rep_type; rep_type t; // 底層容器——紅黑樹 public: .... typedef typename rep_type::iterator iterator; // 實值可以修改 .... map() : t(Compare()) {} explicit map(const Compare& comp) : t(comp) {} .... key_compare key_comp() const { return t.key_comp(); } value_compare value_comp() const { return value_compare(t.key_comp()); } iterator begin() { return t.begin(); } const_iterator begin() const { return t.begin(); } iterator end() { return t.end(); } .... // 下標操作，存在相同鍵值的節點則返回，否則插入再返回 // insert返回pair<iterator, bool>，iterator指向紅黑樹的某個節點 // 下標操作返回迭代器的第二個元素，即實值 T& operator[](const key_type& k) { return (*((insert(value_type(k, T()))).first)).second; } // 插入/刪除 pair<iterator,bool> insert(const value_type& x) { return t.insert_unique(x); } iterator insert(iterator position, const value_type& x) { return t.insert_unique(position, x); } .... // map相關操作 iterator find(const key_type& x) { return t.find(x); } size_type count(const key_type& x) const { return t.count(x); } iterator upper_bound(const key_type& x) {return t.upper_bound(x); } pair<iterator,iterator> equal_range(const key_type& x) { return t.equal_range(x); } friend bool operator== __STL_NULL_TMPL_ARGS (const map&, const map&); friend bool operator< __STL_NULL_TMPL_ARGS (const map&, const map&); }; ~~~ 參考： 《STL源碼剖析》 P237.