和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.