编者注：虽然标题中提到了 OI，但个人认为本文对追求极限的代码调优的价值远大于对 OI 的价值。

# 免责声明

本文仅供参考，由读者引发的一切后果，任何责任由读者自行承担。后果包括但不限于：

1. 优化后程序变慢。
2. 某些 OJ/OI 上导致的编译错误。
3. 文章中的某些错误引起的争论。

# GCC 系列

关于 GCC 的黑科技想必大家也就知道这几句吧：

#pragma GCC optimize(3)

#pragma GCC optimize(2)

#pragma GCC optimize(1)

俗称 “吸氧”。

在这里小编就简单地讲一下 -O1 , -O2 , -O3 , -Os （怎么还有个 -Os ）。

# O 系列

# -O1

包含下列选项：

-fauto-inc-dec

-fcprop-registers

-fdce

-fdefer-pop

-fdelayed-branch

-fdse

-fguess-branch-probability

-fif-conversion2

-fif-conversion

-finline-small-functions

-fipa-pure-const

-fipa-reference

-fmerge-constants -fsplit-wide-types

-ftree-builtin-call-dce

-ftree-ccp

-ftree-ch

-ftree-copyrename

-ftree-dce

-ftree-dominator-opts

-ftree-dse

-ftree-fre

-ftree-sra

-ftree-ter

-funit-at-a-time

-fomit-frame-pointer

# -O2

除了加载 -O1 的选项外，还加载：

-fthread-jumps

-falign-functions -falign-jumps

-falign-loops -falign-labels

-fcaller-saves

-fcr-Ossjumping

-fcse-follow-jumps -fcse-skip-blocks

-fdelete-null-pointer-checks

-fexpensive-optimizations

-fgcse -fgcse-lm

-findirect-inlining

-foptimize-sibling-calls

-fpeephole2

-fregmove

-freorder-blocks -freorder-functions

-frerun-cse-after-loop

-fsched-interblock -fsched-spec

-fschedule-insns -fschedule-insns2

-fstrict-aliasing -fstrict-overflow

-ftree-switch-conversion

-ftree-pre

-ftree-vrp

# -O3

除了加载 -O2 外，还加载：

-finline-functions

-funswitch-loops

-fpredictive-commoning

-fgcse-after-reload

-ftree-vectorize

# -Os

在研究编译驱动的 makefile 的时候，发现 GCC 的命令行里面有一个 -Os 的优化选项。

遍查 GCC 文档，发现了 -O0 , -O1 , -O2 , -O3 ，就是没有发现 -Os 。

祭出 GOOGLE，搜了一下，终于发现这篇文章说明了 -Os 的作用：

http://www.linuxjournal.com/article/7269

原来 -Os 相当于 "-O2.5"。是使用了所有 -O2 的优化选项，但又不缩减代码尺寸的方法。
除了包含 -O2 的开关外， -Os 还会使得下列开关禁用。

-falign-functions 

-falign-jumps 

-falign-loops

-falign-labels 

-freorder-blocks 

-freorder-blocks-and-partition

-fprefetch-loop-arrays 

-ftree-vect-loop-version

另外，对于多个 -O 选项的情形，最后一个加载的为有效。比如 gcc -O1 -Os -O3 –o test test.c ，有效的优化开关为 -O3 。

一般来说，用的最多的是 -O3 和 -Os ，如果遇到程序运行不正常的问题，请降低优化级别，如把 -O3 改为 -O2 （情况很少见）。

# 针对目标机器

# -march=cpu-type

为 cpu-type 所针对的机器开启需要的指令集。

cpu-type 可以为 pentium4、core2、athlon-4 等（具体参见文档），比如 -march=core2 时，则会开启 core2 所支持的 MMX、SSE、SSE2、SSE3、SSSE3 指令集。

另外还支持 native 类型，为编译器所在目前的 CPU 类型优化指令集，指定 -march=native 。

# -mfpmath=unit

选择浮点运算单元。

unit 可以为 387 和 sse 。

