C++ 常数代码技巧
brealid
2018-07-31 09:52:03
# C++ 代码小技巧(一)
在写代码的时候，我们常常会用一些小技巧，下面做简单介绍
## 一、o1+o2+o3（常数优化）
如题，开优化开关。
洛谷上有O2优化选项，当然，你也可以这样：在代码开头这样加一句：
``` cpp
#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
```
（逃~
Tips：此方法对STL非常有效！（NOIP赛场上不要用，不然会禁赛 3 年）
## 二、 ``inline`` 关键字（常数优化）
可以在一个函数的最开始加上inline，如：
```
inline int max(int a, int b)
{
if (a < b)
return b;
return a;
}
```
意义：inline可以跳过调用，直接引用，类似与直接将函数中的代码拿到当前函数中一样，如：
```pas
inline int max(int a, int b) _
{ \
if (a < b) |
return b; }----------.
return a; | |
} _/ |
|
int main() | 编译时
{ | 直接包
int a, b, c; | 含进去，
cin >> a >> b >> c; | 加快程
cout << max(a, b) << endl; <----------| 序运行
| 速度。
cout << max(a, c) << endl; <----------|
|
cout << max(b, c) << endl; <----------/
return 0;
}
```
使用贴士：
1. 不要试图给递归函数加``inline``，这样并没什么卵用！
2. 不要试图给调用多次且代码量很大（即较复杂） 的非递归函数加``inline``， 这样并不会优化！
3. 本方法应该给调用多次或复杂度较低的函数使用（如：min, max, fast_IO相关函数）。
## 三、``register`` 关键字（常数优化）
可以在一个变量声明的类型前面加上这个关键字。例：
```
// example #1:
register int a;
// example #2:
register long long b[107];
// example #3:
struct node1 {
int rank;
int num;
};
register node1 c;
// example #4:
register struct node2 {
int a, b;
int c;
} d;
```
原理：我们运行的程序会放在内存里，所以访问速度还是较慢，所以我们可以将常用的变量放在离CPU更近的寄存器里（即register）。不过这些操作编译器可能已经帮我们自动做了，再有开启编译优化的时候这招并不明显。
使用小贴士：
1. 用``register``的变量只能在函数里声明！！！（这也很好理解）
2. 如上面 ``example #4``，register可以写在``struct``开头。
3. ~~因为寄存器空间有限，所以请只给反复使用的变量加``register``。（e.g.循环变量``i, j, k``）~~ 被批判了，这条保留
## 四、template + typename模板
可以给一个函数声明成template + typename的形式。如：
```
// example:
template <typename _Tp>
_Tp max(_Tp a, _Tp b)
{
if (a > b)
return a;
return b;
}
// use:
int x, y;
cin >> x >> y;
cout << max(x, y) << endl;
cout << max<int>(x, y) << endl; //这两行等价
```
可以看到，声明这种函数的方法是在开头加上
```
template <typename 类型1, typename 类型2, ...> // 类型个数任意
```
注意：若一个typename（即类型）不是该函数的一个输入参数，则需用``<...>``的形式告诉函数这个typename的类型！
（这不是卡常优化用的，只是很有用）
## 五、fread大招
先给代码嘤嘤嘤
```
char BufferRead[1 << 15];
int rLen = 0, rPos = 0;
inline int Getchar(){
if (rPos == rLen) rPos = 0, rLen = fread(BufferRead, 1, 1 << 15, stdin);
if (rPos == rLen) return EOF;
return BufferRead[rPos++];
}
```
说明：
1. fread比getchar快，所以用fread优化程度更高
2. 若本地运行且不加freopen，那么会出错（无休止的读入）！（因为fread会读满``1 << 15``个字节，而从文件读入时会读到文件结束符从而停止读入，不会出问题）
3. 不知道``fread``可以通过[这篇文章](https://hkxa.blog.luogu.org/cpp-fread)简要了解一下
4. 来自 @[Av_alon_](https://www.luogu.org/space/show?uid=47374) 大佬的温馨提醒： 本地 ``fread``不用``freopen`` 时可以用 ``CTRL+Z`` 结束输入。。
## 六、快读整数（``fast_IO #1``）
代码还是很简单的，如下：
```
template <typename _TpInt>
inline _TpInt read()
{
register int flag = 1;
register char c = Getchar();
while ((c > '9' || c < '0') && c != '-')
c = Getchar();
if (c == '-') flag = -1, c = Getchar();
register _TpInt init = (c & 15);
while ((c = Getchar()) <= '9' && c >= '0')
init = (init << 3) + (init << 1) + (c & 15);
return init * flag;
}
```
几点说明：
1. 此方法的原理是：十进制，一位一位读入
2. ``flag`` 是负数标记
3. ``(c & 15)``：``'0'``的``ASCII``码是48，``(c & 15)``此处等于``(c % 16)``，所以本句``(c & 15)``的意义是``c-'0'``
4. ``(init << 3) + (init << 1) = (init * 8) + (init * 2) = (init * 10)``
5. ``typename``：可以读不同的类型
Tips：``'&'``和``'<<'``是位运算，关于位运算，可以上百度查资料
应用例子：
```
int a;
long long b;
short c;
a = read<int>();
b = read<long long>();
c = read<short>();
```
## 七、快读实数（``fast_IO #2``）
仿照整数快读，写出实数快读：
```
template <typename _TpRealnumber>
inline double readr()
{
register int flag = 1;
register char c = Getchar();
while ((c > '9' || c < '0') && c != '-')
c = Getchar();
if (c == '-') flag = -1, c = Getchar();
register _TpRealnumber init = (c & 15);
while ((c = Getchar()) <= '9' && c >= '0')
init = init * 10 + (c & 15);
if (c != '.') return init * flag;
register _TpRealnumber l = 0.1;
while ((c = Getchar()) <= '9' && c >= '0')
init = init + (c & 15) * l, l *= 0.1;
return init * flag;
}
```
没什么好说明的。
应用例子：
```
float d;
double e;
d = readr<float>();
e = readr<double>();
```
## 八、快写整数（``fast_IO #3``）
使用递归执行。
```
template <typename _TpInt>
void write(_TpInt x)
{
if (x < 0) {
putchar('-');
write<_TpInt>(~x + 1);
}
else {
if (x > 9) write<_TpInt>(x / 10);
putchar(x % 10 + '0');
}
}
```
说明：
1. ``(~x+1) = -x``，此处是为了``unsigned``型整数而写此句
2. 若去掉 ``if (x > 9)``，则会死循环
3. 本函数不可用于输出某种有符号类型的最小数！会无限输出负号！！！e.g.
- ``write<int>(-2147483648);``
- ``write<short>(-65536);``
- ``etc...``
应用例子：
```
write<int>(1);
printf("\n");
write<short>(-891);
printf("\n");
write<int>(-2147483647);
printf("\n");
long long n = 6;
write<long long>(n);
printf("\n");
```
## 九、循环展开
有dalao补充，将一些循环展开，可以常数优化。
```
for(int i=1;i<=20;i++)
a[i]=1;
```
可以改成
```
for(int i=1;i<=20;i+=4)
a[i]=1;
a[i+1]=1;
a[i+2]=1;
a[i+3]=1;
```
## 尾声：给个模板吧
```
// luogu-judger-enable-o2
/*
Problem: C++ 代码模板
Author: 航空信奥
Date: 2018/08/02
*/
#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <vector>
#include <map>
#include <set>
#define lowbit(a) ((a) & (~a + 1)) // define 快
using namespace std;
namespace AuthorName { // 防重名
inline char Getchar();
template <typename _TpInt> inline _TpInt read();
template <typename _TpRealnumber> inline double readr();
template <typename _TpInt> void write(_TpInt x);
template <typename _TpSwap> inline void swap(_TpSwap &x, _TpSwap &y);
int main()
{
// here : DO SOMETHING
return 0;
}
char BufferRead[1 << 15];
int rLen = 0, rPos = 0;
inline char Getchar()
{
if (rPos == rLen) rPos = 0, rLen = fread(BufferRead, 1, 1 << 15, stdin);
if (rPos == rLen) return EOF;
return BufferRead[rPos++];
}
template <typename _TpInt>
inline _TpInt read()
{
register int flag = 1;
register char c = Getchar();
while ((c > '9' || c < '0') && c != '-')
c = Getchar();
if (c == '-') flag = -1, c = Getchar();
register _TpInt init = (c & 15);
while ((c = Getchar()) <= '9' && c >= '0')
init = (init << 3) + (init << 1) + (c & 15);
return init * flag;
}
template <typename _TpRealnumber>
inline double readr()
{
register int flag = 1;
register char c = Getchar();
while ((c > '9' || c < '0') && c != '-')
c = Getchar();
if (c == '-') flag = -1, c = Getchar();
register _TpRealnumber init = (c & 15);
while ((c = Getchar()) <= '9' && c >= '0')
init = init * 10 + (c & 15);
if (c != '.') return init * flag;
register _TpRealnumber l = 0.1;
while ((c = Getchar()) <= '9' && c >= '0')
init = init + (c & 15) * l, l *= 0.1;
return init * flag;
}
template <typename _TpInt>
void write(_TpInt x)
{
if (x < 0) {
putchar('-');
write<_TpInt>(~x + 1);
}
else {
if (x > 9) write<_TpInt>(x / 10);
putchar(x % 10 + '0');
}
}
template <typename _TpSwap>
inline void swap(_TpSwap &x, _TpSwap &y)
{
_TpSwap t = x;
x = y;
y = t;
}
}
int main()
{
AuthorName::main();
return 0;
}
```