集合
Set的特性是：所有的元素会根据键值自动被排序。Set的元素与map不同的是，它的实值就是键值，键值就是实值。
Set不允许有两个元素拥有相同的键值。
Set的元素值是不可以被改变的，它的迭代器是 const iterator
同时，Set拥有它自己的特殊相关算法。交集，联集，差集等等。
STL 的 Set以我们前面提到的红黑树作为底层容器。
其实现大致如下： (代码 + 注释 很详细)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 |
template <class Key, class Compare = less<Key>, class Alloc = alloc> class set{ public: //typedefs: typedef Key key_type; typedef Key value_type; //注意，以下 key_compare 与 value_compare 使用同一个比较函数 typedef Compare key_compare; typedef Compare value_compare; private: //以下的 identify 定义于 <stl_function.h> 参见第七章 //很明显这是一种仿函数的实现方法 /* * template <class T> * struct identify : public unary_function <T, T> { * const T& operator()(const T& x) const { return x; } * } */ typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type; rep_type t; //红黑树表现 Set public: typedef typename rep_type::const_pointer pointer; //注意这里是const_pointer typedef typename rep_type::const_pointer const_pointer; typedef typename rep_type::const_reference reference; //这里也是const_... typedef typename rep_type::const_reference const_reference; typedef typename rep_type::const_iterator iterator; //注意！全是const //着重注意上面，iterator定义的是 RBTree 的 const_iterator //这表示Set的迭代器无法进行写入操作。 //因为Set元素有一定的次序安排，不允许用户在任意处进行写入操作 typedef typename rep_type::const_iterator const_iterator; typedef typename rep_type::const_reverse_iterator reverse_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; //allocation / deallocation //注意，Set使用的是RB-Tree的insert_unique() //MultiSet才使用 insert_equal() //主要还是相同键值的问题 set() : t(Compare()){} explicit set(const Compare& comp) : t(comp) {} template <class InputIterator> set(InputIterator first, InputIterator last) : t(Compare()) { t.insert_unique(first, last); } template <class InputIterator> set(InputIterator first, InputIterator last, 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; return *this; } //以下所有Set的操作，RBTree都已经提供了，所以只用传递调用就行了 //Accessors: 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(); } bool empty() const { return t.empty(); } size_type size() const { return t.size(); } size_type max_size() const { return t.max_size(); } void swap(set<Key, Compare, Alloc>& x) { t.swap(x.t); } //Insert Erase 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); } template <class InputIterator> void insert(InputIterator first, InputIterator last) { t.insert_unique(first, last); } void erase(iterator position) { typedef typename rep_type::iterator rep_iterator; t.erase((rep_iterator&)position); } size_type erase(const key_type& x) { return t.erase(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 operations 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); } 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; } |
以上是全部实现，我敲了一遍就懂了。
以下是一个小的测试程序 ~随意：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <set> #include <iostream> #include <algorithm> using namespace std; int main() { int i; int ia[5] = {0,1,2,3,4}; set<int> iset(ia, ia+5); //Size = 5 cout << "Size = " << iset.size() << endl; //3-Count = 1 cout << "3-Count = " << iset.count(3) << endl; iset.insert(3); //Size = 5 cout << "Size = " << iset.size() << endl; //3-Count =1 cout << "3-Count = " << iset.count(3) << endl; iset.insert(5); //Size = 6 cout << "Size = " << iset.size() << endl; //3-Count = 1 cout << "3-Count = " << iset.count(3) << endl; iset.erase(1); //Size = 5 cout << "Size = " << iset.size() << endl; //3-Count = 1 cout << "3-Count = " << iset.count(3) << endl; //1-Count = 0 cout << "1-Count = " << iset.count(1) << endl; set<int>::iterator ite1 = iset.begin(); set<int>::iterator ite2 = iset.end(); //0 2 3 4 5 for( ; ite1 != ite2; ++ite1) { cout << *ite1 << " "; } cout << endl; //使用STL的算法find()来搜寻是可以的，但是效率够好 ite1 = find(iset.begin(), iset.end(), 3); if(ite1 != iset.end()) cout << "3 found" << endl; ite1 = find(iset.begin(), iset.end(), 1); if(ite1 != iset.end()) cout << "1 found" << endl; //关联式容器，最好使用他们自己的find函数来搜索，这样效率更高 ite1 = iset.find(3); if(ite1 != iset.end()) cout << "3 found" << endl; ite1 = iset.find(1); if(ite1 != iset.end()) cout << "1 found" << endl; //改变元素的值，是不允许的... //*ite = 9; } |
【STL】Set