[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; } } ~~~