387 为 x86 系列的默认值，使用标准的 387 浮点协处理器。

sse 为 x64 的默认值，使用 sse 指令集。

一般你的程序如果有大量的浮点运算的话，在 P4 和 K8 以上级别的处理器上推荐开启 -mfpmath=sse 。

# 加载指定指令集

可以使用 -msse2 或 -msse4.1 加载指定的指令集。

# 其他比较有效的选项

# -ftracer

执行尾部复制以扩大超级块的尺寸，它简化了函数控制流，从而允许其它的优化措施做的更好。单独使用没啥意义，和其他优化选项一起使用很有效。

# -ffast-math

违反 IEEE/ANSI 标准以提高浮点数计算速度，是个危险的选项，仅在编译不需要严格遵守 IEEE 规范且浮点计算密集的程序考虑采用。不考虑精度时使用这个选项速度会加快。

# -fivopts

在 trees 上执行归纳变量优化。

# -ftree-parallelize-loops=n

使循环并行化。只当循环无数据依赖时使用，在多核 CPU 上时使用才会有利。

# -ftree-loop-linear

在 trees 上进行线型循环转换。它能够改进缓冲性能并且允许进行更进一步的循环优化。

# -fforce-addr

必须将地址复制到寄存器中才能对他们进行运算。由于所需地址通常在前面已经加载到寄存器中了，所以这个选项可以改进代码。

# -floop-interchange

交换循环变量。

例如：

DO J = 1, M

  DO I = 1, N

    A(J, I) = A(J, I) * C

  ENDDO

ENDDO

会改变为：

DO I = 1, N

  DO J = 1, M

    A(J, I) = A(J, I) * C

  ENDDO

ENDDO

改变后，如果 N 比缓冲区大的话，会更有效率。这是因为 Fortran 里数组是以列主元为排列方式的。当然这个选项并不仅仅用于 Fortran，gcc 家族的编译器都有效。

# -fvisibility=hidden

设置默认的 ELF 镜像中符号的可见性为隐藏。使用这个特性可以非常充分的提高连接和加载共享库的性能，生成更加优化的代码，提供近乎完美的 API 输出和防止符号碰撞。我们强烈建议你在编译任何共享库（Dll）的时候使用该选项。

-fvisibility-inlines-hidden

默认隐藏所有内联函数，从而减小导出符号表的大小，既能缩减文件的大小，还能提高运行性能，强烈建议你在编译任何共享库的时候使用该选项。

# -minline-all-stringops

默认时 GCC 只将确定目的地会被对齐在至少 4 字节边界的字符串操作内联进程序代码。该选项启用更多的内联并且增加二进制文件的体积，但是可以提升依赖于高速 memcpy , strlen , memset 操作的程序的性能。

# -m64

生成专门运行于 64 位环境的代码，不能运行于 32 位环境，仅用于 x86_64 [含 EMT64] 环境。

# -fprefetch-loop-arrays

生成数组预读取指令，对于使用巨大数组的程序可以加快代码执行速度，适合数据库相关的大型软件等。具体效果如何取决于代码。不能和 -Os 一起使用。

# -pipe

在编译过程的不同阶段之间使用管道而非临时文件进行通信，可以加快编译速度。建议使用。

# 推荐选项开关

综上，比较安全的开关为

-pipe

-O3 (-Os)

-march=native

-mfpmath=sse

-msse2

-ftracer

-fivopts

-ftree-loop-linear

-fforce-addr

如果不需要多高的精度，比如 GUI 框架之类，加入：

-ffast-math

如果是编译的是共享库（ .dll , .a ）加入

-fvisibility=hidden

-fvisibility-inlines-hidden

注意某些比赛不能使用 -O1 , -O2 , -O3 , -Os .

# 底层优化（坑）

# I/O 优化

I/O 优化是卡常中最常用的技巧，当数据较大的时候，读入输出占用了很多时间。

# 读入优化

