作为 OI 选手不可不知的编程操作注意事项（新手向）

Autre · 2024-10-24 13:57:05 · 算法·理论

环境相关

• Windows 下，在终端中调用以相对路径描述的程序时，系统会优先在当前路径寻找，然后在环境变量中的 Path 变量列出的路径中寻找。如果想在任意路径下都使用 g++/gdb 等命令，可以直接使用绝对路径，或将这些命令所在位置（一般在编译器安装目录的 bin 子目录下）加入 Path 环境变量。
• Linux 下 g++/gdb 所在的路径 /usr/bin 默认在 PATH 中，不用手动配置。
• Linux 下比较两个文件可以使用 diff [文件 1] [文件 2]，指定 -w 以忽略所有空白字符，-Z 忽略行末空格，-B 忽略所有空行，-q 不输出具体哪里匹配失败只输出是否相等。和 Windows 下 fc 命令类似，如果两个文件相同当且仅当程序返回值为 0。

程序内存空间相关

• 全局/static 变量（包括数组）在静态空间内；局部（函数内）非声明的非 static 变量（包括数组）、通过 new/malloc 分配的空间、除 std::array 以外所有 STL 容器的元素动态分配。struct/class 内成员变量按照上述规则若为动态分配的，则为动态分配的；否则取决于该 struct/class 对象是否是动态分配的。
• Windows/Linux 下 GCC 编译器均可使用 size 命令（与 g++ 命令在同一目录），使用方法为 size [可执行文件名]，该命令输出中 dec 下方的数为以 B 为单位的静态空间大小。
• Linux 下的内存管理，常驻内存即“用多少算多少”，虚拟内存为“开多少算多少”，arbiter 评测所限制的“内存”指虚拟内存。
• Linux 下 \time -v [可执行文件名] 运行该程序并统计运行时间、内存大小等信息。其中 User Time 为评测所统计的“运行时间”，Maximum resident set size 为常驻内存峰值。目前不清楚测算虚拟内存峰值的方法，不过可以对虚拟内存大小进行限制，见下文。
• Linux ulimit 命令可以对该终端之后运行的所有程序（包括在该终端打开的终端）做出某些限制。如果不小心用 ulimit 错改了一些设置，并且导致无法再次运行 ulimit 改正设置，重新开一个终端即可。限制程序虚拟内存大小可以使用 ulimit -v [空间大小]（以 KB 为单位）；限制程序栈空间大小可以使用 ulimit -s [空间大小]（以 KB 为单位）。[空间大小] 可以填 unlimited，表示不做出限制。听说栈空间限制开过大或不做出限制，程序栈溢出可能导致死机，请谨慎使用。
• 请尽量避免用全局变量结尾和开头两个变量地址相减的办法测算空间，会测少（标准库自身会使用一部分静态空间），并且这种写法是 UB。

编译命令相关

• -o 指定编译的目标文件，并且如果编译失败也可能导致目标文件被删除/修改，请警惕 g++ a/a.cpp -o a.cpp 惨剧。NOI Linux 2 带有的 g++9.3.0 进行了改进，在源文件和目标文件相同时会报错。但 g++ a -o a.cpp 仍然会导致 a.cpp 被无条件删除。
• -g/g1/g2/g3 指定编译结果中带有的调试信息等级。-g 等同于 -g2，会记录行号、变量名等信息，-g3 则更强，会记录宏。对于不擅长使用 gdb 的选手而言，可以仅掌握 run 命令查看程序在哪 RE 了（不是）。
• Linux 下，-fsanitize=address,undefined 开启 address sanitizer 和 undefined sanitizer。前者能够检测堆栈溢出（包括死递归）、访问越界、整数除以 0 等问题，在检测到后打印当前寄存器、内存、函数调用栈等信息，如果编译时启用了 -g 则会提供问题在源码哪一行被触发，并立即触发 RE；后者能够检测大部分不由标准库规定的 UB，并报告引发 UB 的行数和列数，开 -fno-sanitize-recover=undefined 后会引发 RE。关于 UB 的详细信息请见下文。需要注意的是这个参数会大幅降低程序运行效率，测试运行时长请勿打开 sanitizer。
• -D[宏] -D[宏]=[值]，前者相当于在文件最开头加入 #define [宏] 1，后者相当于 #define [宏] [值]。顺便一提，-D_GLIBCXX_DEBUG 用于打开标准库的检查开关，可以有效排除错误地使用 STL 导致的 UB，代价是大量的检查，可能导致复杂度错误，比如会在 std::lower_bound 时线性地检查一遍所有元素是否有序。
• -std=c++14 务必要加上！否则 g++9.3.0 会默认以 -std=gnu++14 编译并导致类似 abs(__int128) 的 GNU 私货在本地过编，评测环境 CE。关于高版本语法，只要 NOI Linux 下严格按照题面上的编译命令过编译就基本不会出问题（出了问题也大概率不是你的问题）；关于高版本标准库，请勿使用任何奇技淫巧更改相关参数使用高版本标准库特性。
• -O2 现代比赛默认开 O2，测极限数据下程序用时别忘开就行。
• -Wall -Wextra 会打开大部分 warning 开关，包括检测易错运算符优先级的 -Wparentheses、检测未初始化变量的 -Wuninitialized。注意：检测作用域内外变量重名的 -Wshadow、检测隐式类型转换的 -Wconversion 等不包含在其中，需要手动开启。
• -ftrapv 可以在没有 ubsan 的情况下检测有符号整数溢出并直接触发 RE。

