性能基准

GCC · -O2 · Release。数据为单次运行取最优值。

ccmap vs std::map — 100K 顺序操作

函数指针模式（默认）

CCMAP_COMPARE 宏模式（零开销内联比较）

erase 始终快 8-11×：侵入式设计不释放节点内存，只修改指针。std::map 需释放内部树节点 + 析构 pair。

宏模式：insert 接近持平（1.45×），find 反超（0.83×）——比较完全内联，与 std::map 模板 functor 相同零开销。 定义 CCMAP_COMPARE(a,b) 宏即可切换，无需修改业务代码。

cchashmap vs std::unordered_map vs uthash — 200K 随机操作

全链路优于 STL 和 uthash。cchashmap 与 uthash 同为 header-only 侵入式 C 哈希表，但 cchashmap 缓存 hash 值（避免重复计算）+ 位掩码索引 + CCHASHMAP_DEFAULT_SLOT=64 减少 resize 次数，find 比 uthash 快 7×。

cclist vs std::list — 200K 操作

push/pop 比 std::list 快 12×。侵入式链表无单独节点分配开销。

cclink vs std::forward_list — 200K 操作

push/pop 比 std::forward_list 快 19-33×。侵入式单链表 head+tail 指针，push_front / pop_front 均为 O(1)。

ccheap vs std::priority_queue — 200K 操作

函数指针模式（默认，container_of 恢复父结构体）

CCHEAP_COMPARE 宏模式（零开销内联比较）

侵入式指针数组。函数指针模式与 STL 接近；宏模式直接比较 node.priority 字段（无需 container_of），消除间接调用。 通过 -DCCHEAP_ARITY=4 / 8 可切换 D-ary 分叉数。

ccvector vs std::vector — 500K 操作

push_back 比 STL 快 1.9×——ccvector 更轻量。ccvector_at 用 __builtin_expect 标注边界检查为 unlikely 分支，编译器将热路径优化为直接数组索引，access 反超 STL。

ccflatmap vs ccmap vs std::map — 50K 随机操作

逐个插入/删除（ccflatmap_insert/ccflatmap_erase）：因 O(n) memmove 较慢，适合低频修改场景。

批量插入（push_back + sort）：3.48 ms 比 ccmap 快 5.5×——追加 O(1) + 快速排序 O(n log n)。

批量删除（erase_unordered + sort）：5.84 ms 比 ccmap 快，比逐个删除快 83×——swap-with-last O(1) + 最后一次性重排。

find：branchless 二分搜索（cmov）5.70 ms，三家最快。iterate：连续内存指针递增 0.09 ms，比 ccmap 快 8×。

删除策略对比：erase vs erase_unordered + sort

规则：删除 ≤50 个元素用 ccflatmap_erase，超过 50 个用 ccflatmap_erase_unordered + ccflatmap_sort。 erase_unordered 的 sort 是固定入场费（≈0.8ms），与删除数量无关。erase 成本随删除数 K 线性增长（O(Kn) memmove）。 交叉点约在 K = 2·log₂(n) ≈ 32（理论值），实测 ≈50（含常数因子）。

cctreap vs std::map — 100K 顺序操作

priority 由内部 xorshift64 自动生成，无需外部管理。支持 CCTREAP_COMPARE 宏消除函数指针，以及 CCTREAP_RAND 宏替换随机数生成器。

insert / find / erase / iterate

insert 快 2.5×——侵入式无堆分配 + treap 修复比 RB 树着色更简洁。升序 key 插入命中 fast-last 捷径（O(1) BST 阶段）。

find 稍慢 1.17×——主因是函数指针间接调用（key_cmp），每次比较额外 3-5 cycle × 约 40 次比较。定义 CCTREAP_COMPARE 宏可完全消除此差距。

erase 快 2.9×——同 insert 不涉及内存释放，_tp_del_fix 向下旋转比 RB 删除修复路径更短。

顺序统计（kth / rank）

kth：STL map 不支持 O(log n) 随机访问，std::advance(it, k) 每次 O(k)，平均前进 N/2 = 50K 步。treap 利用子树 size 字段二分下降，每次 O(log n)。

rank：STL std::distance(begin, it) 每次 O(n)。treap 下降时累加左子树大小，每次 O(log n)。

构建与运行

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --target bench