流输入方式很方便，不需要记忆占位符，但每次读入时，它都要检测是否和 stdin 的同步（是否被 freopen 改变 / 是否被 scanf 读取），因此它是可以和 scanf 混用的。但也导致了它每次都要从数据开始位置跳转到当前读入的位置，浪费了大量时间，可以用 std::ios::sync_with_stdio(false); 关闭两者的同步以加快速度，这样做之后会比 scanf 还快！但必须注意，调用后不能再用 freopen ，但是还可以用 fstream 。

当然，更好的方法是用 getchar 自己写读入函数。

inline void read(int &sum) {

    char ch = getchar();

    int tf = 0;

    sum = 0;

    while ((ch < '0' || ch > '9') && (ch != '-')) ch = getchar();

    tf = ((ch == '-') && (ch = getchar()));

    while (ch >= '0' && ch <= '9') sum = sum * 10 + (ch - 48), ch = getchar();

    (tf) && (sum = -sum);

}

inline int read() {

  int x = 0, c = getchar(), f = 0;

  while (c < '0' || c > '9') f |= c == '-', c = getchar();

  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

  return f ? -x : x;

}

这样效率有了很大的提升，而且可以和 scanf 混用（字符串等），第 7 行和第 10 行的代码后面会说。

我们知道， getchar 是逐字符读取的，在 stdio.h 中，有一个 fread 函数，能整段读取，比 getchar 还快，并且支持 freopen （完美兼容）和 fopen （需要把下面的所有 stdin 改成你的文件指针）。

函数原型： size_t fread(void *buffer, size_t size, size_t count, FILE *stream);

作用：从 stream 中读取 count 个大小为 size 个字节的数据，放到数组 buffer 中，返回成功了多少个大小为 size 个字节的数据。

inline char nc() {

    static char buf[1000000], *p1 = buf, *p2 = buf;

    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;

}

//#define nc getchar

inline void read(int &sum) {

    char ch = nc();

    int tf = 0;

    sum = 0;

    while ((ch < '0' || ch > '9') && (ch != '-')) ch = nc();

    tf = ((ch == '-') && (ch = nc()));

    while (ch >= '0' && ch <= '9') sum = sum * 10 + (ch - 48), ch = nc();

    (tf) && (sum = -sum);

}

但要注意，由于这种方法是整段读取的，这也造就了它两个巨大的缺陷：

1. 不能用键盘输入。数据还没输入，程序怎么整段读取。如果你需要在电脑上用键盘输入调试，请把第 6 行的注释取消。
2. 不能和 scanf ， getchar 等其他读入方法混合使用。因为 fread 是整段读取的，也就是说所有数据都被读取了，其他函数根本读取不到任何东西（只能从你的读取大小后面开始读），因此，所有类型的变量读入都必须自己写，上面的 read 函数只支持 int 类型。

下面是测试，摘自 LibreOJ，单位为毫秒（$n=3 \times 10^6$）。

没错，你没有看错， fread 以压倒性的优势碾压了其他所有方法，而关闭同步的 cin 比 scanf 快，并且读 long long 的时候比 getchar 还要快。

下面的内容某些 OI 比赛不支持。慎用！

其实还可以更快， Linux 下 sys/mman.h 中存在函数 mmap ， scanf 底层实现时调用的就是 mmap 函数，其作用是把文件映射进内存，这里仅仅给出代码，有兴趣的同学可以自行查阅有关资料。

#include <sys/mman.h>

namespace Inputs {

    char* s;

    int a[24];

    io() {

        s = (char*)mmap(NULL, 1 << 26, PROT_READ, MAP_PRIVATE, fileno(stdin), 0);

    }

    void scan(char* u) {

        while (*s < 48) ++s;

        while (*s > 32) *u++ = *s++;

        *u = 0;

    }

    int scan() {

        int Hibiki = 0, v = 1;

        while (*s < 48) v = *s++ ^ 45 ? 1 : -1;

        while (*s > 32) Hibiki = Hibiki * 10 + *s++ - 48;

        return Hibiki * v;

    }

}

有人喜欢用 isdigit 宏，但这个宏在本机测试上的确更慢了，这个宏的效率还有待研究。

