提升 C++ I/O 性能的极致快读快写技术解析

核心逻辑与数学原理

在 NOIP 等算法竞赛中，当数据规模达到 $N, M \ge 10^6$ 级别时，传统的输入输出（I/O）往往会成为程序的性能瓶颈。若不进行优化，I/O 操作所消耗的时间甚至会超越算法核心逻辑的运行时间，导致程序因常数过大而引发 TLE（时间超限）。

C++ 默认的输入输出流 std::cin 和 std::cout 为了保证与 C 语言标准输入输出库（scanf / printf）的兼容性，在底层显式维护着一个同步机制。这意味着在执行每次 I/O 操作时，C++ 流都会强行刷新（Flush）对应的 C 缓冲区，从而引入了巨大的系统级上下文切换开销。此外，std::cin 默认与 std::cout 处于绑定（Tie）状态，在每次从输入流读取数据前，都会自动刷新输出流的缓冲区。其时间复杂度开销在常数层面被严重放大。

通过执行：

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

可以强行解除同步与绑定。其底层数学逻辑是消除了缓冲区高频刷新的常数级阶乘因子，使 C++ 流的 I/O 效率逼近甚至超越 scanf / printf。

然而，要达到极致的性能，必须绕过 C++ 的流解析层，直接操作底层的标准文件描述符输入缓冲区。这就需要引入更硬核的系统级函数 fread 和 fwrite。

fread 的数学本质是分块批量读入（Blocked I/O）。设测试数据文件总大小为 $S$ 字节，单次从磁盘读取的系统调用时间开销为 $T_{\text{sys}}$，单次内存字符扫描开销为 $T_{\text{mem}}$（其中 $T_{\text{sys}} \gg T_{\text{mem}}$）。 若使用普通的逐字符读入，总时间开销为：

$$T_{\text{normal}} = S \times T_{\text{sys}} + S \times T_{\text{mem}}$$

而使用 fread 申请一个大小为 $B$（通常设为 $1 \le B \le 1 \le 22$ 字节，如 $1 << 20$ 字节，即 1MB）的本地高效率内存缓冲区：

$$T_{\text{fread}} = \left\lceil \frac{S}{B} \right\rceil \times T_{\text{sys}} + S \times T_{\text{mem}}$$

由于 $\left\lceil \frac{S}{B} \right\rceil \ll S$，系统调用的次数被降低了几个数量级，I/O 的常数开销成功收敛到极致的 $\Omega(1)$ 基本内存移动开销。

快读快写状态机推导

快读（Fast Read）的本质是一个确定有限状态自动机（DFA）。对于一个符号整型数字，其字符序列由可选的负号 - 和一串连续的数字字符 0-9 组成。

1. 状态转移逻辑

• 状态 $S_0$（跳过非数字字符）：持续读入字符，若遇到 -，则标记符号变量 $f = -1$；若遇到字符 $c \in ['0', '9']$，则以此字符作为数字的最高位，累加至结果变量 $x$，并转移至状态 $S_1$。
• 状态 $S_1$（累加数字字符）：持续读入字符，只要 $c \in ['0', '9']$，就进行基数加权移位累加： $$x = x \times 10 + (c - '0')$$

若遇到任何非数字字符，状态机终止，返回结果 $f \times x$。

2. 位运算优化移位

在状态 $S_1$ 的基数累加中，乘以 $10$ 的操作可以利用位运算进行硬件级加速。由于 $10 = 8 + 2 = 2^3 + 2^1$，因此：

$$x \times 10 = (x \ll 3) + (x \ll 1)$$

这直接避开了 CPU 内部相对低效的乘法器指令，进一步压低了常数。

C++ 标准源码

以下提供一套在 NOIP/Linux 生产环境下性能登峰造极的通用快读快写（包括处理负数、__int128 扩展以及 fwrite 高速输出缓存）的完整源码。

#include <iostream>
#include <vector>
#include <algorithm>

// 极致快读内存缓冲区大小定义：1 << 20 字节即 1MB
const int IO_BUFF_SIZE = 1 << 20;

class FastIO {
private:
    char in_buf[IO_BUFF_SIZE];
    int in_p1 = 0, in_p2 = 0;

    char out_buf[IO_BUFF_SIZE];
    int out_p = 0;

    // 内部底层逐字符读入，利用 fread 批量填充
    inline char gc() {
        if (in_p1 == in_p2) {
            in_p2 = (in_p1 = 0) + fread(in_buf, 1, IO_BUFF_SIZE, stdin);
            if (in_p1 == in_p2) return EOF; // 文件结束
        }
        return in_buf[in_p1++];
    }

public:
    // 析构时必须强行刷新输出缓冲区，防止数据残留导致无输出 WA
    ~FastIO() {
        flush();
    }

    inline void flush() {
        if (out_p > 0) {
            fwrite(out_buf, 1, out_p, stdout);
            out_p = 0;
        }
    }

    // 内部底层逐字符输出，利用 fwrite 满额自动刷新
    inline void pc(char c) {
        if (out_p == IO_BUFF_SIZE) {
            flush();
        }
        out_buf[out_p++] = c;
    }

