C++ 的 cin
cout
和 C 的 scanf
printf
等 IO 函数已经够我们是用了,但是它们很慢,尽管 cin
cout
可以取消同步以优化,但还是不够快.
所以我们需要找一种更快的方式来输入输出,以防在 OI 中出现 TLE 的情况,便有了快读快输.
代码快读 read quickly注:它们只能读取整数
(资料图片)
templateinline void rq(T& x) { x = 0; char c; bool sign = 0; while(!isdigit(c = getchar())) if(c == "-") sign = 1; do x = (x << 3) + (x << 1) + (c ^ 48); while(isdigit(c = getchar())); if(sign) x = -x; return;}
快写 write quicklytemplateinline void wq(const T& x) { T t = x; static char _wq_buffer[39]; int bp = -1; if(!t) { putchar("0"); return; } if(t < 0) putchar("-"), t = -t; while(t) { _wq_buffer[++bp] = t % 10 + "0"; t /= 10; } for(int i = bp; i >= 0; i--) putchar(_wq_buffer[i]); return;}
代码解释快读第一部分templateinline void rq(T& x)
template
是一个 C++ 的关键字,在这里它的作用是声明函数模板. 尖括号里的 class T
可以理解为声明一个类型 T
,这里的 class
也可以替换成 typename
,并无两样.
这个 T
是什么类型一般取决于这里的 x
是什么类型. 例如:
int x;rq(x); // T = intlong long y;rq(y); // T = long longchar z;rq(z); // T = char
inline
是 内联,在这里是 内联函数,加上它可能会让程序运行的速度变快,类似于宏展开,但它做出的优化取决于编译器和函数的复杂程度, 有兴趣的可以看这位大佬的博客.
void
在这里的意思是无返回类型函数.
T& x
在这里是 引用传参,在此函数内更改 x
对应传进来的参数也会更改,这里它和指针极为相似:
void swap1(int& a, int& b) { int t = a; a = b; b = t;}void swap2(int* a, int* b) { int t = *a; *a = *b; *b = t;}int main() { int x = 1, y = 2; swap1(x, y); // x = 2, y = 1 swap2(&x, &y); // x = 1, y = 2}
这两个的函数的功能都一样,在汇编层面也一样,只不过 swap1
比 swap2
的写法更简便,更像是 C++ 相对于 C 特有的语法糖.
x = 0;char c;bool sign = 0;
x = 0
,这里一般清零,因为传进来的 x
的值不确定,如果不是 \(0\) 会导致接下来的运算出错,从而导致读入无效. 如果可以保证传进来的 x
等于 \(0\) ,则可以省略这一行.
char c
,这个 c
是读入的字符,一般 IO 都是靠字符,然后再转化为数字等别的类型.
bool sign = 0
,这个 sign
表示 x 的符号,\(0\) 表示 \(x \geq 0\) ,\(1\) 表示 \(x < 0\) . 在这里必须清零,因为这是在函数内,如果不清零,它的值是不确定的,从而导致 x
的正负性受到影响. 如果可以保证读入的数是一个非负整数,则可以省略这一行以及相关的内容.
while(!isdigit(c = getchar())) if(c == "-") sign = 1;
此部分是跳过不是数字的时候并确定 x
的符号.
c = getchar()
是读入一个字符,getchar()
是一个较快的方法,比 cin >> c
和 scanf("%c", &c)
快.
!isdigit(...)
是判断该字符是否是一个非数字. 为什么不用 a < "0" || "9" < a
之类的?因为直接 !isdigit(...)
比这个快,isdigit
内部实现类似于打表,有兴趣的可以看这位大佬的博客.
if(c == "-") sign = 1;
显然是确定符号. 但是这种判断有个缺点,当输入:
ho-mo114514
时,sign = 1
,显然这是不正确的.
如果可以保证一开始读入的就是符号或是有效数字位,或已知输入的格式,则可以删除这个 while
循环并做出相应的更改. (我建议还是不要删,删了之后处理格式会很麻烦)
do x = (x << 3) + (x << 1) + (c ^ 48);while(isdigit(c = getchar()));
此部分是边读边更改 x
.
(x << 3) + (x << 1)
是 x * 10
.
x << 3
表示将 x
的二进制位左移三位,x << 1
同理.
什么是左移、右移?
假设
a
是一个 \(8\) 位的数,并且a = 4
,则a
在二进制下是00000100
.左移三位得00010000
,表示 \(32\) ,也就是 \(4 \times 2^3\)不难得出
a << b
\(=a \times 2^b \space (b \geq 0)\) ,a >> b
\(=a \div 2^b \space (b \geq 0)\) .
则上面的表达式等价于 \(x \times 2^3 + x \times 2^1 = x \times 8 + x \times 2 = x \times 10\) .
c ^ 48
是 c - "0"
,将一个数字字符化为数字.
其中 ^
表示异或,在数学中用 \(\bigoplus\) 表示,有基本的四种基本的运算法则:\(0 \bigoplus 0 = 0\) ,\(0 \bigoplus 1 = 1\) ,\(1 \bigoplus 0 = 1\) ,\(1 \bigoplus 1 = 0\). (同0异1)
\(48\) 在 ASCII 中对应的字符是 0
,二进制是 00110000
if(sign) x = -x;
此部分是添加 x
的符号. 有的可能把 -x
写成 ~(x - 1)
,这都表示取 x
的倒数,在汇编层面都一样,会被编译器优化.
templateinline void wq(const T& x)
此部分与快读的第一步分基本一样,只不过多了个 const
. const
在这里表示 x
在此函数内不可被更改,这样就可以写类似这样的代码 wq(1)
wq(a + b)
.
T t = x;static char _wq_buffer[39];int bp = -1;
因为 x
不可变,所以复制了一份给 t
,下面关于 x
的操作一律用 t
代替.
static
在这里表示静态的,相当于在全局定义 _wq_buffer
. 给 buffer
加 _wq_
这个前缀是为了避免和其他的关键字冲突. \(39\) 是 __uint128_t
的十进制下最大位数( \(2^{127} - 1 = 340282366920938463463374607431768211455\) \(39\) 位),如果需要的话可以开更多位.
bp
是 _wq_buffer
当前的有效位数的位置,这里初始值为 \(-1\) 是为了下面方便计算.
if(!t) { putchar("0"); return;}if(t < 0) putchar("-"), t = -t;
特判一些情况,但是直接 -t
的会导致像 \(-128\) \(-65536\) \(\cdots\) \(-2^{8 \times \text{sizeof(T)}}\) 这样的数会输出乱码.
while(t){ _wq_buffer[++bp] = t % 10 + "0"; t /= 10;}
每次取 t
的个位,然后转化为数字字符倒序存到 _wq_buffer
里,直到 t = 0
.
for(int i = bp; i >= 0; i--) putchar(_wq_buffer[i]);
输出,因为是倒序存,所以要倒着输出.
参考文献函数模板
pathenon. isdigit()极品实现.
恋喵大鲤鱼. C++ inline 函数简介