# 输出优化

输出优化并不是十分常用，因为很少有题目要求大量输出，这里仍然给出代码。（第 4 行以后再说）

void write(int x) {

    if (x == 0) return (void)putchar('0');

    (x < 0) && (putchar('-'), x = -x);

    static int a[26];

    int tp = 0;

    while (x > 0) {

        a[++tp] = x % 10;

        x /= 10;

    }

    for (int i = tp; i > 0; i--) putchar(a[i] + '0');

}

如果你按照上面的代码打，那只能说明你的想象力不够， fwrite 扑进 fread 的怀里失声痛哭。 fwrite 的优势被你完美地抛弃了，取而代之的是逐字符输出的 putchar 。

函数原形：

size_t fwrite(const void *buffer, size_t size, size_t count, FILE *stream);

作用：把 buffer 中的数据拆成大小为 size 个字节的数据，输出前 count 个到 stream 中，实际成功写入的大小为 size 的数据块数目。

namespace Ostream {

  static const int BUF = 50000000;

  char buf[BUF], *h = buf;

  inline void put(char ch) {

    h == buf + BUF ? (fwrite(buf, 1, BUF, stdout), h = buf) : 0;

    *h++ = ch;

  }

  inline void putint(int num) {

    static char _buf[30];

    sprintf(_buf, "%d", num);  //(*)

    for (char *s = _buf; *s; s++) put(*s);

  }

  inline void finish() { fwrite(buf, 1, h - buf, stdout); }

};

有人也许会说，上面的代码的 (*) 处还可以优化，但这个优化的意义并不大，当然，也可以优化。

下面是测试：

($n = 5 \times 10^6$ , rand)

Clock Rate: 3.70 GHz

RAM: 4 GB

由上表得， sprintf 的复杂度并不高， fwrite 也没有给 fread 丢脸。而 fprintf 的表现却让人大跌眼镜。 getchar 的结果很可能具有偶然性，反正上面的数据是在小编的机器上用同一组随机数测的。

# 位运算

在很多时候，我们会听到很多有关位运算的追捧，像 “位运算的常数很小，比加减法还要快”。这是真的吗？

# 左移和右移的天上地下

下面有两段代码：

#include <cstdio>

int x = 5;

int main(void) {

    x <<= 1;

    printf("%d", x);

    return 0;

}

#include <cstdio>

int x = 5;

int main(void) {

    x *= 2;

    printf("%d", x);

    return 0;

}

它们理论上是等价的，但 g++ 翻译成汇编后呢？

两段代码的汇编代码是一样的！下面是 x<<=1 和 x*=2 被翻译后的代码。

addl    %eax, %eax

它等价于 a=a+a 。是不是被打脸了，响不响，痛不痛，红不红，痒不痒…… 好吧，从上面的例子可以看出，某些时候自作聪明的优化并没有任何用。

那乘以 4 呢？翻译后的代码还是一样的：

sall    $2, %eax

上面的代码等价于 x<<=2 。现在死心了吧。

或许你还执着于 x*=10 。这次翻译后的汇编代码终于不一样了，下面是 x*=10 的汇编代码（ -O2 优化）：

leal    (%eax,%eax,4), %eax
addl    %eax, %eax

只有两条指令：

x=x+x*4 // 别看是加法和乘法，却是一条指令完成

x=x+x   // 加法还不容易吗

那些喜欢用 x=(x<<3)+(x<<1) 的人请自重。

那是不是说位运算一无所用呢？并不是，在除法方面有不少用处。

右移的汇编代码：

  movl    _x, %eax
  sarl    %eax
  movl    %eax, _x
  movl    _x, %eax

除以 2 的代码：

  movl    _x, %eax
  movl    %eax, %edx  ;(del)
  shrl    $31, %edx   ;(del)
  addl    %edx, %eax  ;(del)
  sarl    %eax
  movl    %eax, _x
  movl    _x, %eax

整整多了三行。

