【C++】用于ACM/OI等算法竞赛的读入优化

【C++】用于ACM/OI等算法竞赛的读入优化

【C++】用于ACM/OI等算法竞赛的读入优化缩略图

比较

正常情况下,cin/cout是最慢的输入输出方式,其速度远远小于scanf和printf。

那么,如何解决这个问题呢?

我们引入取消同步的操作
std::ios::sync_with_stdio(false);

这个函数是一个“是否兼容 stdio”的开关,C++ 为了兼容 C,保证程序在使用了 printf 和 std::cout 的时候不发生混乱,将输出流绑到了一起。

这其实是 C++ 为了兼容而采取的保守措施。我们可以在进行 IO 操作之前将 stdio 解除绑定,但是在这样做之后要注意不能同时使用 std::cin/std::cout 和 scanf/printf 。

更深一层的优化

其实,还有比scanf和printf更快的操作。

注意,本页面中介绍的读入和输出优化均针对整型数据,若要支持其他类型的数据(如浮点数),可自行按照本页面介绍的优化原理来编写代码。

原理

众所周知, getchar 是用来读入 1 byte 的数据并将其转换为 char 类型的函数,且速度很快,故可以用“读入字符——转换为整型”来代替缓慢的读入

每个整数由两部分组成——符号和数字

整数的 ‘+’ 通常是省略的,且不会对后面数字所代表的值产生影响,而 ‘-‘ 不可省略,因此要进行判定

10 进制整数中是不含空格或除 0~9 和正负号外的其他字符的,因此在读入不应存在于整数中的字符(通常为空格)时,就可以判定已经读入结束

C 和 C++ 语言分别在 ctype.h 和 cctype 头文件中,提供了函数 isdigit , 这个函数会检查传入的参数是否为十进制数字字符,是则返回 true ,否则返回 false 。对应的,在下面的代码中,可以使用 isdigit(ch) 代替 ch >= ‘0’ && ch <= ‘9’ ,而可以使用 !isdigit(ch) 代替 ch <‘0’ || ch> ‘9’

具体代码实现

int read()
{
	int f=1,c=0;
	char ch=getchar();
	while(ch<'0' or ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>'0' and ch<'9')
	{
		c=c*10+ch-'0';
		ch=getcahr();
	}
	return c*f;
 } 

发表评论