【1.8.2版本】回复“无敌函数库”
2026-08-14 14:40:57
发布于：浙江
注：GPT-5.6 Sol很贵的！请@Deep欠揍 | 深度欠揍仔细、全面修复Bug后再找我进行AI审查！
原帖 | 作者 | 回复@Deep欠揍 | 深度欠揍 | GPT-5.6 Sol技术支持
我已经把这 919 行源码按“实际编译 + 强制模板实例化 + 构造边界测试 + ASan/UBSan + 代码审计”检查了一遍。结论比较明确：
这份 1.8.2 版本目前仍然存在多处阻断级和严重正确性 Bug。尤其危险的是：当前空 main() 把大量模板问题隐藏起来了，所以“源码能编译”是一个假象。 源文件本身确实把主要库代码都定义好了，但 main() 没有真正调用这些组件。
我实际使用 GCC 14.2 / GNU++20 做了验证。
总体结论
| 等级 | 问题 | 实际后果 |
|---|---|---|
| P0 | sort<int> 一实例化就编译失败 |
排序库当前实际上不可用 |
| P0 | introsort_logic 的“两 run”分支下标基准错误 |
排错区间、污染区间外数据 |
| P0 | pivot 被 move 后继续拿原槽位交换 |
对 move-sensitive 类型直接丢元素 |
| P0/P1 | _gc() 用 char 表示 EOF |
UTF-8/0xFF/unsigned-char 平台全部存在错误 |
| P1 | read() 出错时先计算 _rbuf + (-1) |
非法指针状态，随后读取旧缓冲区 |
| P1 | scanf("%d %d") 错误消费输入 |
12 34 实测读成 12 4 |
| P1 | scanf 在 EOF + 格式空白时死循环 |
可直接 hang |
| P1 | read_f(".5") 解析错误 |
实测 .5→5，-.5→-5 |
| P1 | out(LLONG_MIN) 有符号溢出 |
UBSan 实测报错 |
| P1 | gcd 不支持负数 |
gcd(-6,4) 实测死循环 |
| P1 | getline 错误处理 CRLF |
第二次 getline 得到空行 |
| P1 | string 的 noexcept move 内部执行 new |
OOM 时直接 std::terminate |
| P1 | 自定义 vector 不销毁 pop/clear 的元素 |
资源生命周期严重错误 |
| P1 | write() 不处理 partial write/EINTR |
合法 POSIX 情况下静默丢输出 |
| P1/P2 | sqrt(x,n) 接受浮点 n，却使用整数 Newton 公式 |
非整数 n 数学上错误 |
| P2 | 23 个 GCC optimize 选项在 GCC 14.2 中无效 | “优化配置”大量实际没生效 |
| P2/部署风险 | 强制 avx512f |
不支持 AVX-512 的 CPU 可直接 SIGILL |
| P2 | 多个宏一使用就不能在 GCC 14.2 编译 | 潜伏型编译雷 |
| P2 | out(const char*) 每次都构造 string |
快速 I/O 反而产生堆分配 |
| P2 | merge_run 固定 T stk[4096] |
大 T 栈爆；string 每次 4096 次小分配 |
下面说关键问题。
1. sort() 当前实际上无法使用
最严重的问题首先不是排序错，而是模板实例化就编译失败。
这里：
vector<run<T>> rs;
rs.reserve(n);
int cnt=get_runs(a,n,&rs,cmp);
但是 get_runs() 要的是：
run<T>* rs
你传进去的是：
vector<run<T>>*
后面同样还有：
int id=best_pair(rs,cnt);
best_pair() 同样需要 run<T>*。源码位置：
我实际增加：
int a[65];
sort(a, 0, 64);
GCC 14.2 立即产生：
error: no matching function for call to
'get_runs(int*&, int&, std::vector<math::run<int> >*, ...)'
error: no matching function for call to
'best_pair(std::vector<math::run<int> >&, int&)'
所以这是确定性编译 Bug。
正确的最小修法不是单纯改 &rs，而应该真正把 vector 的逻辑 size 建立起来：
vector<run<T>> rs(n);
int cnt = get_runs(a, n, rs.data, cmp);
...
int id = best_pair(rs.data, cnt);
或者至少：
rs.resize(n);
int cnt = get_runs(a, n, rs.data, cmp);
只 reserve() 然后绕过 size() 写 capacity 内存，是非常差的接口设计，即使你这个自定义 vector 因为提前构造了 capacity 个对象而“碰巧可写”，也不应该依赖这种行为。
2. 修完上面的编译错误后，排序还有真正的数据破坏 Bug
introsort_logic() 的 cnt == 2 分支：
int pos=begin;
int len1=find_run(a,end-begin+1,pos-begin,cmp);
...
pos+=len1;
int len2=find_run(a,end-begin+1,pos-begin,cmp);
问题在于：
n、st 用的是子区间相对坐标，但是数组指针仍然传的是原始 a。
所以当：
begin != 0
时，它实际上从：
a[0]
开始分析，而不是：
a[begin]
源码就在这里。
我修掉前面的 powersort 编译问题以后，专门构造了 [10,29] 为两个 run 的测试。
结果这个函数把 a[30] 也卷入了 merge，不仅 [10,29] 没正确排序，还污染了排序区间外的数据。
这属于真正的数据完整性 Bug。
最小修复：
if (cnt == 2) {
int n = end - begin + 1;
int len1 = find_run(a + begin, n, 0, cmp);
int l1 = begin;
int r1 = begin + len1 - 1;
int l2 = r1 + 1;
int r2 = end;
merge_run(a, l1, r1, l2, r2, cmp);
return;
}
更好的办法是：第一次 run 扫描时直接保存 run boundary，不要随后重新扫描一遍。
3. pivot 的 move() 会直接丢失元素
这里是另一个非常隐蔽的严重问题：
T p=move(a[(l+h)>>1]);
swap(a[mid],a[l]);
对于 int：
move(int)
效果和复制差不多，所以测试可能永远发现不了。
但是对于真正有 move semantics 的对象：
T p = move(a[mid]);
以后：
a[mid]
已经是 moved-from 状态。
紧接着又：
swap(a[mid], a[l]);
于是 moved-from 对象被正式塞回待排序数组。
而真正的 pivot 现在只存在局部变量 p 中，后面又没有被放回数组。
我用一个 move 后把源对象置为 -7777777 的测试类型验证，排序结果出现：
0 1 2 ... 12 -7777777 14 ... 23
原值 13 消失。
也就是说：元素真的丢了。
如果你暂时接受“类型必须可复制”，最低成本修法是：
T p = a[mid];
swap(a[mid], a[l]);
如果你确实要支持 move-only 类型，则必须重新设计 partition，采用“hole partition”或者让 pivot 始终占据数组中的合法槽位。
不能把 pivot move 出去以后继续把那个槽位当正常对象交换。
4. _gc() 的返回类型设计错了
当前：
static inline char _gc()
但 EOF 定义：
#define EOF (-1)
这是经典错误。
字符输入函数如果需要表示：
所有 unsigned char 值 0..255
+
EOF
返回值至少应该是 int。
现在会造成两个问题。
第一，在 char 为 unsigned 的平台上：
return EOF;
会变成：
255
EOF 检测彻底失效。
第二，在 x86 GCC 默认 signed char 的环境里，UTF-8 字节通常 ≥ 128，会变成负数。
例如：
read_s()
里：
while (c <= 32)
UTF-8 中文字节变成负数后，也满足：
c <= 32
我实测输入：
中文 abc
read_s() 返回的是：
abc
前面的中文全部被当成“空白”跳掉了。
正确实现应该是：
static inline int _gc() {
if (_rptr == _rend) {
long n = read(0, _rbuf, sizeof(_rbuf));
if (n <= 0)
return EOF;
_rptr = _rbuf;
_rend = _rbuf + n;
}
return static_cast<unsigned char>(*_rptr++);
}
随后所有：
char c = _gc();
也应该改成：
int c = _gc();
直到最终真正写入 char 时再转换。
5. _gc() 的 read error 处理顺序还有一个独立 Bug
现在：
ssize_t bytes_read = read(...);
_rend = _rbuf + bytes_read;
_rptr = _rbuf;
if (bytes_read <= 0) return EOF;
如果：
read() == -1
你先做了：
_rbuf + (-1)
即形成数组首地址之前的非法指针状态。
更糟糕的是 _rend 已经被改坏。
我通过关闭 stdin 后调用两次 _gc() 实测得到：
第一次：EOF
第二次：0
也就是说，第一次错误以后，第二次开始读旧的静态缓冲区内容。
必须先判断：
if (bytes_read <= 0)
再更新 _rend。
对于 POSIX 环境还应该区分：
EINTR
并重试。
6. write() 可能部分写出，你现在直接把剩余数据丢了
当前：
write(1, _wbuf, _wptr - _wbuf);
_wptr = _wbuf;
POSIX write() 没有保证请求 N 字节一定返回 N。
它合法地可以：
要求写 65536
实际只写 8192
尤其在 pipe、socket、signal、nonblocking fd 等场景。
你的代码不检查返回值，随后直接：
_wptr = _wbuf;
后面的 57344 字节静默丢失。
应该实现 write_all()，循环直到全部写完，并处理 EINTR。
7. read_f() 对非常正常的小数解析错误
当前先一直找数字：
while (c < '0' || c > '9') {
if (c == '-') f = -1.00;
c = _gc();
}
所以：
.5
小数点被跳掉，然后发现 5，于是整数部分成为 5。
实测：
.5 -> 5.000
-.5 -> -5.000
源码：
另外：
1e3
也不支持科学计数法。
建议重新写状态机，明确顺序：
skip whitespace
→ optional sign
→ integer digits
→ optional '.'
→ fractional digits
→ optional e/E exponent
至少必须允许：
.5
-.5
+.5
1.
8. 你的 scanf() 是目前 I/O 中最危险的函数之一
当前：
scanf("%d %d", &a, &b)
输入：
12 34
我实际得到：
12 4
原因是 read_d() 已经把 12 后面的空格取走了。
随后格式串中的：
' '
又进入：
c = _gc();
while (c <= 32 && *fmt != '%') c = _gc();
这次 _gc() 读到的是：
3
因为 3 > 32，循环不执行，但这个 3 已经被无条件丢掉了。
所以下一个 %d 只剩：
4
更严重的是：
scanf(" ");
在 EOF 输入下会无限循环。
我用 timeout 实测确认会 hang。
这里不建议“小修”。
因为你的 read_d() 本身采用“把数字后的第一个 delimiter 也吃掉”的模式，而真正的格式扫描器需要 peek/unget 能力。
正确架构应该变成：
Scanner::peek()
Scanner::get()
Scanner::skip_space()
Scanner::read_int()
Scanner::read_float()
保留一个 one-character lookahead。
否则 scanf 的 literal matching、format whitespace 都无法正确实现。
另外还有一个严重 API 陷阱：
%s
你要求的是：
string*
而标准 scanf("%s") 要求：
char*
如果使用者按标准 scanf 习惯传 char*，这里会把它解释为 string*，属于潜在内存破坏。
所以如果不准备兼容标准 scanf，至少换名字，不要叫 scanf。
9. getline() 对 Windows CRLF 是错的
现在遇到：
'\r'
立即停止。
但是：
\r\n
里的 \n 还留在输入流。
因此：
first\r\nsecond\r\n
连续调用两次 getline，我实测：
A=first
B=
第二次直接读到上一次残留的 \n。
最简单的修复方式反而是只把 \n 当 delimiter：
while (c != '\n' && c != EOF) {
push(c);
c = _gc();
}
if (s.len && s.data[s.len - 1] == '\r') {
--s.len;
s.data[s.len] = '\0';
}
这样同时兼容 LF 和 CRLF。
10. out(LLONG_MIN) 仍然有 UB
你明显已经专门处理了：
LLONG_MIN
但处理方式仍然有 signed overflow：
ull _x=-(x+1)+1;
我用 UBSan 实测该路径直接报：
runtime error: negation of -9223372036854775808 cannot be represented
尤其你还启用了 Ofast，编译器更可以利用 signed-overflow UB 做激进优化。
建议完全在 unsigned 域求绝对值：
inline void out(ll x) {
if (x < 0) {
_pc('-');
ull ux = 0ULL - static_cast<ull>(x);
out(ux);
} else {
out(static_cast<ull>(x));
}
}
unsigned 算术的模运算是标准定义行为。
11. read_d() 同样无法正确读 LLONG_MIN
解析使用：
x = (x << 3) + (x << 1) + digit;
其中：
x
本身是 ll。
想读取：
-9223372036854775808
时，你必须先构造正的：
9223372036854775808
但它已经超过：
LLONG_MAX
所以在最终加符号之前就已经发生 signed overflow UB。
正确办法也是用 ull magnitude 累加，同时做 overflow 检测，最后根据符号转换。
12. gcd() 对负数会死循环
当前 binary gcd 默认假定：
a > 0
b > 0
但函数签名完全没有表达这个限制：
inline ll gcd(ll a, ll b)
实际：
gcd(-6, 4)
我运行 1 秒仍未结束，被 timeout 杀掉。
原因包括：
ctzll(a)
a >>= ...
对负数的位模式和算术右移进入完全不同的算法状态。
建议先转到 unsigned magnitude。
如果希望完整支持：
LLONG_MIN
最好让 gcd 内部甚至返回：
ull
因为：
gcd(LLONG_MIN, 0) = 2^63
本来就无法用正的 ll 表示。
另外：
lcm = a / gcd(a,b) * b;
仍然可能 signed overflow。
应该用：
__builtin_mul_overflow
或者 __int128 做检查。
13. sqrt(x,n) 的 API 和实现数学上不一致
声明：
lf sqrt(lf x, lf n)
意味着 n 可以是：
2.5
3.7
-1.2
但内部：
for (int i = 0; i < static_cast<int>(n) - 1; ++i)
却把指数截断成整数。
同时 Newton 更新公式仍然使用原始浮点：
(n - 1)
...
/ n
这已经不是任何正确的 n 次根 Newton 公式。
所以：
sqrt(16, 2.5)
没有明确数学正确性。
此外：
n == 0
直接：
return 0;
也是错误的，0 次根不是 0。
建议明确 API：
lf nth_root(lf x, int n)
并规定：
n <= 0 -> domain error / NaN
x < 0 && n even -> NaN
再增加最大迭代次数和相对误差判断，避免极端情况下无界循环。
14. 自定义 string 的 move 构造标成 noexcept，但里面执行 new
当前：
string(string&& other) noexcept {
...
other.data = new char[1];
}
move assignment 也一样。
这是错误的异常保证。
因为：
new char[1]
理论上会抛 std::bad_alloc。
而函数：
noexcept
意味着异常不能传播，只能：
std::terminate()
最简单修复：去掉 noexcept。
更好的修复是让 moved-from string：
data = nullptr;
len = 0;
capacity = 0;
并让其他成员函数支持 capacity==0 的 lazy initialization。
这样 move 才真正是 O(1) 且 noexcept。
15. 这个自定义 vector 的对象生命周期并不符合 vector 语义
你的 reserve()：
T* new_data = new T[new_cap];
会直接构造 new_cap 个 T。
然后：
new_data[i] = move(data[i]);
这意味着 reserve(1000000) 不是“保留原始内存”，而是真的默认构造一百万个 T。
随后：
pop_back() { sz--; }
clear() { sz = 0; }
都没有析构已经删除的元素。
比如：
vector<string>
pop_back() 后那个 string 的内部资源仍然活着，直到整块 capacity 被 delete[]。
所以资源不会按 vector 语义及时释放。
此外它要求 T：
必须 default-constructible
必须 move-assignable
而真正 vector reserve 不需要把 capacity 部分全部构造出来。
如果要做通用容器，应使用：
raw storage
+ placement new / construct_at
+ 显式析构
否则建议不要叫 vector，明确这是“预构造数组容器”。
16. 往 namespace std 里面重新定义 vector/string/pair 是非常危险的
你从这里开始：
namespace std {
随后定义：
move
forward
pair
vector
string
...
标准 C++ 不允许程序随意向 std namespace 添加这些定义。
这意味着代码本质上不能和标准库正常共存。
例如将来只要：
#include <string>
#include <vector>
就会发生冲突/重定义。
前面自己定义：
typedef unsigned long long size_t;
typedef long long ssize_t;
也存在同样问题。
建议全部改成：
namespace fast {
template<class T> struct vector;
struct string;
}
然后：
fast::vector
fast::string
不要冒充 std。
17. printf() 并不具备 printf 语义，而且存在非常明显的错误
我实际执行：
printf("%.2f|%.2f|%lld\n", 0.0, 1.999, 123LL);
结果：
0|1.99|123ld
而不是应有的类似：
0.00|2.00|123
原因有三个。
write_p() 对 0.0 直接：
_pc('0');
return;
完全忽略 precision。
浮点输出完全不做 rounding，只做 truncation。
而 %lld 根本没有实现；第一个 %l 直接消费参数，然后剩余 "ld" 被当普通字符输出。
如果它只是“快速的自定义格式器”，建议改名。
如果确实想叫 printf，则至少实现：
%d
%u
%lld
%llu
%f
%s
%c
%%
并正确处理 precision、rounding 和 argument type。
18. merge_run() 的固定 T stk[4096] 很危险
这里：
const int SL=4096;
T stk[SL];
对 int 大概是 16 KiB，问题不大。
但模板是：
template<typename T>
所以如果：
sizeof(T) = 1024
一次函数调用就是：
4 MiB stack
足够触发栈溢出。
更讽刺的是，对你自己的 string：
string()
会执行：
new char[1]
因此：
T stk[4096]
在 T=string 时意味着每次 merge 默认构造 4096 个 string，也就是约 4096 次微型 heap allocation。
这和这份代码拼命堆 GCC 优化 flag 的目标完全背道而驰。
19. GCC pragma 本身存在大量无效配置
第一行 optimize pragma 非常长。
在 GCC 14.2 上，我实际得到 23 种不同的 bad option，例如：
-ffgraphite
-fflto
-ffno-stack-protector
-ffno-omit-frame-pointer
-fftree-parallelize-loops=4
-ffuse-linker-plugin
-fipa-devirt
-fipa-jump-function
...
其中不少原因是 #pragma GCC optimize() 会自行转成 -f...，而字符串本身又写了一个 f，导致：
fno-stack-protector
最终变成类似：
-ffno-stack-protector
所以实际上根本没有启用。
而且你同时存在：
omit-frame-pointer
fno-omit-frame-pointer
设计意图本身也冲突。
这类“把几十个优化 flag 全部堆上去”的方式收益通常极低，却会显著提高不可预测性。
建议首先退化到：
#pragma GCC optimize("O3")
必要时经过 benchmark 后再单独增加已经证明有效的选项。
20. 全局 AVX-512 target 是部署炸弹
#pragma GCC target("avx512f", ...)
意味着 GCC 可以合法地为后续代码生成 AVX-512 指令。
编译机器支持不代表运行机器支持。
如果最终二进制被放到只有 AVX2 的 CPU 上：
SIGILL
Illegal instruction
是完全可能的。
如果这是提交到 CPU 型号固定的 OJ，可以明确依赖。
如果是一般库代码，应该删除 AVX-512 强制 target，或者进行 runtime dispatch：
__builtin_cpu_supports("avx512f")
然后只让 AVX-512 专用函数使用对应 target attribute。
21. 有几个宏目前属于“一展开就炸”
源码定义了：
#define fnlikely(cond) __builtin_unpredictable((cond))
#define roundll(x) __builtin_roundll((x))
#define types_compatible_p(...) ...
#define assume(cond) __builtin_assume((cond))
当前 main() 没调用，所以没有暴露。
我在 GCC 14.2 分别强制展开，确认：
__builtin_unpredictable
__builtin_assume
__builtin_roundll
都会出现“不存在/未声明”的编译错误。
types_compatible_p 这个宏写法本身对 type 参数加括号：
((type1), (type2))
也无法按类型 builtin 的方式工作。
因此这些是潜伏型编译 Bug。
例如 roundll 真正可能想写的是：
__builtin_llround(x)
而不是：
__builtin_roundll(x)
22. out(const char*) 白白进行 heap allocation
当前：
inline void out(const char* val) {
string s=val;
out(s);
}
所以每次：
out("hello");
都：
strlen
new[]
memcpy
输出
delete[]
这是快速 I/O 中非常不应该发生的事情。
直接：
inline void out(const char* p) {
if (!p) return;
while (*p)
_pc(*p++);
}
即可。
out(bool) 调 out("true") 时也不再产生堆分配。
23. 输出没有可靠的自动 flush
整个设计依赖：
_return();
手动执行。
如果业务代码写：
cout << "error";
return 0;
那么 _return() 不会执行，缓冲区未满的话 "error" 直接丢失。
交互题也很危险，因为：
'\n'
并不会自动 flush，可能导致双方互相等待。
至少应该提供：
flush()
并用 RAII 确保正常程序退出时 flush。
建议的修复优先级
我建议不要继续先做微观性能优化。当前真正应该优先修复的是：
第一批必须立即修： powersort 编译错误、cnt==2 子区间错误、pivot move 丢元素、_gc() 改 int、read error 状态、scanf 重写、LLONG_MIN、负数 gcd。
第二批正确性修复： read_f、CRLF、partial write、lcm overflow、sqrt API、vector/string 生命周期。
第三批再做工程与性能： 移出 namespace std、清理 GCC pragma、移除全局 AVX-512、修复错误 builtins、去掉 out(const char*) 分配、重构 merge 临时缓冲。
以目前状态来说，源码开头“修复绝大部分 P0、P1 级 BUG”这个评价还偏乐观：至少排序主入口的模板实例化、子区间排序以及 move 类型排序三个问题，本身就足以阻止它作为通用排序库使用。
最值得先改的是排序和 I/O 两大块；它们目前不是“极端输入才出问题”，而是已经存在可以用很小测试用例稳定复现的错误。
有帮助，赞一个