关联容器 — set
最后更新于：2022-04-01 19:54:17
set中的key就是value，value就是key，并且key是唯一的，利用红黑树有序地存储（红黑树在插入时自动调整）。正因为有序，所以无法通过迭代器随意修改key，否则顺序会打乱。set的底层容器就是rb_tree，有了tr_tree的基础，set的就很好理解了，很多的接口都只是转调用rb_tree的操作。
整体代码如下：
~~~
template , 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_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 pair_iterator_bool;
pair insert(const value_type& x) {
pair p = t.insert_unique(x);
return pair(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 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。
';