读入、输出优化的一般方法

· · 算法·理论

众所周知，C++ 的输入输出流 cin 和 cout 是十分缓慢的，那有什么方法可以优化呢？

1、取消与 stdio 的绑定（竞赛不可用）

C++ 中，cin 与 cout 默认是与 stdio 绑定的，这其实是 C++ 为了让你写代码写的舒服兼容性而采取的措施。

但是，这样一来，cin 与 cout 的读入、输出速度就会变得极其慢，喜欢用 cin 与 cout 的童鞋肯定表示不嘻嘻。

不过，万能的 C++ 早已备好了措施：ios::sync_with_stdio(0)！它可以取消 cin 与 cout 和 stdio 的绑定，故可以提升速度。

不过，这样一来，你就不能同时使用 cin 与 cout 和 scanf 与 printf，因此要理智使用。

这里以洛谷 P1923 【深基9.例4】求第 k 小的数为例。

使用 ios::sync_with_stdio(0)

不使用 ios::sync_with_stdio(0)

很容易看出来两者的差别吧。

但是，在竞赛（要开 freopen 的情况下），必须使用 stdio 来重定向输入输出，你这样一关绑定，那 freopen 不就用不了了嘛！所以，你就会喜提爆零大礼包。

2、使用 C 的输入输出

既然 iostream 慢，那我们就用 stdio 嘛！直接使用 scanf 和 printf 来读入、输出数据，速度中规中矩。

还是以洛谷 P1923 【深基9.例4】求第 k 小的数为例。

使用 stdio

3、使用 getchar 和 putchar 来进行快速读入、输出

这是重头戏！！

getchar 和 putchar 本来是针对字符的读入输出，但由于它 \mathcal{O}(1) 的时间复杂度，可以用它来快速读入、输出整数，时间复杂度 \mathcal{O}(n)，其中 n 表示数字的位数。

快速输入

定义一个 read 函数。

void read(int &x);

首先，重复输入前面的非数字字符，判断是否为负号。

x = 0; // 初始化 x
int flag = 1;
while(!isdigit(ch)) {
    if(ch == '-') flag = -1;
    ch = getchar();
}

然后，重复循环并更新变量 x 直到读入了非数字字符（可以使用 cctype 头文件中的 isdigit 函数）。

ch = getchar(); // 避免读入的是负号导致下面的循环进不去
while(isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
}

最后，将 x 乘以 flag。

x *= flag;

快速输出

由于快速输出是要从左至右输出，而传统的取余方法是从右至左输出，我们可以写一段递归代码，利用 putchar 快速输出。

首先，定义一个 write 函数。

void write(int x)

然后，判断 x 是否是负数。

if(x < 0) {
    putchar('-');
    x *= -1;
}

接着，递归实现从左至右输出。

if(x >= 10) write(x / 10);
putchar(x % 10 + '0');

不过，使用递归实现常数较大 （也是 STL 的通病），因此考虑采用栈来模拟这一过程。

可以定义一个手工栈，存储 x 的每一位，最后逆序输出。

signed st[120], top = 0;
while(x > 0) {
    st[top++] = x % 10 + '0';
    x /= 10;
}
for (signed i = top - 1; i >= 0; i--) putchar(st[i]);

完整代码

void read(int &x) {
    x = 0;
    char ch = getchar();
    int flag = 1;
    while(!isdigit(ch)) {
        if(ch == '-') flag = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    x *= flag;
}
void write(int x) {
    if(x < 0) {
        putchar('-');
        x *= -1;
    }
    signed st[120], top = 0;
    while(x > 0) {
        st[top++] = x % 10 + '0';
        x /= 10;
    }
    for (signed i = top - 1; i >= 0; i--) putchar(st[i]);
}

究极优化后的时间

小技巧

可以使用 C++ 中的关键字 template 来自定义读入输出的数据类型。

用法如下：

template <typename T>
// 这是你的代码，其中 T 可以视作一个普通的数据类型关键字来使用

例：

template <typename T>
void read(T &x) {
    x = 0;
    char ch = getchar();
    int flag = 1;
    while (!isdigit(ch)) {
        if(ch == '-') flag = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    x *= flag;
}
template <typename T>
void write(T x) {
    if (x >= 0 && x < 10) {
        putchar(x + '0');
        return ;
    } 
    if (x < 0) {
        putchar('-');
        x *= -1;
    }
    int st[120], top = 0;
    while (x > 0) {
        st[top++] = x % 10 + '0';
        x /= 10;
    }
    for (int i = top - 1; i >= 0; i--) putchar(st[i]);
}

这样，这段快读快写代码无论什么数据类型都能用了。

注：<template> 关键字因涉及到类型判定，会让程序运行时间略微增加 1~10 毫秒，如果想要卡常的话还是尽量不要用 <template> 了。

\text{Update 2025.5.11}

修复了一处代码错误。