给你的程序提速:论C++中的那些坑

发布于 2018-08-15  269 次阅读


dalao勿喷,本文将给你的程序提速,避免踩坑。

前言

在开发一个小项目时,我有一个程序一直编译过不了,后来才发现和std里有一个函数冲突了。。QAQ,于是“感慨万千”写下此文。

常见的坑

namespace的坑

不要把bits/stdc++.h和using namespace std一块用

bit/stdc++.h 是万能头

using namespace std 是取消所有的std名称空间

std::cout -> cout

因为假设你写了一个函数和和std里的刚好冲突。。。。

for的坑

我们来看一段代码

int n;
scanf("%d", &n);
for(int i=1 ; i <= n/2 ; i++)
{
    //code
}

这段代码看上去无任何问题,它循环了n/2次,但它实际上同时计算了n遍n/2,数据大的话可能会TLE的。

我们不如这样写:

int n;
scanf("%d", &n);
for(int i=1,N=n/2 ; i <= N ; i++)
{
    //code
}

int n;
scanf("%d", &n);
int N=n/2;
for(int i=1; i <= N ; i++)
{
    //code
}

这样就能快好多了。

STL "> >"的坑(C++11已经修复,现在这个问题是旧NOIP时代的产物了)

我们定一个小根堆

priority_queue<int,vector<int>,greater<int>> q;

编译报错

 error: ‘>>’ should be ‘> >’ within a nested template argument list
 priority_queue<int,vector<int>,greater<int>> q;

错误:“嵌套模板参数列表”中的“>>”应该是“> >”

正确定义:

priority_queue<int,vector<int>,greater<int> > q;

多测一定要清空

一定不要忘初始化并查集

能循环展开一定要循环展开

运算符的优化

位运算永远是最快的,一次或许看不出来,但循环执行成百上千次呢

交换变量的值

“^”(异或运算符,位值相同为0,不同为1)

int x=2,y=1;
x ^= y;
y ^= x;
x ^= y;
cout<<x<<" "<<y;

运行结果

1 2

判断奇偶

”&“(按位与运算符,位值都为1为1,不为1时为0)

if(i&1) cout<<i<<"是奇数"<<endl;
else    cout<<i<<"是偶数"<<endl;

例如一个数 N,(N&1)的结果就是取二进制的最末位。
这可以用来判断一个整数的奇偶,
二进制的最末位为0表示该数为偶数,
最末位为1表示该数为奇数.
这是因为二进制数末位的权值为2的0次方等于1,
其他位置上则为2的非0整数次方,使其权值不会产生奇数

“<<”(左移运算符,把该数的二进制位左移n位)

下面的语句是等价的

n * 2

n << 1

左移一位相当于乘2

“>>”(右移运算符,把该数的二进制位右移n位)

下面的语句是等价的

n / 2

n >> 1

右移一位相当于除以2

register

正常的话,C++定义变量是吧变量放到内存中的,但是CPU中还有一个更快的地方叫寄存器,我们可以把经常的变量用register把变量放到寄存器中,别放太多了。

register int a = 1;

iostream优化

其实C++的stream为了和C保持一定兼容,做了不少努力,cin,cout慢并不是开倒车。

我们可以解除cin,cout与printf的绑定。

更离谱一点的话甚至还可以解除cin和cout的绑定(强制在线的题目不能用)

    ios::sync_with_stdio (false);
    cin.tie (0); //慎用
    cout.tie (0);  //慎用

写在最后

关于优化的就讲这么多了,有兴趣的童靴可以对二进制位做深入的研究,这里就不再多说了。