从set中删除数据. 可以通过值/迭代器来定位一个元素. 或者通过两个迭代器来指定一个区间. 需要注意的是对于multiset, erase一个值代表的是erase掉所有等于这个值的数据而不是只删除一个. 对于multiset若要删除一个元素只能选择传入迭代器.

9. std::set::count  $O(log(n))$

在set中查找传入的值并返回该值在set中的个数. 对于set来说可以判某值是否存在于set中.

10. std::set::find  $O(log(n))$

在set中查找传入的值病返回指向查找到的值的迭代器. 若未找到则返回该set的 end() 

11. std::set::lower_bound  $O(log(n))$

返回指向第一个不小于给定值的迭代器. 或者说指向第一个"可插入位置".

这里要记住不要用形如 std::lower_bound(s.begin(), s.end(), value); 来调用算法库里的相应函数. 因为迭代器移动需要 $O(log(n))$ 的时间复杂度, 而二分查找又要 $O(log(n))$ 的复杂度, 然而set的迭代器不是随机访问迭代器所以二分的时候变成了 $O(n)$ 的...然后你的复杂度就多乘了一大坨东西w目测搜索一次的时间复杂度是 $O(nlog^2(n))$  ...(还记得某学长胡策的时候就被这个坑了OwO欢声笑语中打出GG)

12. std::set::upper_bound  $O(log(n))$

返回指向第一个大于给定值的迭代器. 或者说指向最后一个"可插入位置".

注意事项同lower_bound

13. 六种大小比较运算符 != == > >= < <=  $O(n)$

按字典序比较两个set中的内容.

2.1.2.2 std::map

STL映射.必须指定的模板参数有两个: 下标的类型与数据的类型. 由于重载了 operator[] 所以在代码字面上可以当做一个下标不连续/下标可以是任何可比较类型数组来使用(下标是 std::string 都没人管你), 有时用于离散化.

内部实现是 std::pair 加上一个平衡树. 下标为第一关键字, 值为第二关键字扔在平衡树里. 因为底层元素是pair用迭代器查值时要用形如 *it.first  it->first 这样的语句获取该结点对应的下标,  *it.second  it->second 来获取该结点存储的值.

1. std::map::operator[]  $O(log(n))$

按下标访问map中的元素. 若该下标不存在则自动新建结点保存数据, 若存在则返回对对应数据的引用供读取/修改.

2. std::map::begin  $O(1)$

标准容器函数(雾) 返回指向首元素的迭代器

3. std::map::end  $O(1)$

返回指向尾元素下一位置的迭代器

4. std::map::rbegin  $O(1)$

返回指向翻转后区间的首元素(即原区间的尾元素) 的迭代器

5. std::map::empty  $O(1)$

返回容器是否为空.

6. std::map::size  $O(1)$

返回容器中元素的个数.

7. std::map::clear  $O(n)$

清空map中的所有数据.

8. std::map::insert  插入一个值为$O(log(n))$, 传入位置参考迭代器且位置参考有效则为均摊 $O(1)$ , 插入区间为 $O(dis*log(dis+n))$ (dis为区间长度)

插入一个值. 这个值为下标, 整个insert的意义可以解释为"为参数所提供的下标分配映射所需空间". 支持单点/区间.

9. std::map::erase  删除指定值为$O(log(n))$ , 删除指定迭代器指向的结点为均摊 $O(1)$ , 删除区间为 $O(log(n)+dis)$ (dis为区间长度)

删除一个值与它对应的映射值. 可以删除单点/区间.

10. std::map::count  $O(log(n))$

11. std::map::find  $O(log(n))$

12.六种大小比较运算符  != == > >= < <=  $O(n)$

2.1.3 无序关联容器

包括 std::unordered_set  std::unordered_map  std::unordered_multiset  std::unordered_multimap 四个, 具体用法和与之对应的关联容器基本相同. 内部基于Hash来进行元素查找, 均摊时间复杂度 $O(1)$ , 最坏时间复杂度 $O(n)$ , C++11起可用. C++11前G++的STL实现了 std::hash_set  std::hash_map 这样的非标准规定的容器, 当数据随机时可以用这些来将查找优化到均摊 $O(1)$ (但愿不会有丧病出题人专卡STL的Hash算法吧qwq)

2.1.4 容器适配器