STL 小的知识点

STL

函数

• nth_element(a+l,a+k,a+(r-l));
  表示对a数组在（l-r）的左闭右开区间找出第k大的数（但其他位置的数是无序的，只是第k大的左边的数都比k位置的小，右边都大于它）

• __builtin_ffs(x)：返回x中最后一个为1的位是从后向前的第几位
  __builtin_popcount(x)：x中1的个数。
  __builtin_ctz(x)：x末尾0的个数。x=0时结果未定义。
  __builtin_clz(x)：x前导0的个数。x=0时结果未定义。
  __builtin_parity(x)：x中1的奇偶性。
  （复杂度均为 $o(1)$ ）

• lower_bound(返回数组中第一个大于等于key值的下标)

int x=lower_bound (a,a+n,key-(1e-8))-a;
//如果查的是浮点数应该key-(1e-8),减去一个很小的数防止精度丢失
//如果是整数就不用减

• upper_bound (返回数组中第一大于key值的下标)

各种容器

• set
  默认排序是从小到大，不允许有重复元素
• multiset
  与set不同在可以有重复元素
• priority_queue < int > q
  默认从大到小排序
• priority_queue < int , vector < int > ,greater< int >> q;
  优先队列从小到大排序