[TOC] # set Set的特性是所有元素都會根據元素的鍵值自動被排序。Set的元素不像map那樣可以同時擁有實值和鍵值，set的元素即是鍵值又是實值。Set不允許兩個元素有相同的鍵值。 我們可以通過set的迭代器改變set元素的值嗎？不行，因為set元素值就是其鍵值，關系到set元素的排序規則。如果任意改變set元素值，會嚴重破壞set組織。換句話說，set的iterator是一種const\_iterator. set擁有和list某些相同的性質，當對容器中的元素進行插入操作或者刪除操作的時候，操作之前所有的迭代器，在操作完成之后依然有效，被刪除的那個元素的迭代器必然是一個例外。 # multiset multiset特性及用法和set完全相同，唯一的差別在于它允許鍵值重復。 set和multiset的底層實現是紅黑樹，紅黑樹為平衡二叉樹的一種。 # 常用api ## 構造函數 ~~~ set<T> st;//set默認構造函數： mulitset<T> mst; //multiset默認構造函數: set(const set &st);//拷貝構造函數 ~~~ ## 賦值操作 ~~~ set&operator=(const set &st);//重載等號操作符 swap(st);//交換兩個集合容器 ~~~ ## 大小操作 ~~~ size();//返回容器中元素的數目 empty();//判斷容器是否為空 ~~~ ## 插入和刪除操作 ~~~ insert(elem);//在容器中插入元素。 clear();//清除所有元素 erase(pos);//刪除pos迭代器所指的元素，返回下一個元素的迭代器。 erase(beg, end);//刪除區間[beg,end)的所有元素 ，返回下一個元素的迭代器。 erase(elem);//刪除容器中值為elem的元素。 ~~~ ~~~ #include <set> //multset也是這個頭文件 void printSet(set<int> &s) { for (set<int>::iterator it = s.begin(); it != s.end(); ++it) { cout << *it << " "; } cout << endl; } void test02() { set<int> s; s.insert(4); s.insert(8); s.insert(9); s.insert(10); s.insert(11); printSet(s); } ~~~ ## 自定義排序 ~~~ //定義個排序規則 struct myfunc { bool operator()(int v1,int v2) { return v1 > v2; } }; void printSet2(set<int, myfunc> &s) { for (set<int, myfunc>::iterator it = s.begin(); it != s.end(); ++it) { cout << *it << " "; } cout << endl; } //改變set容器的規則，變為降序（從大到小） void test02() { set<int, myfunc> s; s.insert(4); s.insert(8); s.insert(2); s.insert(10); s.insert(7); printSet2(s); } ~~~ ~~~ void print(int v) { cout << v << " "; } //不能通過算法排序 void test04() { multiset<int> s; s.insert(4); s.insert(8); s.insert(2); s.insert(2); s.insert(7); //自身規則進行排序，從小到大 //不能通過算法排序來排序關聯式容器的元素 //sort(s.begin(), s.end()); for_each(s.begin(), s.end(), print); cout << endl; } ~~~ ## 判斷是否插入成功 ~~~ pair<set<int,myfunc>::iterator, bool> ret=s.insert(11); if (ret.second) { cout << "插入成功" << endl; } else { cout << "插入失敗" << endl; } ~~~ ## 查找 ~~~ find(key);//查找鍵key是否存在,若存在，返回該鍵的元素的迭代器；若不存在，返回set.end(); 1. count(key);//查找鍵key的元素個數 2. lower_bound(keyElem);//返回第一個key>=keyElem元素的迭代器。 3. upper_bound(keyElem);//返回第一個key>keyElem元素的迭代器。 equal_range(keyElem);//返回容器中key與keyElem相等的上下限的兩個迭代器。 ~~~ ~~~ set<int> s; s.insert(4); s.insert(8); s.insert(6); s.insert(9); s.insert(7); set<int>::iterator it=s.find(10); if (it == s.end()) { cout << "查找失敗" << endl; } else { cout << "查找成功：" << *it << endl; } //查找大于等于2的最小的數 it = s.lower_bound(2); if (it == s.end()) { cout << "查找失敗" << endl; } else { cout << "查找成功：" << *it << endl; } //查找大于2的最小的數 it = s.upper_bound(2); if (it == s.end()) { cout << "查找失敗" << endl; } else { cout << "查找成功：" << *it << endl; } //返回大于等于2的兩個最小的數，如果有2那么就返回2和大于2的最小數 pair<set<int>::iterator,set<int>::iterator> ret=s.equal_range(2); cout << *(ret.first) << endl; cout << *(ret.second) << endl; multiset<int> s1; s1.insert(4); s1.insert(4); s1.insert(4); s1.insert(9); s1.insert(7); cout << s1.count(4) << endl; ~~~ ## 存儲對象 ~~~ //存儲對象時，需要告訴set容器規則 class Maker { public: Maker(string name,int age) { this->name = name; this->age = age; } public: string name; int age; }; struct Makerfunc { bool operator()(const Maker &m1,const Maker &m2) { return m1.age > m2.age; } }; void test06() { set<Maker, Makerfunc> s; s.insert(Maker("aaa", 18)); s.insert(Maker("bbb", 19)); s.insert(Maker("ccc", 20)); s.insert(Maker("ddd", 21)); s.insert(Maker("eee", 22)); for (set<Maker, Makerfunc>::iterator it = s.begin(); it != s.end(); ++it) { cout << "Name:" << it->name << " Age:" << it->age << endl; } } ~~~