但这种情况仅限于有符号的整数，因为有符号的整数的右移和除法不是同一个东西，编译器还需要修正一下。
如果用的是 unsigned 类型，那汇编代码又一样了。

# Mod 和 And 的战争

下面是 x%2 的代码（ -O2 ）：

  movl    _x, %eax
  movl    $LC0, (%esp)
  movl    %eax, %edx   ;(del)
  shrl    $31, %edx    ;(del)
  addl    %edx, %eax   ;(del)
  andl    $1, %eax
  subl    %edx, %eax   ;(del)
  movl    %eax, 4(%esp)
  movl    %eax, _x

那 x&1 呢？少了 4 条语句（ -O2 ）：

  movl    _x, %eax
  movl    $LC0, (%esp)
  andl    $1, %eax
  movl    %eax, 4(%esp)
  movl    %eax, _x

# Xor 和 temp 的故事

相信大家在学交换两个变量的值的时候一定会先学习所谓的 “三变量交换法”，然后就被异或取代了。

下面是异或（ a^=b^=a^=b ）的汇编：

  movl    _b, %edx
  movl    _a, %eax
  xorl    %edx, %eax
  xorl    %eax, %edx
  xorl    %edx, %eax
  movl    %eax, _a
  xorl    %eax, %eax
  movl    %edx, _b

有 movl 指令和 xorl 指令各 4 条。
那三变量交换法（ int t=a; a=b, b=t; ）呢？

  movl    _a, %eax
  movl    _b, %edx
  movl    %eax, _b
  xorl    %eax, %eax
  movl    %edx, _a

从此，有 temp 再没有异或。

# 神奇的 “位运算技巧”

网上有很多奇奇怪怪的方法，例如取绝对值 (n^(n>>31))-(n>>31) ，取两个数的最大值 b&((a-b)>>31)|a&(~(a-b)>>31) ，取两个数的最小值 a&((a-b)>>31)|b&(~(a-b)>>31) 。

喜欢用上面代码的人难道没有自己亲自数一数上面有多少条位运算的指令吗？

但凡事没有绝对，还是有一些优秀的例子的：

取二进制下最后一个 1 和后面的 0 ：

lowbit(x)=(x&(-x))

判断一个数是不是 2 的幂：

n>0?(n&(n-1))==0:false

# Xor 和网络流的故事

还记得网络流的反向弧？通常某些人喜欢在结构体中新建一个变量来表示这条边的反向弧编号。但这样不免有些浪费，因为在插入新边的时候，我们一般会把两条互为反向弧的边相邻插入，有一个有趣的性质可以完美地解决这个问题：

(2*x)^1=2*x+1

(2*x+1)^1=2*x

也就是说，我们可以用异或节省下一个空间。

那在汇编中呢？异或本来就是逻辑运算，一条指令 xorl $1, _x 搞定，但如果用另一个变量呢？编译器需要对变量进行初始化，还多了一条指令。

# 条件语句

相信条件语句会在程序中经常出现，而且也是不可避免的，谁知道，这么死板的事情还可以再优化。

# if 和 ?: 的故事

if-else 与 ?: 运算符本质上相同，大多数情况下所产生的汇编代码完全相同。

对于下面的两段代码：

	if (x == 1)
	printf("1");
	else
	printf("2");

x == 1 ? printf ("1") : printf ("2");

网上有人说，三目运算符比 if 语句快，所以第二段代码就比第一段代码快。

实际上汇编代码是一模一样的，所以运行时间也是一样的。

摘自：浅谈底层常数优化及编译器优化 - zhaojinxi 的博客 - 洛谷博客

?: 运算符并不会消除分支预测。

分支预测的原理，是在 if 括号内部的判断语句未执行完成时，在另一线程中预测一条分支执行接下来的语句。当判断语句执行完毕时，若执行结果与预测相同，则继续执行该分支语句；若执行结果与预测不同，则重新执行另一分支语句。分支预测可以充分发挥 CPU 的多线程性能，避免多余的等待。

