【1.8.0版本】回复“无敌函数库”
2026-08-13 13:48:19
发布于：浙江
原帖 | 作者 | 回复@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() 是确定性的严重逻辑错误
代码：
inline string substr(size_t pos, size_t len = (size_t)-1) const {
if (pos >= len) return string();
size_t actual_len = len - pos;
if (len < actual_len) actual_len = len;
...
}
这里函数参数也叫 len，把成员变量 this->len 完全遮蔽掉了。
例如：
string s("abc");
s.substr(1, 2);
正确结果应该是 "bc"。
你的代码：
actual_len = 2 - 1 = 1;
最后得到 "b"。
更严重的是：
s.substr(1);
默认 len = SIZE_MAX，于是：
actual_len = SIZE_MAX - 1;
随后可能尝试申请一个接近 SIZE_MAX 的缓冲区。
正确写法
string substr(size_t pos, size_t count = (size_t)-1) const {
if (pos >= this->len)
return string();
size_t actual_len = this->len - pos;
if (count < actual_len)
actual_len = count;
string result;
delete[] result.data;
result.capacity = actual_len + 1;
result.data = new char[result.capacity];
memcpy(result.data, data + pos, actual_len);
result.data[actual_len] = '\0';
result.len = actual_len;
return result;
}
这个 Bug 必须优先修。
2. powersort() 存在真实的栈越界
这里：
const int MR=2048;
run<T> rs[MR];
int cnt=get_runs(a,n,rs,cmp);
但 get_runs() 完全没有检查 cnt < 2048：
while(i<n){
int len=find_run(...);
rs[cnt].l=i;
rs[cnt].r=i+len-1;
cnt++;
i+=len;
}
这是 P0 内存安全 Bug。
我用 5000 个交替元素直接测试 powersort：
1 0 1 0 1 0 ...
ASan 明确报告：
ERROR: AddressSanitizer: stack-buffer-overflow
rs[2048]
最坏情况下游程数量可以是 O(n)，你不能用固定 2048。
修复
最简单：
run<T>* rs = new run<T>[n];
int cnt = get_runs(a, n, rs, cmp);
// ...
delete[] rs;
或者使用修好后的动态容器。
如果想精确一点，按照当前 find_run() 的特性，可以申请约：
(n + 1) / 2 + 1
但我更建议先申请 n，正确性优先。
3. sort() 连两个元素都排不了
入口：
void sort(T a[], int begin, int end, Compare cmp = Compare()) {
if(end-begin<2)return;
你的整个排序体系显然把 end 当作闭区间端点。
那么：
int a[] = {2,1};
sort(a,0,1);
有：
end - begin == 1
于是直接 return。
我实际测试结果就是 [2,1] 不变。
修复
if (begin >= end) return;
不是：
if (end - begin < 2) return;
4. introsort 的“双游程”分支坐标系错了
这里：
int pos=begin;
int len1=find_run(a,end-begin+1,pos,cmp);
而 find_run 的接口是：
find_run(T a[], int n, int st, ...)
其中 n 是相对于数组 a 的长度。
你传入：
a = 原数组
n = end-begin****t = begin
如果递归区间是：
begin = 100
end = 150
则：
n = 51
st = 100
一进 find_run()：
if(st>=n-1)return 1;
也就是直接返回 1。
随后只合并很小的一部分，然后：
return;
整个子区间可能仍然没有排序。
我做非零 begin 的随机测试，确实很快就出现了未排序结果。
修复
统一使用相对坐标：
int n = end - begin + 1;
int len1 = find_run(a + begin, n, 0, cmp);
int len2 = find_run(a + begin, n, len1, cmp);
merge_run(
a,
begin,
begin + len1 - 1,
begin + len1,
begin + len1 + len2 - 1,
cmp
);
更好的设计是：第一次扫描 run 时就记录两个 run 的边界，根本不要再重新调用 find_run()。
5. introsort 的 pivot 对非平凡类型会“丢元素”
最危险的一段之一：
T p=move(a[mid]);
swap(a[mid],a[l]);
对 int 来说，所谓 move 本质还是 copy，因此碰巧没事。
但对真正具有 move 语义的类型：
T p = move(a[mid]);
之后 a[mid] 已经是 moved-from 状态。
然后：
swap(a[mid],a[l]);
交换的是“已经被掏空”的 a[mid]。
pivot 真值只剩在局部变量 p 里面。
后面的 partition 从来没有把 p 放回数组。
函数结束：
p.~T();
这个元素就彻底没了。
我专门构造了一个 move 后把源对象设成 -999999 的类型。
排序前元素和：
217
排序后：
-999791
这不是排序，是数据被破坏了。
最小修复
鉴于你的其他容器本来就大量要求可复制类型，最直接：
T p = a[mid];
swap(a[mid], a[l]);
不要 move pivot。
如果你真正想支持 move-only 类型，则必须重新设计 partition，用“hole partition”等方法，在最后把 pivot 明确 move 回数组。
6. gcd(ll,ll) 实际只正确处理了低 32 位 trailing-zero
你定义：
#define ctz(x) __builtin_ctz((x))
#define ctzll(x) __builtin_ctzll((x))
但 gcd(ll,ll) 里面却是：
ll shift = ctz(a | b);
a >>= ctz(a);
b >>= ctz(b);
__builtin_ctz 的操作数是 32 位 unsigned int。
也就是说你的 64 位 ll 被截成低 32 位。
我实测：
gcd(1LL << 40, 1LL << 41)
正确结果应该：
1099511627776 // 2^40
你的函数返回：
4294967296 // 2^32
同时 UBSan 报：
runtime error: passing zero to ctz()
因为高位有数据，但低 32 位全是 0。
至少改成
int shift = ctzll((ull)a | (ull)b);
a >>= ctzll((ull)a);
b >>= ctzll((ull)b);
不过负数仍有问题。
更加正确的方案是整个 binary GCD 使用 ull 绝对值：
inline ull magnitude(ll x) {
return x < 0 ? 0ULL - (ull)x : (ull)x;
}
再全部调用：
__builtin_ctzll()
这样还能安全处理 LLONG_MIN 的 magnitude。
7. scanf("%d", &int) 会直接破坏内存
这里：
}else if (*fmt == 'd') {
ll* val = va_arg(args, ll*);
*val = read_d();
}
如果用户按照 scanf 的常识：
int x;
scanf("%d",&x);
实际传进去的是：
int*
你却：
va_arg(args,ll*)
然后写 8 字节。
我用：
struct {
int x;
unsigned guard;
}
测试，初始：
guard = 0xDEADBEEF
输入 123 后 guard 被改成：
0
也就是确定的相邻内存覆盖。
修复
如果函数名字叫 scanf，就遵循 scanf 类型规则：
%d -> int*
%ld -> long*
%lld -> long long*
%f -> float*
%lf -> double*
如果你就是想规定 %d 表示 ll，那至少不要把函数叫 scanf，例如：
fast_scan(...)
否则这个接口非常危险。
8. 你的 scanf 多参数解析逻辑本身也是错的
例如：
scanf("%d %d", &a, &b);
输入：
12 34
我实测得到：
12 4
原因是 read_d() 在读完 12 后已经通过：
c = _gc();
把后面的空格吃掉了。
然后 scanf 解析格式字符串中的空格时又：
c = _gc();
于是把第二个数字的 '3' 又吃掉。
最后第二个 read_d() 只能读到：
4
因此，当前 scanf 的 token reader 与 format parser 都在消费分隔符，架构上发生“双重消费”。
修复原则
二选一：
方案 A： read_d() 遇到非数字时不要真正消费它，需要 unget。
方案 B：更推荐： scanf 自己完全控制字符流，整数解析函数接收首字符，不让底层 tokenizer 偷吃后面的字符。
9. printf("%d") 的 va_arg 类型也是 UB
代码：
case 'd':
case 'i':
out((ll)va_arg(args, ll));
但调用：
printf("%d", -1);
C/C++ varargs 实际传的是：
int
你却用：
va_arg(args,long long)
这是未定义行为。
我在当前 x86-64 环境实际测试：
printf("%d", -1);
输出：
4294967295
而不是：
-1
另外：
precision = va_arg(args, ll);
对于：
"%.*f"
也是错的，因为 * 精度参数是 int。
正确方向
case 'd':
case 'i':
out((ll)va_arg(args, int));
break;
然后完整解析：
%ld
%lld
%u
%lu
%llu
对应正确的 vararg 类型。
10. out(bool) 有一个很隐蔽的递归重载 Bug
现在的顺序：
inline void out(const string& a) { ... }
inline void out(const bool& val) {
out(val?"true":"false");
}
inline void out(const char& val) { ... }
inline void out(const char* val) { ... }
关键问题：
在编译 out(bool) 函数体时：
out(const char*)
还没有声明。
表达式：
val ? "true" : "false"
类型是：
const char*
当前候选中，const char* -> bool 是标准转换，而：
const char* -> string
需要用户定义转换。
因此编译器选择：
out(bool)
自己调用自己。
而你又给它：
__attribute__((always_inline))
我实际实例化：
out(true);
GCC 直接报：
inlining failed in call to always_inline
function not considered for inlining
即使去掉 always_inline，也很可能变成无限递归。
修复
最简单直接：
inline void out(const bool& val) {
if (val) {
_pc('t'); _pc('r'); _pc('u'); _pc('e');
} else {
_pc('f'); _pc('a'); _pc('l'); _pc('s'); _pc('e');
}
}
或者把：
out(const char*)
声明放到 out(bool) 前面。
11. string += string 自连接是 UB
代码：
memcpy(data + len, other.data, other.len + 1);
如果：
string s("abc");
s += s;
那么 other 就是 *this。
源区间和目标区间重叠。
而 memcpy 不允许重叠。
ASan 实测直接报告：
ERROR: AddressSanitizer: memcpy-param-overlap
修复
专门处理 self append：
if (this == &other) {
size_t old_len = len;
// ensure capacity >= old_len * 2 + 1
memmove(data + old_len, data, old_len);
len = old_len * 2;
data[len] = '\0';
return *this;
}
注意复制 old_len 即可，最后自己写 '\0'。
operator+=(const char*) 还有类似的 alias 风险，例如：
s += s.c_str() + 1;
最稳妥的是先构造临时副本。
12. _gc() 在 read() 返回 -1 时，已经先发生 UB
代码顺序：
ssize_t bytes_read = read(...);
_rend = _rbuf + bytes_read;
_rptr = _rbuf;
if (unlikely(bytes_read <= 0))
return EOF;
如果：
read() == -1
你先执行：
_rbuf - 1
这已经在数组对象范围之外构造了指针。
必须先判断。
正确写法
static inline int _gc() {
if (unlikely(_rptr == _rend)) {
long n = read(0, _rbuf, sizeof(_rbuf));
if (unlikely(n <= 0)) {
_rptr = _rend = _rbuf;
return EOF;
}
_rptr = _rbuf;
_rend = _rbuf + n;
}
return (unsigned char)*_rptr++;
}
这里还有第二个关键修改：
char
改成：
int
13. EOF 不应该用 char 承载
现在：
static inline char _gc()
却返回：
EOF // -1
标准 I/O 为什么 getc() 返回 int？
就是因为必须同时表示：
0..255
EOF (-1)
你的设计导致：
char为 unsigned 的平台，EOF变成 255；- 即使 signed char，也无法区分真正输入字节
0xFF和 EOF。
所有这些：
char c = _gc();
if(c == EOF)
都应该改成：
int c = _gc();
最后真正存进 string 时：
(char)c
14. out(ll) 在 LLONG_MIN 上 UB
if (x < 0) {
_pc('-');
x = -x;
}
对于：
x = LLONG_MIN
正数 9223372036854775808 无法放进 long long。
于是：
-x
发生 signed overflow。
修复
用无符号 magnitude：
ull u;
if (x < 0) {
_pc('-');
u = 0ULL - (ull)x;
} else {
u = (ull)x;
}
然后按照 ull 输出。
15. 你的自制 vector 不是合法的 std::vector 语义
例如：
void pop_back() {
if (sz > 0) sz--;
}
void clear() {
sz = 0;
}
对于有析构函数的 T，元素根本没有销毁。
更根本的问题是：
new T[new_cap]
已经把整个 capacity 的 T 全部构造出来了。
因此你不能简单在 pop_back() 里：
data[--sz].~T();
因为最后：
delete[] data;
还会再次析构那个对象。
也就是说，如果你希望它具有真正 std::vector<T> 的泛型语义，当前内存模型本身就需要重写：
raw storage
+ placement new
+ 显式 destructor
而不是 new T[capacity]。
另外：
T& at(size_t index) { return data[index]; }
根本不做 bounds checking，也不应该叫 at()。
两种选择
如果这是竞赛代码，只处理 POD/trivial 类型：
把它改名：
fast_vector
明确限制类型。
如果要仿造真正 vector，则需要重写对象生命周期管理。
16. 所有这些类型不应该定义到 namespace std
你直接：
namespace std {
...
struct vector
...
struct string
这是非常不应该做的。
用户程序自行向 std 添加这些类型，属于标准保留命名空间的违规使用；而且以后只要：
#include <string>
#include <vector>
#include <utility>
就会产生重定义或其他不可预测问题。
修复
全部换：
namespace fast {
...
}
然后：
using fast::string;
using fast::vector;
using fast::pair;
不要冒充标准库。
17. GCC 优化 pragma 本身大量写错
最开头那串：
#pragma GCC optimize("...,flto,...,fno-stack-protector,...")
我直接用 GCC 14.2 编译原文件，出现大量：
bad option '-fflto'
bad option '-ffno-stack-protector'
bad option '-ffgraphite'
...
原因之一是 pragma 中部分选项的写法导致 GCC 再补一个 -f。
另外 LTO、linker plugin 一类本来就不适合作为这种 function optimization pragma 使用。
结果是：几乎每个函数都被这些错误 option 污染，真正有价值的编译警告反而被几百行垃圾 warning 淹没。
建议直接砍到：
#pragma GCC optimize("O3")
足够了。
18. 强制 AVX-512 会让程序在别的 CPU 上直接崩
你写了：
#pragma GCC target(
"avx512f",
"avx512vl",
...
)
这不是“CPU 支持就自动使用”。
这是在告诉编译器：
可以假定运行 CPU 支持 AVX-512。
如果拿到没有 AVX-512 的机器运行，编译器恰巧生成相应指令：
SIGILL / Illegal instruction
因此除非判题机 CPU 型号完全确定，否则这是运行时 Bug。
竞赛环境通常宁可：
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
甚至干脆不要写 target。
19. fnlikely 在 GCC 14.2 直接不能用
你定义：
#define fnlikely(cond) __builtin_unpredictable((cond))
我实际实例化：
fnlikely(1)
GCC 14.2 直接：
error: '__builtin_unpredictable' was not declared in this scope
目前之所以原文件能编译，只是这个宏根本没用到。
如果针对 GCC：
#define fnlikely(cond) (cond)
即可。
不要为了不存在的微优化引入编译错误。
20. 还有几处应该一起改
string 的 move constructor / move assignment 标了：
noexcept
内部却执行：
new char[1];
new 可以抛异常；在 noexcept 函数里会直接 std::terminate。要么去掉 noexcept，要么设计无需分配的 moved-from 状态。
getline() 遇到 \r\n 时读到 \r 就停，却把 \n 留在流里：下一次 getline() 会马上遇到 \n，得到空行。
_pc() / _return() 直接假设：
write(fd,p,n) == n
但系统调用允许 partial write；目前部分写入会造成输出静默丢失。
read_d() 累积：
x = x * 10 + digit;
对超出 long long 的输入会发生 signed overflow，也属于 UB。
建议的修复优先级
如果你准备继续维护这个 1.8.0 版本，我建议不要先碰优化，修复顺序应当是：
第一批必须立即修：
substr
powersort rs 越界
sort 两元素判断
introsort cnt==2 坐标
pivot move 丢元素
scanf/printf varargs
gcd ctz -> ctzll
out(bool)
string self +=
_gc EOF/read error
LLONG_MIN 输出
第二批做架构修正：
namespace std -> 自有 namespace
vector 对象生命周期
string move noexcept
partial write
CRLF getline
整数解析 overflow
最后才是性能：
删掉那一整串 pragma
做 benchmark
只保留真正有收益的 O3 / target
现在这份代码最大的性能问题其实不是“还不够快”，而是优化层叠得非常激进，但正确性基础还没有完全站稳。特别是排序：我已经实际复现了两元素不排序、非零子区间失败、move 类型丢元素以及 powersort 栈越界；这些都应该在任何进一步优化之前解决。
如果只让我挑 三个最致命的 Bug，就是：powersort 的 rs[2048] 越界、scanf("%d") 的 8 字节内存覆盖、以及 introsort move pivot 后不归还导致元素丢失。
有帮助，赞一个