    // 极致快读模板函数，支持所有标量整型及 __int128
    template <typename T>
    inline void read(T &x) {
        x = 0;
        T f = 1;
        char c = gc();
        // 状态 S0: 跳过空白及非法字符
        while (c < '0' || c > '9') {
            if (c == '-') f = -1;
            c = gc();
        }
        // 状态 S1: 移位累加数字
        while (c >= '0' && c <= '9') {
            // 致命踩坑点：位运算优化乘法时，外层括号必须严谨，否则由于优先级问题会引发计算错误
            x = (x << 3) + (x << 1) + (c ^ 48); // c ^ 48 等价于 c - '0'
            c = gc();
        }
        x *= f;
    }

    // 极致快写模板函数
    template <typename T>
    inline void write(T x) {
        if (x < 0) {
            pc('-');
            x = -x;
        }
        static char stack[40]; // 栈空间暂存逆序数位
        int top = 0;
        do {
            stack[top++] = (x % 10) ^ 48;
            x /= 10;
        } while (x);
        while (top > 0) {
            pc(stack[--top]);
        }
    }

    inline void write_char(char c) {
        pc(c);
    }

    inline void write_string(const char* s) {
        while (*s) pc(*s++);
    }
} io;

int main() {
    // 致命踩坑点：一旦使用基于 fread/fwrite 的自定义 FastIO，
    // 严禁在后续代码中混用 std::cin, std::cout, scanf, printf，否则会发生输入流抢占导致数据错乱！

    int n;
    io.read(n);

    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        long long val;
        io.read(val);
        sum += val;
    }

    io.write_string("Total Sum: ");
    io.write(sum);
    io.write_char('\n');

    return 0; // 程序退出时，io 对象的析构函数会自动触发最终的 flush() 写入磁盘
}

NOIP 实战避坑指南

1. 自定义 fread 快读与标准输入函数混用引发数据断层

• 低级错误表现：在代码的前半部分为了读入图的节点数使用了 io.read(n)，随后因为要读入一串字符串，图方便直接调用了 scanf("%s", str) 或 std::cin >> str。运行后发现 str 读入的数据完全错误，甚至程序直接卡死。
• 避坑手段：fread(in_buf, 1, IO_BUFF_SIZE, stdin) 会在一瞬间强行把标准输入流底层的物理数据一次性榨干并塞入自定义的 in_buf 缓冲区。此时，操作系统底层的输入流指针已经移动到了整个文件的末尾。随后你再调用 scanf 或 cin 时，它们去底层的系统缓冲区读取数据，只会读到 EOF。铁律：一旦在代码中引入了基于 fread / fwrite 的块级快读快写，必须保证全篇代码百分之百使用自定义的 I/O 接口，严禁与其他原生 I/O 库混用。

2. 快写 fwrite 缓冲区未手动刷新导致输出空中蒸发

• 低级错误表现：在代码最后通过 io.write(ans) 输出了最终答案，本地测试时一切正常，但提交到评测机上后，评测结果显示“无任何输出（Output Empty）”从而直接被判 WA。
• 避坑手段：fwrite 是将数据先写入用户态的本地数组 out_buf 中，只有当缓冲区被填满（达到 IO_BUFF_SIZE）时才会真正调用系统级输出。如果你的答案数据量很小，未能填满缓冲区，且在程序结束前没有手动刷新缓冲区，这些答案数据就会在进程消亡时直接被操作系统内存丢弃，无法落盘。虽然上述代码在类中使用了析构函数自动 flush()，但在考场上，为了万无一失，必须在 main 函数结束返回前，显式调用一次强行刷新：io.flush();

经典 NOIP/洛谷 真题

1. 洛谷 P3865 【模板】ST 表

• 题意描述：给定一个长度为 $N$ 的序列，包含 $M$ 次询问，每次询问给定区间 $[L, R]$ 里的最大值。其中 $N, M \le 10^6$。
• 问题本质：静态区间最大值查询（RMQ 问题）。
• 核心解题思路：使用预处理复杂度为 $O(N \log N)$，查询复杂度为 $O(1)$ 的 ST 表算法。本题的算法核心逻辑极其简单，但由于 $M = 10^6$ 的询问量极为恐怖，总输入数据行数达到了百万级。如果使用不加优化的 std::cin，I/O 时间将耗时近 3.0 秒，直接导致 TLE。而换用上述硬核的 fread 快读后，整个 I/O 的时间常数可以被无情压缩至 0.1 秒以内，为后文的倍增数组查询留出了绝对安全的运行空间。

2. 洛谷 P1177 【模板】快速排序

• 题意描述：利用快速排序或者其他 $O(N \log N)$ 算法，对包含 $N$ 个常规元素的序列进行升序排列。其中 $N \le 10^5$。
• 问题本质：基础排序与数据流吞吐常数校验。
• 核心解题思路：虽然标准解法是直接调用 std::sort，但在大容量评测点下，由于输出元素需要空格或换行隔开，大量的数字转字符输出会耗费巨大常数。在手写三路快排或堆排时，为了在极限时限内通过，引入 fwrite 的快写机制可以绕过标准输出流极为臃肿的格式化解析层（Format Parsing），直接将逆序压栈后的字符块批量倾倒至物理显存/终端，其输出速度可达传统 std::cout << ans << " " 的 20 倍以上。