分支预测的效率取决于 CPU 的设计。在大部分情况下，分支预测能加快运算速度，除非分支预测的准确度极低。毕竟 CPU 的设计者也不是傻子。

分享一篇不错的关于分支预测的文章：为什么很多程序员不用 switch，而是大量的 if...else if ...？ - 是 Yes 呀的回答 - 知乎

下面的内容某些 OI 比赛不支持。慎用！

gcc 存在内置函数： __builtin_expect(!!(x), tf)

当 tf 为 true 时表示 x 非常可能为 true ，反之同理。

用法： if(__builtin_expect(!!(x), tf))

编者附：

而 GCC 提供了一个内建函数 __builtin_expect ，通过分支预测提高效率，将接下来运行的可能性较大的代码放在靠前的位置，减少指令跳转，这样保证了空间局部性，可以减少 cache miss。但经过测试后发现， __builtin_expect 仅在开启 -O2 优化下有效。

例如下面的代码：

	#include <cstdio>
	#include <cstdlib>
	int main() {
	srand(2333);
	int cnt1 = 0, cnt2 = 0;
	for (int i = 0; i < 1000000000; ++i) {
	int t = rand();
	if (t < 10)
	++cnt1;
	else
	++cnt2;
	}
	printf("%d %d\n", cnt1, cnt2);
	}

	#include <cstdio>
	#include <cstdlib>
	int main() {
	srand(2333);
	int cnt1 = 0, cnt2 = 0;
	for (int i = 0; i < 1000000000; ++i) {
	int t = rand();
	if (__builtin_expect(t < 10, false))
	++cnt1;
	else
	++cnt2;
	}
	printf("%d %d\n", cnt1, cnt2);
	}

使用 __builtin_expect (t < 10, false) 后，编译器把 else 后的语句放到了紧跟着前面的语句的位置，而当 t < 10 为 true 时才进行跳转。

摘自：浅谈底层常数优化及编译器优化 - zhaojinxi 的博客 - 洛谷博客

# switch 和 if-else 的故事

下面有两段代码，你觉得那段更快呢？

if (x == 1)

    x++;

else if (x == 2)

    x *= 2;

else if (x == 3)

    x /= 3;

else if (x == 4)

    x >>= 1;

else if (x == 5)

    x = 1;

switch (x) {

    case 1:

        x++;

        break;

    case 2:

        x *= 2;

        break;

    case 3:

        x /= 3;

        break;

    case 4:

        x >>= 1;

        break;

    case 5:

        x = 1;

}

显然地，下面的代码更快，因为上面的代码需要逐条判断，而下面的代码直接跳转。

那是不是所有 switch 都比 if 快呢？凡事没有绝对，当 switch 遇到 default 的时候，整个程序的效率就会大打折扣，因为它又回到了 if 的无脑判断模式。再比如，当 if 用来判断区间的时候就比 switch 快， if 只需要做三次逻辑运算（两条判断，一条逻辑与），而 switch 呢？我就呵呵一笑。

# 短路的故事

此短路非彼短路，它指的是一种运算符的特性。

我们常用的逻辑运算符，例如 && 和 || 都是短路运算符。什么意思呢？比如在运算 A && B 时，如果发现 A 已经为 false ，就不会再计算 B。

现在你能解释第一章中留下的问题了吗？

(tf)&&(sum=-sum); 当 tf 为 true 的时候，会执行后面的 sum=-sum ，如果 tf 为 false ，则不会执行后面的 sum=-sum 。

等价于如下语句：

if (tf) sum = -sum;

tf = ((ch == '-') && (ch = getchar()));

当 ch='-' 时，会执行后面的 ch=getchar() ，因为 getchar 一般不会等于 0 （如果不放心可以写成 tf=((ch=='-')&&((ch=getchar()),true)) ），因此 tf 的结果等于 true 。

当 ch!='-' 时，不会执行后面的 ch=getchar() ， tf 的值为 false 。

等价于如下语句：

if (ch == '-') {

    tf = true;

    ch = getchar();

}

总结一下：

if(A) B; ⇔ (A)&&(B)

