set/multiset

特性     set保证出现在set内的元素只出现一次，且按照字典序从小大到大排序

初始化

① 初始化一个集合

set<int> S;

② 复制一个集合

set <int > Ss(S); 求长度(时间复杂度为O(1)) set<int> s; s.size(); 判空(时间复杂度为O(1)) a.empty(); 清空 a.clear(); 删除元素/插入元素 a.erase(1); // 删除为1的那个值 ，时间复杂度为O(logn ) a.erase(a.begin()); // 删除set的第一个元素 a.erase(iterator::it1, iterator::it2); // 删除[it1, it2) a.insert(1); // 插入一个元素1 判断一个数是否出现过 a.count(x); // 判断x是否在集合中出现过，如果出现过返回1，否则0 迭代器 a.begin(); // 第一个元素的迭代器 a.end(); // 最后一个元素的下一位的迭代器 遍历 1.迭代器遍历 for (set<int> ::iterator it = S.begin(); it != S.end(); ++it) cout << *it ; 2. c++方式遍历 for (auto Si: S) cout << Si << ends; 查找（支持lower_bound() 和 upper_bound()操作） set<int> S; S.insert(1); S.insert(2); set <int> ::iterator it1 = S.lower_bound(2); if (it1 != S.end()) cout << *it1; else cout << 0; set <int> ::iterator it2 = S.find(2); S.erase(it2); multiset的性质和set一样，上面全是set的特性，而multiset在set的特性之上使得一个集合内可以出现多次同一个元素,multiset内的元素也是按照字典序排好序的 multiset <int> s; s.insert(1); s.insert(1); for (auto si: s) cout << si << ends;

输出

1 1

    在s.erase(int x)时，会删除所有出现的x，时间复杂度为O(logn + k) (k为出现次数)

multiset <int> s; s.insert(1); s.insert(1); s.erase(1); cout << s.empty();

输出

1