set中的key就是value，value就是key，并且key是唯一的，利用红黑树有序地存储（红黑树在插入时自动调整）。正因为有序，所以无法通过迭代器随意修改key，否则顺序会打乱。set的底层容器就是rb_tree，有了tr_tree的基础，set的就很好理解了，很多的接口都只是转调用rb_tree的操作。 整体代码如下： ~~~ template <class Key, class Compare = less<Key>, class Alloc = alloc> // 默认采用递增排序 class set { public: // typedefs: // set的key既是key_type也是value_type typedef Key key_type; typedef Key value_type; typedef Compare key_compare; typedef Compare value_compare; private: // 这里使用仿函数identity作为rb_tree的KeyOfValue类型实参 // identity直接将传入的参数返回 typedef rb_tree<key_type, value_type, // 注意，红黑树节点实际存储的是value_type，也就是key_type identity<value_type>, key_compare, Alloc> rep_type; rep_type t; // 底层容器——红黑树 public: .... typedef typename rep_type::const_iterator iterator; // const_iterator，迭代器无法写入 typedef typename rep_type::const_iterator const_iterator; .... set() : t(Compare()) {} explicit set(const Compare& comp) : t(comp) {} .... // 转调用rb_tree的接口 key_compare key_comp() const { return t.key_comp(); } value_compare value_comp() const { return t.key_comp(); } iterator begin() const { return t.begin(); } iterator end() const { return t.end(); } .... // 插入/删除 typedef pair<iterator, bool> pair_iterator_bool; pair<iterator,bool> insert(const value_type& x) { pair<typename rep_type::iterator, bool> p = t.insert_unique(x); return pair<iterator, bool>(p.first, p.second); } iterator insert(iterator position, const value_type& x) { typedef typename rep_type::iterator rep_iterator; return t.insert_unique((rep_iterator&)position, x); } .... // set相关操作 iterator find(const key_type& x) const { return t.find(x); } size_type count(const key_type& x) const { return t.count(x); } iterator lower_bound(const key_type& x) const { return t.lower_bound(x); } iterator upper_bound(const key_type& x) const { return t.upper_bound(x); } pair<iterator,iterator> equal_range(const key_type& x) const { return t.equal_range(x); } // set之间是可以比较的 friend bool operator== __STL_NULL_TMPL_ARGS (const set&, const set&); friend bool operator< __STL_NULL_TMPL_ARGS (const set&, const set&); }; ~~~ 有一点需要注意，使用STL的find算法来查找set中的元素是可以的，但此find是遍历整个容器进行比较，没有利用红黑树作为二叉查找树这一性质，所以导致效率不高，效率为O(N)。推荐的做法是使用关联容器内部的find()接口，利用二叉查找树进行遍历，效率为O(logN)。 参考： 《STL源码剖析》 P233。