STL的几个中用的功能

发表于 更新于

I LOVE　STL(深度调教)

本文默认数组从1开始用

总录

mt19937

第一个先说随机数,这个东西很好用,常常用在对拍里来测试程序的稳定性……

优点

  • 速度比rand()快
  • 范围比rand()大 rand()在win下随机范围为0-32767而mt19937为-2147483646-2147483647

初始化方法也很简单std::mt19937 name(seed); name就是你随机函数的名字,种子自己选,多当前时间,调用时时候要加上()。eg:mt19937 duipai(time(0));

这里有一个示例 

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;
std::mt19937 duipai(time(0));
int main()
{
    while(1){
        printf("%d\n",duipai()%114514;)
    }
	return 0;
}

我对它的研究不深,想要限制数据范围最好的方法就是取模。如果你想更大的随机数(mt19937为+/-INT_MIN范围啊),你可以用mt19937_64

如果你想了解C++生成(伪)随机数的原理,可以看这里

如果你想把mt19937💘调教⚥⚢⚨⚣⚩⚦♀♁到极致,什么数据上下界,可以看这里

nth_element

第二个是和区间第k小的,定义在<algorithm>;

功能:在[l,r)区间第k小的放到第k位上

写法依然简单,eg:std::nth_element(arr+1,arr+k,arr+n+1);

  • arr+1: 起始位置
  • arr+k: 即为第k小
  • n: 从起始位置开始的元素个数

但是有几个细节要注意:

  • 它只保证k不保证其他的有序！！！
  • r是开区间,所以我们要对n加上个1!!! (毒瘤额)

这里有一个示例

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
int main() {
    int in[6]={0,5,4,3,2,1};
    std::nth_element(in+1,in+4,in+6);
    for(int i=1;i<=5;i++){
        printf("%d ",in[i]);
    }
    return 0;
}
//result: 3 1 2 4 5

其他的调教方案请看这里

vector

第三个是vector,这个相比大家又会的说,所以我不在赘述。

这里要说的是手打实现的(防止TLE,有时候我不需要动态内存(这个超慢的的说),只需要vector的添加修改功能, 手动记队尾不就出错率++可调试性--QwQ)

这里引用来自ymj的代码(我被喷了,别骂了我写不出STLQwQ)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename T, size_t N> struct c {
  T a[N];
  size_t endpos = 0;
  T *begin() { return a; }
  T *end() { return a + endpos; }
  void push_back(T &&val) {
    a[endpos] = val;
    endpos++;
  }
  T pop_back() {
    endpos--;
    return a[endpos];
  }
  bool empty(){return endpos==0;}
  size_t size(){return endpos;}
};

T

当然可以在里面加很多骚操作,比如说线段树,但是我不会啦QwQ,有事 @ymj

binary_search & lower_bound & upper_bound

以下都定义在<algorithm>库中

  binary_search

用法就跟名字一样二分搜索是否存在该值,返回bool。查询的值存在为1，反之为0。

优点(硬要说的话):

  • 手打可能回出错QwQ,STL很严谨

要注意的点:

  • 要保证元素有序

格式: std::binary_search(arr+1,arr+1+n,val)

  • arr+1:起始位置
  • n:从起始位置开始的元素个数
  • val: 要查找的值

这里有一个示例 

1
2
3
4
5
6
7
8
9
#include <algorithm>
#include <iostream>
int main() {
    int in[]={0,1,2,4,7,8,1314,91182};
    bool flag=std::binary_search(in+1,in+7,3);
    std::cout<<flag<<"\n";
    return 0;
}
// rusult: 0

   lower_bound

这个大家应该都不陌生,查找第一个大于等于某个元素的位置,返回下标地址(注意是地址指针)

优缺点同上

格式: std::lower_bound(arr+1,arr+n,val)-arr;

  • arr+1:起始位置
  • n:从起始位置开始的元素个数
  • val: 要查找的值

注意点:

  • 返回的是地址指针,(常用)所以需要减去数组首地址才是下标(如果你用下标话QwQ)

  upper_bound

(其实这个不是STL的,但是很中用)

查找第一个大于某个元素的位置,返回下标地址(注意是大于,不是大于等于)

优缺点同上,用法略同不在赘述……

  **__builtin_popcount**

这个能高效返回数的二进制下1的个数;

格式 : __builtin_popcount(x)

注意点:

  • 返回值是int如果想返回 unsigned long long 可以加上ll eg: __builtin_popcountll(x)

  stable_sort

对序列进行升序排序,但是是稳定排序

格式:std::stable_sort(arr,arr+n)

格式 同上;(以后无特殊说明皆为同上,偷懒);

参考

[ __builtin_popcount（） 函数]

推荐文章

[__builtin_popcount]

🍂未完待续……