源码剖析：STL中关联式容器之set

前言

在了解了红黑树的思路以及实现源码后，本章将对关联式容器set进行讲解

了解容器set

容器set的特性主要是：所有元素都会根据元素的键值自动排序，且不允许两个元素有相同的值

而关于容器set的底层实现，主要是依靠了RB-tree，所以set的自动排序的效率很高，且对于set容器的操作来说，也只是转调用了RB-tree的操作。具体容器set的实现源码如下：

cpp

//set结构源码template<class Key, 3         class Compare = less<Key>,    //代表默认情况下使用自增排序         class Alloc =alloc>class set{public:    typedef Key key_type;            //键值类型    typedef Key value_type;          //值类型    typedef Compare key_compare;     //类的类型    typedef Compare value_compare;   //值的类型private:    typedef rb_tree<Key_type, value_type,                    identity<value_type> key_compare,    //identity类型参考下文                    Alloc> rep_type;    rep_type t;    //使用红黑树来实现setpublic:    //指针与常量指针    typedef typename rep_type::const_pointer pointer;        typedef typename rep_type::const_pointer const_pointer;    //引用与常量引用    typedef typename rep_type::const_reference reference;    typedef typename rep_type::const_reference const_reference;    //迭代器与常量迭代器    typedef typename rep_type::const_iterator iterator;    //此次表明set迭代器为const    typedef typename rep_type::const_iterator const_iterator;    //反向迭代器与常量反向迭代器    typedef typename rep_type::const_reverse_iterator const_iterator;    typedef typename rep_type::const_reverse_iterator const_reverse_iterator;    typedef typename rep_type::size_type size_type;                //容器大小类型    typedef typename rep_type::difference_type difference_type;    //迭代器间距离}

针对上述结构源码中提到的identity模板类的源码如下：

cpp

//identity模板类源码template <class T>struct identity : public unary_function<T, T>{    const T& operator()(const T& x) const{    //仿函数        return x;    }}

容器set的构造函数

了解了容器set的结构后，我们知道其set不能修改元素的值的主要原因在于迭代器类型被const关键字修饰，而对于容器set的构造函数的具体实现源码如下：

cpp

//set的构造函数set() : t(Compare()){}explicit set(const Compare& comp) : t(comp) {}tempalte<class InputIterator>set(InputIterator first, InputIterator last) : t(Compare()){    t.insert_unique(first, last);}template<class InoutIterator>set(InputIterator first, InputIterator lase, const Compare& comp) : t(comp){    t.insert_unique(first, last);}set(const set<Key, Compare, Alloc>& x) : t(x.t){}set<Key, Compare, Alloc>& operator=(const set<Key, Compare, Alloc>& x){    t = x.t;}

容器set的基本操作函数

关于容器set的操作函数，在本篇文章的开头已经表明set的操作函数大多数都是调用RB-tree的操作函数，具体实现代码如下：

cpp

//set基本操作函数源码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(); }reverse_iterator rbegin() const { return t.rbegin(); }reverse_iterator rend() const { return t.rend(); } iterator empty() const { return t.empty(); }size_type size() const { return t.szie(); } size_type max_size() const { return t.max_size(); }void swap(set<Key, Compare, Alloc>& x) { t.swap(x.t); }

容器set的插入操作函数

cpp

//set的插入操作函数typedef apir<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);}template<class InputIterator>void insert(InputIterator first, InputIterator last){    t.insert_unique(first, last);}

容器set的清除操作函数

cpp

//set清除操作函数void erase(iterator postion){    typedef typename rep_type::iterator rep_iterator;    t.erase((rep_iterator&)position);}size_type erase(const key_type& x){    return t.rease(x);}void erase(iterator first, iterator last){    typedef typename rep_type::iterator rep_iterator;    t.erase((rep_iterator&)first, (rep_iterator&)last);}void clear() { t.clear(); }

容器set的其他操作函数

cpp

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的重载运算符函数

cpp

//set重载运算符函数friend bool operator== _STL_NULL_TMPL_ARGS(const set&, const set&);friend bool operator< _STL_NULL_TMPL_ARGS(const set&, const set&);template<class Key, class Compare, class Alloc>inline bool operator==(const set<Key, Compare, Alloc>& x,                       const set<Key, Compare, Alloc>& y){    return x.t == y.t;}template<class Key, class Compare, class Alloc>inline bool operator<(const set<Key, Compare, Alloc>& x,                       const set<Key, Compare, Alloc>& y){    return x.t < y.t;}