set、multiset集合

A set is a data structure that maintains a collection of elements. The basic operations of sets are element insertion, search and removal.The benefit of the set structure is that it maintains the order of the elements.
vector 如果要排序，需要 sort 一下； set 就会默认是有序的

  1. set<int> s;
  2. s.insert(3);
  3. s.insert(2);
  4. s.insert(5);
  5. cout << s.count(3) << "\n"; // 1
  6. cout << s.count(4) << "\n"; // 0
  7. s.erase(3);
  8. s.insert(4);
  9. cout << s.count(3) << "\n"; // 0
  10. cout << s.count(4) << "\n"; // 1
  1. set<int> s = {2,5,6,8};
  2. cout << s.size() << "\n"; // 4
  3. for (auto x : s) {        //C++11 用法
  4.     cout << x << "\n";
  5. }
  1. //set里面，每个元素只存一个
  2. set<int> s;
  3. s.insert(5);
  4. s.insert(5);
  5. s.insert(5);
  6. cout << s.count(5) << "\n"; // 1
  1. //multiset里面，每个元素可以存多个
  2. multiset<int> s;
  3. s.insert(5);
  4. s.insert(5);
  5. s.insert(5);
  6. cout << s.count(5) << "\n"; // 3
  1. //把5这个元素全删了
  2. s.erase(5);
  3. cout << s.count(5) << "\n"; // 0
  4. //只删掉一个5元素
  5. s.erase(s.find(5));
  6. cout << s.count(5) << "\n"; // 2
  1. printf("最小值 %d\n", *st.begin());
  2. printf("最大值 %d\n", *(--st.end()));
  3. printf("最大值 %d\n", *st.rbegin());
  5. set<int>::iterator it;
  7. // 第一个大于等于
  8. it = st.lower_bound(10);
  9. if (it != st.end()) cout << *it << '\n';
  11. // 第一个大于
  12. it = st.upper_bound(10);
  13. if (it != st.end()) cout << *it << '\n';
  15. // 最后一个小于
  16. it = st.lower_bound(10);
  17. if (it != st.begin()){
  18.     it--;
  19.     cout << *it << '\n';
  20. }
  22. // 注意不要访问不存在的东西，也不要删除不存在的东西

std::set::lower_bound 与 std::lower_bound的效率问题

  1. // 两者效率相差大的几乎是天壤之别。
  2. // 在CSP-J2021第二轮认证中，T4小熊的果篮
  3. // 这都是血泪史啊
  5. // 这样写就TLE，只能拿30pts
  6. it = upper_bound(st[p].begin(), st[p].end(), now);
  8. // 这样写就可以AC
  9. it = st[p].upper_bound(now);

image.png

image.png
image.png
我倒是觉得下面那个说的很有道理，应该是set<>::iterator不支持随机访问，所以直接当作普通的序列进行二分的时候就不是O(logn)的复杂度了。所以，一定要使用std::set::lower_bound。
https://blog.csdn.net/CZWin32768/article/details/51752267

std::set

https://www.cplusplus.com/reference/set/set/?kw=set
image.png