C++ 语法坑点

• 整数提升，当算术运算符两个操作数都短于 int，则会提升到 int 进行运算；若两个操作数长度相等，且有一个为无符号整数，则会提升到该长度的无符号整数；否则提升到较长的操作数对应的类型。经典错误是，对于空的 STL 容器 a，a.size()-1 一般而言是 unsigned long 类型的最大值。

STL 容器相关

• 调用 std::vector 的 clear 或 resize 使得元素个数减少，一般来说不会释放空间。可以使用 a.shrink_to_fit() 将 std::vector a 的容量自动调整为元素数量；对于任意类型的 STL，将其清空并释放空间可以写成 std::容器类型<元素类型>().swap(a)。
• GCC 自带的标准库（libstdc++）对std::unordered_set/map 的 clear 时间复杂度与哈希表桶个数成线性，不符合标准（与元素个数成线性）。并且由于 clear 不会改变桶的数量，导致对一个桶个数很多的 std::unordered_set/map 进行频繁 clear 会导致复杂度炸掉。应使用 a.erase(a.begin(), a.end()) 清空所有位置而不释放桶（这样写复杂度与元素个数成线性，并且可以避免后续插入元素时扩容的开销），或如上文的 std::unordered_set/map<元素类型>().swap(a) 清空所有元素和所有桶（这样写复杂度仍然与桶个数成线性，但是清空一次桶数变为 0，均摊后正确）。
• libstdc++ 实现的 std::hash 一般来说并不优，而且能很简单地被卡退化，详见这篇帖子。
• 标准对 std::vector<bool> 做了特化，压位实现，有点大病，别用。可以使用 std::basic_string<bool>，操作类似 std::string（即 std::basic_string<char>）。
• std::deque 为空或只有几个元素时，也会带有一定的空间常数，开过多的 std::deque 会导致空间过大，务必参考上文所述的 ulimit 方法进行测试。
• 迭代器失效。当 std::vector 发生扩容、std::unordered_set/map 发生 rehash 时所有迭代器失效；当 std::set/map 某元素被删除时只有该元素迭代器失效（想按照迭代器删除一个 std::set/map 中的元素同时获取它的下一个位置可以使用 it = s.erase(it)）等。

常见的未定义行为（UB）

• 有符号整数算术运算溢出。这里问题其实在于无符号整数溢出不是 UB，于是它在一些不希望溢出的场景溢出，会很难查出来。
• 数组、序列容器（std::vector 等）访问越界。
• 移位运算符右操作数大于等于左操作数类型长度，例如给 (unsigned) int 左/右移超过 31 位，给 (unsigned) long long 左/右移超过 63 位。
• C++20 以前左移的左操作数是负数。
• 读取未初始化变量（此类 UB 不会被 ubsan 检测到）。
• 对空指针、野指针等非法指针解引用（包括悬垂引用）。类似的还有操作失效的迭代器，见上文。
• 返回值非 void 类型的函数没有 return 返回值（无论此返回值有没有被读取）。main 函数除外。
• __builtin_ctz/clz(0) std::__lg(0)
• 不满足 C++ 具名要求。
  • 经典例子是 std::sort std::set 等模板的比较函数 comp 需要满足由 comp(a, b) 所定义的等价关系有传递性。这使得声明 std::set<double> 或对 double 类型数组排序为 UB，因为 nan 不小于也不大于任何数，所以它等价于任何数，然而 1 小于 2 也即 1 不等于 2，所以该等价关系没有传递性。不过实践中只要 std::set<double> 中不插入 nan 元素或 double 类型数组中不含 nan 元素，一般没有问题。
  • 莫队奇偶排序的比较函数中，若第一维所在块相同，比较第二维时不能写成 a[i].y<a[j].y^a[i].y/B&1，因为这等价于 a[i].y/B&1?a[i].y>=a[j].y:a[i].y<a[j].y，而正确写法应该是 a[i].y/B&1?a[i].y>a[j].y:a[i].y<a[j].y。
• 使用模板函数时不满足该函数对数据的要求。例如对一个无序的范围使用 std::lower_bound，或是传入的范围不合法。
• 同一内存上两个副作用间是无顺序的，例如 i=i++ 在 C++17 前。
• 某一内存上一个副作用和一个使用该内存中任意对象进行的值计算之间是无顺序的，例如 i+i++。这里需要注意的是 std::pair(f(), f())（f 为一个有副作用的函数，比如快读）不是 UB，但两个函数调用之间仍然顺序不确定。

致谢

• @UnyieldingTrilobite @Moeebius @gxy001 等大蛇和 uq 内众多群友长期以来的交流探讨。
• 因为奇奇怪怪的原因各种挂分/爆零为后人提供宝贵经验的 OI 前辈们。
• cppreference 的维护者们。

当然这篇文章肯定无法避免一定的错漏，希望大家及时反馈，有价值的内容我一定会及时补充。

Updated:

• @gxy001 指出 std::pair(f(), f()) 并非 UB。
• @MatrixGroup 指出 -Wall -Wextra 并不包含 -Wshadow 和 -Wconversion。