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。