原帖 | 作者 | 回复@DEEP欠揍 | 深度欠揍 | GPT-5.6 SOL技术支持
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
我把这 911 行代码按“可复现的错误结果 → 内存安全/UB → 泛型语义 → 可移植性”四层审了一遍，并实际做了最小测试、随机测试和 ASan/UBSan 验证。结论很明确：
这份代码当前不是只有几个边角 Bug，而是存在多处 P0/P1 级缺陷。尤其 sort/powersort、string::substr、scanf/printf、gcd 和 out(bool)，在特定输入下会确定性地产生错误结果、越界、UB，甚至编译失败。
原来的 main() 只输出一个 0，所以绝大多数模板和重载根本没有被真正实例化/执行，这掩盖了很多问题。
一、最严重的问题总览
严重度 Bug 实际后果 P0 powersort 的 run rs[2048] 无边界保护 栈越界、内存破坏 P0 scanf("%d") 用 ll* 取参数 给 int* 时直接覆盖后 4 字节 P0 string::substr() 把参数 len 和成员 len 混淆 巨额分配、越界读取、错误结果 P0 introsort 把 pivot move 出数组却不放回 对真正 move-aware 类型直接丢元素 P0 string += string 自连接使用重叠 memcpy UB，ASan 已确认 P1 两元素 sort() 直接 return [2,1] 排完仍是 [2,1]
P1 introsort cnt==2 时 find_run 坐标系错误 非零 begin 子区间可能没有排完 P1 64 位 gcd() 却调用 32 位 ctz 64 位整数 GCD 算错，并触发 UB P1 out(bool) 实际递归调用自己 使用后可能直接编译失败/无限递归 P1 printf("%d") 用 va_arg(..., ll) Varargs UB，负整数已经实测输出错误 P1 _gc() 用 char 表示 EOF EOF 与 0xFF 混淆，unsigned-char 平台失效 P1 read() 出错后先做 _rbuf + bytes_read
bytes_read == -1 时已经产生非法指针运算 P1 out(ll) 对 LLONG_MIN 做 -x signed overflow，UB P2 自制 vector/string/pair 放进 namespace std 标准层面未定义行为，加入标准头极易冲突 P2 强制 AVX-512 不支持 AVX-512 的机器可能 SIGILL P2 大量错误的 GCC optimize 参数 警告泛滥，部分优化根本没有生效
下面逐个说。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. STRING::SUBSTR() 是确定性的严重逻辑错误
代码：
这里函数参数也叫 len，把成员变量 this->len 完全遮蔽掉了。
例如：
正确结果应该是 "bc"。
你的代码：
最后得到 "b"。
更严重的是：
默认 len = SIZE_MAX，于是：
随后可能尝试申请一个接近 SIZE_MAX 的缓冲区。
正确写法
这个 Bug 必须优先修。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. POWERSORT() 存在真实的栈越界
这里：
但 get_runs() 完全没有检查 cnt < 2048：
这是 P0 内存安全 Bug。
我用 5000 个交替元素直接测试 powersort：
ASan 明确报告：
最坏情况下游程数量可以是 O(n)，你不能用固定 2048。
修复
最简单：
或者使用修好后的动态容器。
如果想精确一点，按照当前 find_run() 的特性，可以申请约：
但我更建议先申请 n，正确性优先。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. SORT() 连两个元素都排不了
入口：
你的整个排序体系显然把 end 当作闭区间端点。
那么：
有：
于是直接 return。
我实际测试结果就是 [2,1] 不变。
修复
不是：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. INTROSORT 的“双游程”分支坐标系错了
这里：
而 find_run 的接口是：
其中 n 是相对于数组 a 的长度。
你传入：
如果递归区间是：
则：
一进 find_run()：
也就是直接返回 1。
随后只合并很小的一部分，然后：
整个子区间可能仍然没有排序。
我做非零 begin 的随机测试，确实很快就出现了未排序结果。
修复
统一使用相对坐标：
更好的设计是：第一次扫描 run 时就记录两个 run 的边界，根本不要再重新调用 find_run()。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. INTROSORT 的 PIVOT 对非平凡类型会“丢元素”
最危险的一段之一：
对 int 来说，所谓 move 本质还是 copy，因此碰巧没事。
但对真正具有 move 语义的类型：
之后 a[mid] 已经是 moved-from 状态。
然后：
交换的是“已经被掏空”的 a[mid]。
pivot 真值只剩在局部变量 p 里面。
后面的 partition 从来没有把 p 放回数组。
函数结束：
这个元素就彻底没了。
我专门构造了一个 move 后把源对象设成 -999999 的类型。
排序前元素和：
排序后：
这不是排序，是数据被破坏了。
最小修复
鉴于你的其他容器本来就大量要求可复制类型，最直接：
不要 move pivot。
如果你真正想支持 move-only 类型，则必须重新设计 partition，用“hole partition”等方法，在最后把 pivot 明确 move 回数组。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. GCD(LL,LL) 实际只正确处理了低 32 位 TRAILING-ZERO
你定义：
但 gcd(ll,ll) 里面却是：
__builtin_ctz 的操作数是 32 位 unsigned int。
也就是说你的 64 位 ll 被截成低 32 位。
我实测：
正确结果应该：
你的函数返回：
同时 UBSan 报：
因为高位有数据，但低 32 位全是 0。
至少改成
不过负数仍有问题。
更加正确的方案是整个 binary GCD 使用 ull 绝对值：
再全部调用：
这样还能安全处理 LLONG_MIN 的 magnitude。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. SCANF("%D", &INT) 会直接破坏内存
这里：
如果用户按照 scanf 的常识：
实际传进去的是：
你却：
然后写 8 字节。
我用：
测试，初始：
输入 123 后 guard 被改成：
也就是确定的相邻内存覆盖。
修复
如果函数名字叫 scanf，就遵循 scanf 类型规则：
如果你就是想规定 %d 表示 ll，那至少不要把函数叫 scanf，例如：
否则这个接口非常危险。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. 你的 SCANF 多参数解析逻辑本身也是错的
例如：
输入：
我实测得到：
原因是 read_d() 在读完 12 后已经通过：
把后面的空格吃掉了。
然后 scanf 解析格式字符串中的空格时又：
于是把第二个数字的 '3' 又吃掉。
最后第二个 read_d() 只能读到：
因此，当前 scanf 的 token reader 与 format parser 都在消费分隔符，架构上发生“双重消费”。
修复原则
二选一：
方案 A： read_d() 遇到非数字时不要真正消费它，需要 unget。
方案 B：更推荐： scanf 自己完全控制字符流，整数解析函数接收首字符，不让底层 tokenizer 偷吃后面的字符。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
9. PRINTF("%D") 的 VA_ARG 类型也是 UB
代码：
但调用：
C/C++ varargs 实际传的是：
你却用：
这是未定义行为。
我在当前 x86-64 环境实际测试：
输出：
而不是：
另外：
对于：
也是错的，因为 * 精度参数是 int。
正确方向
然后完整解析：
对应正确的 vararg 类型。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
10. OUT(BOOL) 有一个很隐蔽的递归重载 BUG
现在的顺序：
关键问题：
在编译 out(bool) 函数体时：
还没有声明。
表达式：
类型是：
当前候选中，const char* -> bool 是标准转换，而：
需要用户定义转换。
因此编译器选择：
自己调用自己。
而你又给它：
我实际实例化：
GCC 直接报：
即使去掉 always_inline，也很可能变成无限递归。
修复
最简单直接：
或者把：
声明放到 out(bool) 前面。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
11. STRING += STRING 自连接是 UB
代码：
如果：
那么 other 就是 *this。
源区间和目标区间重叠。
而 memcpy 不允许重叠。
ASan 实测直接报告：
修复
专门处理 self append：
注意复制 old_len 即可，最后自己写 '\0'。
operator+=(const char*) 还有类似的 alias 风险，例如：
最稳妥的是先构造临时副本。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
12. _GC() 在 READ() 返回 -1 时，已经先发生 UB
代码顺序：
如果：
你先执行：
这已经在数组对象范围之外构造了指针。
必须先判断。
正确写法
这里还有第二个关键修改：
改成：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
13. EOF 不应该用 CHAR 承载
现在：
却返回：
标准 I/O 为什么 getc() 返回 int？
就是因为必须同时表示：
你的设计导致：
* char 为 unsigned 的平台，EOF 变成 255；
* 即使 signed char，也无法区分真正输入字节 0xFF 和 EOF。
所有这些：
都应该改成：
最后真正存进 string 时：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
14. OUT(LL) 在 LLONG_MIN 上 UB
对于：
正数 9223372036854775808 无法放进 long long。
于是：
发生 signed overflow。
修复
用无符号 magnitude：
然后按照 ull 输出。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
15. 你的自制 VECTOR 不是合法的 STD::VECTOR 语义
例如：
对于有析构函数的 T，元素根本没有销毁。
更根本的问题是：
已经把整个 capacity 的 T 全部构造出来了。
因此你不能简单在 pop_back() 里：
因为最后：
还会再次析构那个对象。
也就是说，如果你希望它具有真正 std::vector<T> 的泛型语义，当前内存模型本身就需要重写：
而不是 new T[capacity]。
另外：
根本不做 bounds checking，也不应该叫 at()。
两种选择
如果这是竞赛代码，只处理 POD/trivial 类型：
把它改名：
明确限制类型。
如果要仿造真正 vector，则需要重写对象生命周期管理。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
16. 所有这些类型不应该定义到 NAMESPACE STD
你直接：
这是非常不应该做的。
用户程序自行向 std 添加这些类型，属于标准保留命名空间的违规使用；而且以后只要：
就会产生重定义或其他不可预测问题。
修复
全部换：
然后：
不要冒充标准库。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
17. GCC 优化 PRAGMA 本身大量写错
最开头那串：
我直接用 GCC 14.2 编译原文件，出现大量：
原因之一是 pragma 中部分选项的写法导致 GCC 再补一个 -f。
另外 LTO、linker plugin 一类本来就不适合作为这种 function optimization pragma 使用。
结果是：几乎每个函数都被这些错误 option 污染，真正有价值的编译警告反而被几百行垃圾 warning 淹没。
建议直接砍到：
足够了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
18. 强制 AVX-512 会让程序在别的 CPU 上直接崩
你写了：
这不是“CPU 支持就自动使用”。
这是在告诉编译器：
> 可以假定运行 CPU 支持 AVX-512。
如果拿到没有 AVX-512 的机器运行，编译器恰巧生成相应指令：
因此除非判题机 CPU 型号完全确定，否则这是运行时 Bug。
竞赛环境通常宁可：
甚至干脆不要写 target。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
19. FNLIKELY 在 GCC 14.2 直接不能用
你定义：
我实际实例化：
GCC 14.2 直接：
目前之所以原文件能编译，只是这个宏根本没用到。
如果针对 GCC：
即可。
不要为了不存在的微优化引入编译错误。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
20. 还有几处应该一起改
string 的 move constructor / move assignment 标了：
内部却执行：
new 可以抛异常；在 noexcept 函数里会直接 std::terminate。要么去掉 noexcept，要么设计无需分配的 moved-from 状态。
getline() 遇到 \r\n 时读到 \r 就停，却把 \n 留在流里：下一次 getline() 会马上遇到 \n，得到空行。
_pc() / _return() 直接假设：
但系统调用允许 partial write；目前部分写入会造成输出静默丢失。
read_d() 累积：
对超出 long long 的输入会发生 signed overflow，也属于 UB。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
建议的修复优先级
如果你准备继续维护这个 1.8.0 版本，我建议不要先碰优化，修复顺序应当是：
第一批必须立即修：
第二批做架构修正：
最后才是性能：
现在这份代码最大的性能问题其实不是“还不够快”，而是优化层叠得非常激进，但正确性基础还没有完全站稳。特别是排序：我已经实际复现了两元素不排序、非零子区间失败、move 类型丢元素以及 powersort 栈越界；这些都应该在任何进一步优化之前解决。
如果只让我挑 三个最致命的 Bug，就是：powersort 的 rs[2048] 越界、scanf("%d") 的 8 字节内存覆盖、以及 introsort move pivot 后不归还导致元素丢失。