if(A) B; else C; ⇔ A&&(B,1)||C

为什么？详情参见下一小节。

如果短路运算符只能改写 if 语句，那这里就不会浪费这么多篇幅来介绍这个东西。事实上，这个东西比我们想象得有用得多。看下面两段代码：

double t = rand();

if (t / RAND_MAX < 0.2 && t != 0) printf("%d", t);

double t = rand();

if (t != 0 && t / RAND_MAX < 0.2) printf("%d", t);

你认为哪一份代码会更快？

好像没什么区别对吧。但对于 CPU 来说很有区别。第一段代码中的 t / RAND_MAX < 0.2 为 true 的概率约为 $20\%$，但 t!=0 为 true 的概率约为 $\frac{1}{RAND\_MAX}$，明显小于 20%。
因此，如果把计算一个不含逻辑运算符布尔表达式的计算次数设为 $1$ 次，设计算了 $X$ 次，则对于第一段代码，$X$ 的数学期望为 $65$，但对于第二段代码，$X$ 的数学期望为 $\frac{2\times (RAND\_MAX-1)}{RAND\_MAX}$，远远大于第一段代码。

总结一下，

• 遇到 A&&B 时，优先把可能为 false 的表达式放在前面。
• 遇到 A||B 时，优先把可能为 true 的表达式放在前面。

# 布尔表达式和逗号运算符的故事

为什么要专门设置这么一小节呢？
因为很多人喜欢用 if(x==true) ，直接用 if(x) 就好了。还有 x==false 和 !x ，它们也是等价的。

现在，请另一位大佬隆重登场：逗号运算符。

若干条语句可以通过逗号运算符合并成一条语句。
例如 t=a;a=b;b=t; 可以写成 t=a,a=b,b=t; 有什么用吗？它的返回值。

int x=(1,5,4,2,6,3,9);

猜一猜，上面的语句执行完后 x​ 的值是多少？

答案是 9。没错，逗号运算符的返回值就是最后一个的值。

现在可以解释上一小节留下总结了吧。

A&&(B,1)||C ：当 A 为 true 时会执行 (B,1) ，返回值为 true ，因此 A&&(B,1) 的返回值为 true ，因此不会执行 C ，当 A 为 false 时，不会执行 (B,1) ，且 A&&(B,1) 的值为 false ，因此会执行 C 。

# Standard Template Library

如果能熟练使用 STL，则可以大大减小代码复杂度，提高对于部分人的可读性（前提是那个人也会 STL）。但在很多 OI 比赛中，STL 会成为性能瓶颈（不仅仅是常数瓶颈），而且要明白：对于 STL 来说， -O2 的开与否带来的不仅仅是几毫秒的差，而是一种蜕变！

# 容器

# 完全连续容器

在 STL 中，唯一的真正意义上的完全连续容器应该只有 vector 和 bitset 了，其中， vector 中的所有元素都是连续的，但它是怎么做到的？在某些编译器中，它实现内存分配的方法是当前的容量不足时，申请一块当前容量 2 倍的新内存空间，然后将所有的老元素全部拷贝到新内存中，添加大量元素的时候的花费的惊人的大。和 allocator 的时间复杂度一样。

函数原型： extern void *realloc(void *memory, unsigned int newsize);

作用：把 memory 开头的指针所占用的空间修改成 newsize 个字节大小。

内部是怎么实现的？在内存中寻找一片足够大的连续空间，然后把原来地方的数据拷到新空间中。

听着就觉慢，因此在 vector 需要存储大量数据的时候，尽量不要用 push_back ，直接用 resize(size_type size) 函数改变大小，或者先用 reserve(size_type size) 函数预留空间，然后再用 push_back 方法，这样能尽可能地降低其弊端。

但由于其是完全连续容器，因此在查找的时候效率和普通数组没有太大区别。

邻接表有两种实用的方法，一种是前向星（有人也叫向前星，这里以百度百科为准），另一种就是用 vector 。

