ThinkSSL🔒 一键申购 5分钟快速签发 30天无理由退款 购买更放心 广告
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。