尽管 vector 修改大小的时候会很浪费时间，但要知道， vector 可是一个完全连续容器，相比前向星好了不知道多少（从一个数组里跳来跳去）。

在某些需要频繁访问边（例如网络流和最短路），遇到很稠密的图的时候， vector 完全连续的作用就被发挥到了最大，而动态开辟空间的消耗也已被降到了最低最低，尤其是在开了 -O2 优化的时候。

下面分别是 vector 和前向星跑网络流（ISap）的用时。（$m=50n$）

十分明显地，开了 -O2 优化的 vector 跑得飞快，而随着数据大小的上升，vector 的速度也越来越快。

bitset 的大小是在编译时就被固定了，因此不会出现和 vector 一样浪费时间的情况。它的最大作用是节约空间。那里节约空间了？要知道，C++ 的任何类型都至少占用一个字节，包括 bool 。因此， bool 会浪费七个字节的空间。但其实 bitset 也是可以自己实现的。

# 部分连续容器

如果你认为 queue （一种容器适配器）和 deque 应该在上一章出现，那你就错了。事实上，它们并不是完全连续容器。它们内部的实现有点诡谲。为什么这样说呢？因为它们在内存中是部分连续的，也就是说，当内存不够的时候，它们就会再申请一段，然后再连接过去，因此在内存中，它们是不完全连续的，是多个内存块组成的，每个块中存放的元素连续内存，而内存块又像链表一样连接起来。

因为有了这种方法，它们不需要每次申请空间时，都像 vector 一样复制原来的元素。而是可以在常数时间内完成这个操作。因为它们在内存中是不完全连续的，因此速度不会太低。也可以很好地避免循环队列大小估计错误的可能。

但要注意是否会出现对空队列取队首或出队的操作，而且由于每次都会申请一大段的连续空间，因此需要注意空间的开销。

当我做完测试后却大吃一惊。

为什么会出现这种情况？

其实 queue 默认实现方法是封装 deque ，通过更改模板参数可以使用 vector 和 list 实现。而 deque 呢？由于其内存不完全连续，因此导致了过多的内存跳转，浪费了大量时间，由此可得，部分连续容器和完全连续容器的效率差极大。

因此，在能使用连续空间的情况下，尽可能地使用完全连续容器。

# 节点容器

节点容器就比较多了。常见的 map ， set 和 list 都属于它的范畴。

其中， list 有点像 deque ，和其原理差不多，只是内存块的大小恒为 1，插入和删除都可以在常数时间内完成。唯一的缺点是不支持二分查找和随机访问。而且由于 list 是不连续容器，因此它的查询会导致内存频繁地跳转，因此只有在经常需要增加或删除的时候才会考虑使用 list 。

set 和 map 属于关联容器，关联容器支持高效的关键字查找和访问，内部是以一种叫做红黑树的 BST 实现的，但它太复杂了，它的插入有 5 种情况，删除有 6 种情况，是 “当今信息界中平均速度最快的 BST”，比我们在 OI 比赛中有能力在时间内手动实现的 BST 快得多。

因此， set 和 map 的查询时间和红黑树的时间复杂度一致，基本上所有操作都是 $\log size$ 级别的，包括迭代器的 ++ 和 — 操作，它们在 BST 中相当于求前驱和后继。而且由于它们是节点容器，因此在内存中是断续的，反复地跳转可能导致更多的开销。

但当需要自己实现部分（不包括一些特别的功能，例如求排名）平衡树的功能时，用 set 和 map 一般会比手写更优。

如果遇到了不能用 set 和 map 的情况，并不推荐用 Splay，因为它的常数太大了，这里推荐一种极好的 BST: 替罪羊树 (Scapegoat Tree)，它的思想非常简单：当且仅当某棵子树的不平衡度超过 $\alpha$ 时，暴力重构整棵子树，从而避免了旋转的操作。

推荐阅读：

浅谈 C++ IO 优化 —— 读优输优方法集锦 - encore 的博客 - 洛谷博客

浅谈底层常数优化及编译器优化 - zhaojinxi 的博客 - 洛谷博客